暴力递归

课程：P10-9.补充视频
image.png

汉诺塔问题

image.png
image.png

字符串所有子集（子序列）

image.png
image.png

打印字符串的全排列（done）

image.png
process(str)省空间做法。
不重复：去掉注释部分。
术语：分支限界。（剪枝）
image.png

背包问题

image.png
递归体：可变参数最少的选择。
image.png
image.png

N皇后

image.png
image.png

前缀树

问题：

  • “bc”：前缀树中有没有这个字符串。（Hash表也可以实现）
  • “ab”：前缀树中多少以 “ab” 作为前缀的字符串，根据 “b”路径尾节点的 pass 值就可以获得。（Hash表没法做到）

跟节点表示什么意思：

  • pass表示前缀树中包含多少个字符串；
  • pass表示有多少字符串是以空串作为前缀的；
  • end表示有多少个空串；

image.png
image.png

image.png
image.png

image.png
image.png

贪心算法

基础知识

堆 + 排序：最常用的方法。
image.png
image.png

会议安排问题

image.png
image.png

image.png
image.png

铜板切割问题

最小堆 + 哈夫曼编码。
image.png
image.png

项目利润

小根堆和大根堆联合使用。
image.png
image.png
image.png
image.png
image.png

数据流中位数

大根堆和小根堆配合使用。

  • 较小的 n/2 个数放到大根堆里，，较大的 n/2 个数放到小根堆里。
  • 时间复杂度 log(n)

image.png
image.png

KMP-P12

课程：P12
位置：1:20
next arr 最长前缀和最长后缀相等的串。
image.png
image.png
image.png
算法：
image.png
代码例子：
image.png
时间复杂度分析：
image.png
next数组求解：
image.png
image.png
image.png

滑动窗口-P13

P13
位置：1:43
image.png
image.png

R 右动双端队列更新：
image.png
L 右动双端队列更新：
image.png

单调栈-P13

P13
位置：2:11:15
image.png

image.png
image.png

树型 dp 套路

P14:

大数据问题

P15
image.png