算法面试通关 40 讲
覃超
Sophon Tech 创始人,前 Facebook 工程师,卡内基梅隆大学计算机硕士
78356 人已学习
新⼈⾸单¥68
课程目录
已完结/共 62 讲
第二章:理论讲解+面试题实战 (53讲)
算法面试通关 40 讲
登录|注册
留言
39
收藏
沉浸
阅读
分享
手机端
回顶部
当前播放: 30 | 面试题:生成有效括号组合
00:00 / 00:00
高清
  • 高清
1.0x
  • 2.0x
  • 1.5x
  • 1.25x
  • 1.0x
  • 0.75x
  • 0.5x
网页全屏
全屏
00:00
付费课程,可试看
01 | 合格程序员的第一步:算法与数据结构
02 | 如何事半功倍地学习算法与数据结构
03 | 如何计算算法的复杂度
04 | 如何通过LeetCode来进行算法题目练习
05 | 理论讲解:数组&链表
06 | 面试题:反转一个单链表&判断链表是否有环
07 | 理论讲解:堆栈&队列
08 | 面试题:判断括号字符串是否有效
09 | 面试题:用队列实现栈&用栈实现队列
10 | 理论讲解:优先队列
11 | 面试题:返回数据流中的第K大元素
12 | 面试题:返回滑动窗口中的最大值
13 | 理论讲解:哈希表
14 | 面试题:有效的字母异位词
15 | 面试题:两数之和
16 | 面试题:三数之和
17 | 理论讲解:树&二叉树&二叉搜索树
18 | 面试题:验证二叉搜索树
19 | 面试题:二叉树&二叉搜索树的最近公共祖先
20 | 理论讲解:二叉树遍历
21 | 理论讲解:递归&分治
22 | 面试题:Pow(x,n)
23 | 面试题:求众数
24 | 理论讲解:贪心算法
25 | 面试题:买卖股票的最佳时机
26 | 理论讲解:广度优先搜索
27 | 理论讲解:深度优先搜索
28 | 面试题:二叉树层次遍历
29 | 面试题:二叉树的最大和最小深度
30 | 面试题:生成有效括号组合
31 | 理论讲解:剪枝
32 | 面试题:N皇后问题
33 | 面试题:数独问题
34 | 理论讲解:二分查找
35 | 面试题:实现一个求解平方根的函数
36 | 理论讲解:字典树
37 | 面试题:实现一个字典树
38 | 面试题:二维网格中的单词搜索问题
39 | 理论讲解:位运算
40 | 面试题:统计位1的个数
41 | 面试题:2的幂次方问题&比特位计数问题
42 | 面试题:N皇后问题的另一种解法
43 | 理论理解:动态规划(上)
44 | 理论理解:动态规划(下)
45 | 面试题:爬楼梯
46 | 面试题:三角形的最小路径和
47 | 面试题:乘积最大子序列
48 | 面试题:股票买卖系列
49 | 面试题:最长上升子序列
50 | 面试题:零钱兑换
51 | 面试题:编辑距离
52 | 理论讲解:并查集
53 | 面试题:岛屿的个数&朋友圈(上)
54 | 面试题:岛屿的个数&朋友圈(下)
55 | 理论讲解: LRU Cache
56 | 面试题:设计和实现一个LRU Cache缓存机制
57 | 理论讲解:布隆过滤器
58 | 课程重点回顾
59 | FAQ答疑&面试中切题四件套
60 | 回到起点:斐波拉契数列
61 | 白板实战番外篇:斐波拉契数列
62 | 结课测试&最后的一些经验分享
登录 后留言

全部留言(39)

  • 最新
  • 精选
往事随风,顺其自然
比如两队括号,按理执行完以后生成了(())之后递归结束了,为什么还会进行递归操作?生成后面的()(),这个还是不理解,第一次递归完成不是return ,程序应该返回值了

作者回复: 还会继续回到上一层递归调用的函数里,把接下来的语句执行完。第一个括号位相当于一层,每层有两个括号的选择。所以肯定后续 ()() 也会被递归到。

2018-11-11
7
7
linxs
视频中那个樱桃小丸子写的是Java吧 老师口误说错了??

作者回复: 是 java 的。

2018-11-11
2
6
..
第三个条件,right<left&&right<n 后面的条件不需要了,因为right<left已经肯定小于n了

作者回复: 对的,好建议!

2019-03-23
5
爷爷刘大
关于代码风格的问题,这个不是樱桃小丸子的锅。leetcode或者其他很多ide的默认设置就是遇到循环或者条件的换行自动缩进四空格。

作者回复: 好的,了解。多谢说明。

2019-01-06
1
jackbauer
我还是理解不了为什么是2个空格缩进……,我们平时工作都是4个

作者回复: 在公司里肯定要服从公司的决定。只是现在整个行业里越来越多的公司使用2空格。

2019-10-27
2
A_foreign 이호연 wuli 혜리
这种放和不放的问题应该可以用动态规划解决的吧

作者回复: 这个题目用 DP 也是可以的。

2019-09-03
2
Terry
学了一点形式语言与自动机,于是就想着用生成的方法来写一个。思路应该和老师说的归纳法类似。 假设S,T是合法的串,于是有两种生成规则(注意判断长度不能超过n*2): 1. concat: S + T 2. expand: '(' + S + ')' 每轮循环从已有的串中取出串并应用以上两种规则,把生成的新串添加到集合中,直至集合的规模不再增大,算法收敛。 取出集合中长度为n*2的串作为结果即可。 提交可以通过,用时200MS+ 这个复杂度不知道怎么分析了。超哥有想法吗? ```processing public class GenerateParentheses { String concat(String s1, String s2) { return s1 + s2; } String expand(String s) { return "(" + s + ")"; } HashSet<String> set = new HashSet<>(); public List<String> generateParenthesis(int n) { ArrayList<String> result = new ArrayList<>(); if (n < 1) return result; int cnt = set.size(); set.add("()"); while (cnt < set.size()) { // 尚未收敛 cnt = set.size(); HashSet<String> frontier = new HashSet<>(); // 此轮新生成的序列 for (String s1: set) { if (s1.length() < n * 2) frontier.add(expand(s1)); for (String s2: set) { if (s1.length() + s2.length() <= n * 2) frontier.add(concat(s1, s2)); } } set.addAll(frontier); // 合并新旧集合。如果有新元素加进来,则会进入下一次循环 } for (String s: set) { if (s.length() == n * 2) result.add(s); } return result; } } ```

作者回复: 第一:重复生成的子串比较多;第二,对于由于有重复子串则需要创建和维护一个hashset,且每次进行三判重操作,进一步加大了时间消耗。

2019-04-04
雪球
老师平常写代码的时候用什么编辑器?不同的编辑器使用会不会形成不同的代码风格。比如换行与缩进。怎样才能修炼出一种比较优秀的代码风格。

作者回复: 最新较为受欢迎的是 vs code

2019-03-10
yenoumu
覃老师,复杂度用递归树的方法,我觉得是n x 2的2n次方啊。请您帮忙解答下,谢谢!

作者回复: 2n个盒子里可以放左或者右括号,所以 2^(2n)的复杂度,对吧?

2019-02-18
Chaos👾
比如两队括号,按理执行完以后生成了(())之后递归结束了,为什么还会进行递归操作?生成后面的()(),这个还是不理解,第一次递归完成不是return ,程序应该返回值了

作者回复: 每一个位置上都会遍历左右两个括号的可能性。

2018-12-20
收起评论