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

杂想

年龄越来越大，感觉自己连发脾气勇气的都被现实生活磨掉了。不敢发脾气。。。

所以会羡慕小孩，想哭哭，想笑笑，喜怒哀乐都不用隐藏。不像成年人的世界，有时候真的是认清现实后，被现实教育的一点脾气都没有。老人、小孩、房贷、车贷。。。

成年人的世界哪有“容易”二字。

第 9 课 深度优先搜索和广度优先搜索

DFS(Deep First Search)

搜索-遍历：

1. 深度优先

2. 每个节点访问一次且仅访问一次（非智能搜索 - 非深度学习）

3. 遍历顺序：总是从根节点开始

visited = set()def dfs(node, visited):  if node in visited:    # already visited    return   visited.add(node)    # process current node  # ... # logic here  # dfs(node.left)  # dfs(node.right)  for next_node in node.children():    if not next_node in visited:      dfs(next_node, visited)  

BFS(Breadth First Search)

广度优先搜索更加符合人脑的思考方式

def BFS(graph, start, end):  queue = []  queue.append([start])  visited.add(start)    while queue:    node = queue.popleft()    visited.add(node)        process(node)    nodes = generate_related_nodes(node)    queue.push(nodes)

实战例题：

1. 二叉树的层次遍历

2. 最小基因变化

3. 括号生成

4. Number of islands

第 10 课 贪心算法 Greedy

贪心算法是一种在每一步选择中都采取在当前状态下最好或者最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法。

贪心算法与动态规划的不同在于它对每个子问题的方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。

贪心法可以解决一些最优化问题，如求图中的最小生成树、求哈夫曼编码等。然而对于工程和生活中的问题，贪心法一般不能得到我们所要求的答案。

适用贪心算法的场景

问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。这种子问题最优解称为最优子结构。

实战例题

1. 零钱兑换(Coin Change)

2. 分发饼干

3. 买卖股票的最佳时机

4. 跳跃游戏(Jump Game)

第 11 课 二分查找

二分查找的前提

1. 目标函数单调性（单调递增或者递减）- 有序性

2. 存在上下界(bounded)

3. 能够通过索引访问(index accessible)

left, right = 0, len(array) - 1while left <= right:  mid = (left + right) / 2  if array[mid] == target:    # find the target!!    break or return result  elif array[mid] < target:    left = mid + 1  else:    right = mid - 1

实战题目

1. Sqrt

2. isPerfectSquare

3. 搜索旋转排序数组(Search in rotated sorted array)

4. 二分查找 O(logN)

Notes

1. 五毒神掌

2. 四部做题法

3. clarification

4. consideration，所有解法都思考一遍

5. coding

6. testing