算法训练营 - 学习笔记 - 第三周

这周常想起乔新亮老师在他《乔新亮的CTO成长复盘》里面的一句话：”你看，不仅仅是工作，生活还有一大摊子事情等着你去处理。”真的是我这周的真实写照。

划重点

1. 要找到一种感觉：爱上看别的代码，“哦，我靠，原来这边还能这么写。”

2. 递归模板

3. recursion terminator(递归终结条件)

4. process logic in current level(处理当前层逻辑)

5. drill down(下探到下一层)

6. reverse the current level status if needed(清理当前层)

7. 思维要点

8. 不要人肉进行递归（最大误区）

9. 找到最近最简方法，将其拆解成可重复解决的问题（找最近重复子问题）

10. 数学归纳法思维

11. n 成立，n+1 也成立

12. 人类世界很多问题都具有重复性，找到其中的规律

13. 比较重要：给你一个问题，怎么拆分成子问题，然后 merge 子结果。

第 7 课 泛型递归、树的递归

为什么树的面试解题法一般都是递归：

1. 节点的定义

2. 重复性（自相似性）

递归

1. 找到递归“归去来兮”的感觉

实战题目解析

• 爬楼梯

• 斐波那契数列

• 第 n 级台阶 = 第 n - 1 级台阶 + 第 n - 2 级台阶

• 括号生成

• 如果判断括号合法

• left 随时可加，只要别超标

• right 必须要出现在左括号的后面，左个数 > 右个数

• 2 * n 个格子，可以随便放左括号或者右括号

• left ==n && right == n

• add(s); return

• if left < n

• _generate(left + 1, right, max, s + "(");

• if left > right

• generate(left, right + 1, max, s + ")");

第 8 课 分治、回溯

分治、回溯可以理解为特殊的递归。

找重复性、分解为多个子问题，组合结果。

分支 Divide & Conquer

分支代码模板

1. recursion terminator

2. if problem is None:

3. print result

4. return

5. prepare data

6. data = prepare_data(problem)

7. subproblems = split_problem(problem, data)

8. conquer subproblems

9. subresult1 = self.divide_conquer(subproblems[0], p1, ...)

10. subresult2 = self.divide_conquer(subproblems[1], p1, ...)

11. subresult3 = self.divide_conquer(subproblems[2], p1, ...)

12. process and generate the final result

13. result = process_result(subresult1, subresult2, subresult3, ...)

14. revert the current level states

回溯

回溯法采用试错的思想，它尝试分布的去解决一个问题。一层一层去试。

区别于暴力回溯

经典应用

1. 八皇后问题

例题

1. Pow(x,n)

2. 子集

3. 迭代

4. 电话号码的字母组合

5. N 皇后