深度优先的思想与“回溯”法有相似之处。
- 模板：
func dfs_traversal(root: TreeNode?) {
// 判断 base case
if (root == nil) {
return;
}
// 处理当前node...
// 访问两个相邻结点：左子结点、右子结点
dfs_traversal(root!.left)
dfs_traversal(root!.right)
}- 模板：
// 借助队列实现BFS
func levelOrder(_ root: TreeNode?) -> [[Int]] {
if root == nil { return [] }
var result = [[Int]]()
var queue = [TreeNode]()
queue.append(root!)
while !queue.isEmpty {
var levelValues = [Int]()
let n = queue.count // 这一层所有节点的数量
for i in 0..<n {
let node = queue.removeFirst()
levelValues.append(node.val)
if let left = node.left {
queue.append(left)
}
if let right = node.right {
queue.append(right)
}
}
result.append(levelValues)
}
return result
}
- 常见题型：
二叉树的层序遍历
在每个树行中找最大值
单词接龙
扫雷游戏
-
场景：
问题能够分解成子问题解决，子问题的最优解能推导到最终问题的最优解，才可以使用贪心法； 贪心与动态规划的区别：贪心法对每个子问题的解决方案的选择不能回退，而动态规划则会记录历史的运算结果，根据历史来决定当前选择，可以回退。
-
场景： 目标函数单调性(递增or递减) + 存在上下界 + 能够使用index线性访问
-
模板：
func binarySearch(values:[Int], target: Int) -> Int? {
// 前提：数组是已经排序好的，从小到大
var left = 0 // 左边界
var right = values.count - 1 // 右边界
while left <= right {
let mid = left + ((right - left) / 2) // 中间元素
if values[mid] == target { // 找到目标
return mid
} else if values[mid] < target { // 目标在mid右侧,更新左界继续
left = mid + 1
} else { // 目标在mid左侧,更新右界继续
right = mid - 1
}
}
return nil
}- 常见题型：
x 的平方根(另一种方法：牛顿迭代法注意理解)
有效的完全平方数
搜索旋转排序数组
寻找旋转排序数组中的最小值
搜索二维矩阵