Week 04

深度优先搜索、广度优先搜索

参考链接

• DFS 代码模板（递归写法、非递归写法）
• BFS 代码模板
• 已知前序、中序，写出后序；或已知后序、中序，推前序

实战题目

• 二叉树的层序遍历 (leetcode) （亚马逊、字节跳动、微软在半年内面试中考过
• N 叉树的层序遍历 (leetcode) （亚马逊在半年内面试中考过）
• [] 最小基因变化 (leetcode)
• 括号生成 (leetcode) (字节跳动在半年内面试中考过)
• 在每个树行中找最大值 (leetcode)（微软、亚马逊、Facebook 在半年内面试中考过）

课后作业

• [] 单词接龙 (leetcode)（亚马逊在半年内面试常考）
• [] 单词接龙 II (leetcode)（微软、亚马逊、Facebook 在半年内面试中考过）
• 200. 岛屿数量 (leetcode)（近半年内，亚马逊在面试中考查此题达到 350 次）
• 695. 岛屿的最大面积 (leetcode)
• 1254. 统计封闭岛屿的数目 (leetcode)
• [] 扫雷游戏 (leetcode)（亚马逊、Facebook 在半年内面试中考过）

贪心算法

参考链接

• 动态规划定义

• [] 零钱兑换

课后作业

• 柠檬水找零 (leetcode)（亚马逊在半年内面试中考过）
• [] 买卖股票的最佳时机 II (leetcode)（亚马逊、字节跳动、微软在半年内面试中考过）
• 分发饼干 (leetcode)（亚马逊在半年内面试中考过）
• [] 模拟行走机器人 (leetcode)
• [] 跳跃游戏 (leetcode)（亚马逊、华为、Facebook 在半年内面试中考过）
• [] 跳跃游戏 II (leetcode)（亚马逊、华为、字节跳动在半年内面试中考过）

二分查找

参考链接

• 二分查找代码模板
• Fast InvSqrt() 扩展阅读

实战题目

• x 的平方根 (leetcode)（字节跳动、微软、亚马逊在半年内面试中考过）
• 有效的完全平方数 (leetcode)（亚马逊在半年内面试中考过）

课后作业

• 33. 搜索旋转排序数组 (leetcode（Facebook、字节跳动、亚马逊在半年内面试常考）)
• 81. 搜索旋转排序数组 II (leetcode（Facebook、字节跳动、亚马逊在半年内面试常考）)
• 153. 寻找旋转排序数组中的最小值 (leetcode（亚马逊、微软、字节跳动在半年内面试中考过）)
• 154. 寻找旋转排序数组中的最小值 II (leetcode（亚马逊、微软、字节跳动在半年内面试中考过）)
• 搜索二维矩阵 (leetcode（亚马逊、微软、Facebook 在半年内面试中考过）)
• 使用二分查找，寻找一个半有序数组 4, 5, 6, 7, 0, 1, 2 中间第一个无序的地方

下周预习

预习题目：

• [] 最长公共子序列题目
• [] 三角形最小路径和
• [] 最大子序和
• [] 打家劫舍

训练场练习（选做）

二分法相关

• [] 分数统计 (leetcode)

*DFS、BFS 相关

• [] 二叉树纵向逆序遍历 (leetcode)
• [] 包裹容量问题 (leetcode)
• [] IP 还原问题 (leetcode)
• [] 任务处理问题 (leetcode)
• [] 追赶朋友 (leetcode)

*贪心相关

• [] 饥饿的老鼠 (leetcode)