第4周总结
DFS 代码模板（递归写法、非递归写法）
递归写法
visited = set()
def dfs(node, visited):
if node in visited: # terminator
# already visited
return
visited.add(node)
# process current node here.
...
for next_node in node.children():
if next_node not in visited:
dfs(next_node, visited)
非递归写法
def DFS(self, tree):
if tree.root is None:
return []
visited, stack = [], [tree.root]
while stack:
node = stack.pop()
visited.add(node)
process (node)
nodes = generate_related_nodes(node)
stack.push(nodes)
# other processing work
...
BFS 代码模板
def BFS(graph, start, end):
visited = set()
queue = []
queue.append([start])
while queue:
node = queue.pop()
visited.add(node)
process(node)
nodes = generate_related_nodes(node)
queue.push(nodes)
# other processing work
...
102. 二叉树的层序遍历
方法一：深度优先搜索（dfs）【时间复杂度：O(n)，空间复杂度：O(n)】
方法二：广度优先搜索（bfs）【时间复杂度：O(n)，空间复杂度：O(n)】
433. 最小基因变化
方法一：深度优先搜索（dfs）【时间复杂度：O(n)，空间复杂度：O(n)】
方法二：广度优先搜索（bfs）【时间复杂度：O(n)，空间复杂度：O(n)】
22. 括号生成
方法一：暴力法【时间复杂度：O(2^{2n}n)，空间复杂度：O(2^{2n}n)】
方法二：回溯法
方法三：闭合数
方法四：深度优先遍历
方法五：广度优先遍历
方法六：动态规划
515. 在每个树行中找最大值
方法一：深度优先搜索（dfs）【时间复杂度：O(n)，空间复杂度：O(n)】
方法二：广度优先搜索（bfs）【时间复杂度：O(n)，空间复杂度：O(n)】
127. 单词接龙
方法一：广度优先搜索
方法二：双向广度优先搜索
126. 单词接龙 II （难度很大，还需要在琢磨下）
200. 岛屿数量
方法一：dfs【时间复杂度：O(M×N)，空间复杂度：最坏情况下为 O(M×N)】
方法二：bfs【时间复杂度：O(M×N)，空间复杂度：O(min(M,N))】
方法三：并查集【时间复杂度：O(M×N)，空间复杂度：O(M×N)】
529. 扫雷游戏
方法一：深度优先搜索（dfs）
方法二：广度优先搜索
322. 零钱兑换
方法一：贪心
方法二：动态规划-自上而下
方法三：动态规划：自下而上
860. 柠檬水找零
方法一：贪心【时间复杂度：O(N)，空间复杂度：O(1)】
122. 买卖股票的最佳时机 II
方法一：贪心（简单的一次遍历）【时间复杂度：O(N)，空间复杂度：O(1)】
方法二：动态规划【时间复杂度：O(N)，空间复杂度：O(1)】
方法三：暴力法【时间复杂度：O(n^n)，空间复杂度：O(n)】
方法四：峰谷法【时间复杂度：O(N)，空间复杂度：O(1)】
455. 分发饼干
方法一：贪心【时间复杂度：O(Nlog(N))，空间复杂度：O(1)】
874. 模拟行走机器人
方法一：情景模拟【时间复杂度：O(N+K)，空间复杂度：O(K)】
55. 跳跃游戏
方法一：贪心【时间复杂度：O(N)，空间复杂度：O(1)】
方法二：回溯【时间复杂度：O(N^2)，空间复杂度：O(n)】
方法三：自顶向下的动态规划【时间复杂度：O(N^2)，空间复杂度：O(2n)】
方法四：自底向上的动态规划【时间复杂度：O(N^2)，空间复杂度：O(n)】
45. 跳跃游戏 II
方法一：动态规划
方法二：贪心
69. x 的平方根
方法一：暴力法【时间复杂度：O(N)，空间复杂度：O(1)】
方法二：二分法【时间复杂度：O(log(N))，空间复杂度：O(1)】
方法三：袖珍计算器算法【时间复杂度：O(1)，空间复杂度：O(1)】
方法四：牛顿迭代法【时间复杂度：O(log(N))，空间复杂度：O(1)】
367. 有效的完全平方数
方法一：二分法【时间复杂度：O(log(N))，空间复杂度：O(1)】
方法二：牛顿迭代法【时间复杂度：O(log(N))，空间复杂度：O(1)】
function isPerfectSquare($num) {
if ($num < 2) return true;
$curr = intdiv($num, 2);
while ($curr * $curr > $num) {
$curr = intdiv($curr + $num / $curr, 2);
}
return $curr * $curr == $num;
}
33. 搜索旋转排序数组
方法一：二分法【时间复杂度：O(log(N))，空间复杂度：O(1)】
方法二：二分法（用位操作）参考地址 【时间复杂度：O(log(N))，空间复杂度：O(1)】
74. 搜索二维矩阵
方法一：直接二分查找【时间复杂度：O(log(N))，空间复杂度：O(1)】
153. 寻找旋转排序数组中的最小值
方法一：二分法（最优）【时间复杂度：O(log(N))，空间复杂度：O(1)】
方法二：排序【时间复杂度：O(Nlog(N))，空间复杂度：O(1)】