-
搜索 - 遍历
- 每个节点都要访问一次
- 每个节点仅访问一下
- 对于节点的访问顺序不限
- 深度优先：depth first search
- 广度优先：breadth first search
-
# Python # 递归写法（二叉树） def dfs(node): if node in visited: # already visited return visited.add(node) # process current node # ... # logic here dfs(node.left) dfs(node.right) # 递归写法（多叉树） 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 ...
-
# Python 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 ...
- 贪心算法 Greedy
- 贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法
- 贪心算法与动态规划的不同在于它对每个子问题的解决方案都是做出选择不能回退。动态规划会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能
- 贪心法可以解决一些最优化问题，如：求图中的最小生成树、求哈夫曼编码等。然而对于工程和生活中的问题，贪心法一般不能得到我们所要求的答案。
- 一旦一个问题可以通过贪心法来解决，那么贪心法一般是解决这个问题的最好办法。由于贪心法的高效性以及其所求得的答案比较接近最优结果，贪心法也可用作辅佐算法或者直接解决一些要求结果不特别精确的问题。
- 贪心算法的适用场景
- 简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。这种子问题最优解称为最优子结构。
- 贪心算法与 动态规划 的不同在于它对每个子问题的解决方案都是做出选择，不能回退。动态规化则会保存以前的远算结果，并根据以前的结果对当前的进行选择，有回退功能。
-
二分查找的前提条件
- 目标函数单调性（单调递增或者递减）
- 存在上下界（bounded）
- 能够通过索引访问（index accessible）
-
参考链接
-
# Python def binary_search(nums, target): left, right = len(nums) - 1 while left <= right: mid = (left + right) / 2 if nums[mid] == target: # find the target break or return result elif nums[mid] < target: left = mid + 1 else: right = mid - 1
- 柠檬水找零
- 买卖股票的最佳时机 II
- 分发饼干
- 模拟行走机器人
- 使用二分查找，寻找一个半有序数组 [4, 5, 6, 7, 0, 1, 2] 中间无序的地方
-
class Solution: def canJump(self, nums: List[int]) -> bool: if not nums: return False end_reachble = len(nums) - 1 for i in range(len(nums) - 1, -1, -1): if nums[i] + i >= end_reachble: end_reachble = i return end_reachble == 0
-
class Solution: def search(self, nums: List[int], target: int) -> int: # 暴力求解，时间复杂度 O(n) for i, n in enumerate(nums): if n == target: return i else: return -1 def search1(self, nums: List[int], target: int) -> int: # 二分法查找，时间复杂度 O(logn) if len(nums) == 0: return -1 left, right = 0, len(nums) - 1 while left <= right: mid = (left + right) // 2 if nums[mid] == target: return mid if nums[0] <= target < nums[mid] or target < nums[mid] < nums[0] or nums[mid] < nums[0] <= target: right = mid - 1 else: left = mid + 1 return -1