第零章 核心框架

双指针->单链表

双指针->数组

快慢指针

左右指针

二叉树(纲要篇)

Tips:快速排序就是二叉树的前序遍历,归并排序是二叉树的后序遍历

  • 快速排序框架:
1
2
3
4
5
6
7
def sort(nums, lo, hi){
    # 前序遍历位置
    # 通过交换元素构建分界点 p
    p = partition(nums, lo, hi)
    sort(nums, lo, p-1)
    sort(nums, p+1, hi)
}
  • 归并排序框架:
1
2
3
4
5
6
7
8
9
def sort(nums, lo, hi){
	int mid = (lo + hi) / 2
	# 排序nums[lo..mid]
	sort(nums, lo, mid)
	# 排序nums[mid+1..hi]
	sort(nums, mid+1, hi)
	# 合并nums[lo..mid] 和 nums[mid+1..hi]
	merge(nums, lo, mid, hi)
}

二叉树遍历框架:

1
2
3
4
5
6
7
8
def traverse(root){
	if not root: return
	# 前序位置
	traverse(root.left)
	# 中序位置
	traverse(root.right)
	# 后序位置
}

前序,中序,后序

前序位置的代码只能从函数参数中获取父节点传递来的数据，而后序位置的代码不仅可以获取参数数据，还可以获取到子树通过函数返回值传递回来的数据

两种解题思路:

后序位置的特殊之处:

​ LeetCode543 二叉树的直径

层序遍历:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def levelTraverse(root){
	if not root: return
	que = deque()
	que.append(root)
    # 从上到下遍历二叉树的每一层
	while que:
    	# 从左到右遍历每一层的每个结点
		for i in range(len(que)):
    		cur = que.popleft()
    		# 将下一层结点放入队列
    		if cur.left:
    			que.append(cur.left)
    		if cur.right:
    			que.append(cur.right)
}

​ BFS算法框架

动态规划(框架)

动态规划框架:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 自顶向下递归的动态规划
def dp(状态1, 状态2, ...):
	for 选择 in 所有可能的选择:
		# 此时的状态已经因为做了选择而改变
		result = 求最值(result, dp(状态1, 状态2, ...))
	return result
# 自底向上迭代的动态规划
# 初始化 base case
dp[0][0][...] = base case
# 进行状态转移
for 状态1 in 状态1的所有取值:
    for 状态2 in 状态2的所有取值:
        for ...
        	dp[状态1][状态2][...] = 求最值(选择1, 选择2...)

解题思路:

暴力穷举,带备忘录的递归和dp数组的迭代(可降空间复杂度为O(1))

总结

计算机解决问题其实没有任何奇技淫巧，它唯一的解决办法就是穷举， 穷举所有可能性。算法设计无非就是先思考“如何穷举”，然后再追求“如何聪明地穷举”。

列出状态转移方程，就是在解决“如何穷举”的问题。之所以说它难，一是因为很多穷举需要递归实现，二是因为有的问题本身的解空间复杂，不那么容易穷举完整。

备忘录、DP table 就是在追求“如何聪明地穷举”。用空间换时间的思路，是降低时间复杂度的不二法门，除此之外，试问，还能玩出啥花活？

回溯算法(框架)

Tips:回溯算法和 DFS 算法的细微差别是：回溯算法是在遍历「树枝」，DFS 算法是在遍历「节点」

回溯算法框架

1
2
3
4
5
6
7
8
9
res = []
def backtrack(路径, 选择列表):
	if 满足结束条件:
		res.add(路径)
		return
	for 选择 in 选择列表:
		做选择
		backtrack(路径, 选择列表)
		撤销xrz

其核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」

总结

时间复杂度都不可能低于 O(N!)，因为穷举整棵决策树是无法避免的。这也是回溯算法的一个特点，不像动态规划存在重叠子问题可以优化，回溯算法就是纯暴力穷举，复杂度一般都很高。

写 backtrack 函数时，需要维护走过的「路径」和当前可以做的「选择列表」，当触发「结束条件」时，将「路径」记入结果集。

回溯->排列,组合,子集

无论是排列、组合还是子集问题，简单说无非就是让你从序列 nums 中以给定规则取若干元素，主要有以下几种变体：

  1. 元素无重不可复选，即 nums 中的元素都是唯一的，每个元素最多只能被使用一次，这也是最基本的形式。

​ 以组合为例，如果输入 nums = [2,3,6,7]，和为 7 的组合应该只有 [7]。

  1. 元素可重不可复选，即 nums 中的元素可以存在重复，每个元素最多只能被使用一次。

​ 以组合为例，如果输入 nums = [2,5,2,1,2]，和为 7 的组合应该有两种 [2,2,2,1] 和 [5,2]。

  1. 元素无重可复选，即 nums 中的元素都是唯一的，每个元素可以被使用若干次。

​ 以组合为例，如果输入 nums = [2,3,6,7]，和为 7 的组合应该有两种 [2,2,3] 和 [7]。

​ 但无论形式怎么变化，其本质就是穷举所有解，而这些解呈现树形结构，所以合理使用回溯算法框架，稍改代码框架即可把这些问题一网打尽。

​ 回溯算法核心

总结

  1. 元素无重复不可复选

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    # 组合/子集问题回溯算法框架
    def backtrack(nums, start){
    	for i in range(start, len(nums)){
            # 做选择
    		tarck.addLast(nums[i])
            # 注意参数
    		backtrack(nums, i+1)
            # 撤销选择
    		track.removeLast()
    	}
    }
    # 排列问题回溯算法框架
    def backtrack(nums){
        for i in range(len(nums)){
            # 剪枝逻辑
            if used[i]: continue
            # 做选择
            used[i] = true
            track.addLast(nums[i])
            backtrack(nums)
            # 撤销选择
            track.removeLast()
            used[i] = false
        }
    }

  2. 元素可重不可复选

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    nums.sort()
    # 组合/子集问题回溯算法框架
    def backtrack(nums, start){
        # 回溯算法标准框架
        for i in range(start, len(nums)){
            # 剪枝逻辑,跳过相同的相邻树枝
            if i>start and nums[i]==nums[i-1]: continue
            # 做选择
            track.addLast(nums[i])
            # 注意参数
            backtrack(nums, i+1)
            # 撤销选择
            track.removeLast()
        }
    }

    nums.sort()
    # 排列问题回溯算法框架
    def backtrack(nums){
        for i in range(len(nums)){
            # 剪枝逻辑
            if used[i]:continue
            # 剪枝逻辑,固定相同的元素在排列中的相对位置
            if i>0 and nums[i]==nums[i-1] and not used[i-1]: continue
            # 做选择
            used[i] = true
            track.addLast(nums[i])
            backtrack(nums)
            #撤销选择
            track.removeLast()
            used[i] = false
        }
    }

  3. 元素无重可复选

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    # 组合/子集问题回溯框架
    def backtrack(nums, start){
        # 回溯算法标准框架
    	for i in range(start, len(nums)){
            # 做选择
    		track.addLast(nums[i])
            # 注意参数
    		backtrack(nums, i)
            # 撤销选择
    		track.removeLase()
    	}
    }
    # 排列问题回溯算法框架
    def backtrack(nums){
    	for i in range(len(nums)){
            # 做选择
            track.addLast(nums[i])
            backtrack(nums)
            # 撤销选择
            track.removeLast()
        }
    }

BFS(框架)

二分搜索

  • 寻找一个数(基本的二分搜索)

    LeetCode704 二分查找

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    def binarySearch(nums, target){
    	left, right = 0, len(nums)-1
    	while(left<=right):
    		mid = left+(right-left)//2
    		if(nums[mid]==target):
        		# 直接返回
    			return mid
    		elif nums[mid]>target:
    			right = mid-1
    		elif nums[mid]<target:
    			left = mid+1
        # 直接返回
    	return -1
    }

  • 寻找左侧边界的二分搜索

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    def left_bound(nums, target){
        left, right = 0, len(nums)-1
        # 搜索区间为[left, right]
        while left<=right:
        	mid = left + (right-left)//2
        	if nums[mid]==target:
        		# 收缩右侧边界
        		right = mid+1
        	elif nums[mid]<target:
        		# 搜索区间变为[mid+1, right]
        		left = mid+1
    	    elif nums[mid]>target:
        		# 搜索区间变为[left, mid-1]
        		right = mid
        # 判断target是否存在于nums中
        # 此时target比所有数都大,返回-1
        if left==len(nums): return -1
        # 判断一下nums[left]是不是target
        return nums[left]==target ? left : -1
    }

  • 寻找右侧边界的二分查找

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    def right_bound(nums, target){
        left, right = 0, len(nums)-1
        while left<=right:
        	mid = left+(right-left)//2
        	if nums[mid]<target:
        		left=mid+1
        	elif nums[mid]>target:
        		right = mid-1
    	    elif nums[mid]==target:
        		# 收缩左边界
    		    left = mid+1
        # 最后改成返回left-1
        if left-1 < 0: return -1
        return nums[left-1]==target ? left-1 :-1
    }

总结:

​ LeetCode34 在排序数组中查找元素的第一个和最后一个位置

  1. 最基本的二分查找算法

    1
    2
    3
    4
    5
    6
    7
    因为我们初始化 right = nums.length - 1
    所以决定了我们的「搜索区间」是 [left, right]
    所以决定了 while (left <= right)
    同时也决定了 left = mid+1 和 right = mid-1

    因为我们只需找到一个 target 的索引即可
    所以当 nums[mid] == target 时可以立即返回

  2. 寻找左侧边界的二分查找

    1
    2
    3
    4
    5
    6
    7
    8
    因为我们初始化 right = nums.length
    所以决定了我们的「搜索区间」是 [left, right)
    所以决定了 while (left < right)
    同时也决定了 left = mid + 1 和 right = mid

    因为我们需找到 target 的最左侧索引
    所以当 nums[mid] == target 时不要立即返回
    而要收紧右侧边界以锁定左侧边界

  3. 寻找右侧边界的二分查找

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    因为我们初始化 right = nums.length
    所以决定了我们的「搜索区间」是 [left, right)
    所以决定了 while (left < right)
    同时也决定了 left = mid + 1 和 right = mid

    因为我们需找到 target 的最右侧索引
    所以当 nums[mid] == target 时不要立即返回
    而要收紧左侧边界以锁定右侧边界

    又因为收紧左侧边界时必须 left = mid + 1
    所以最后无论返回 left 还是 right，必须减一

滑动窗口

总结:

1. 什么时候应该扩大窗口?
1. 什么时候应该缩小窗口?
1. 什么时候应该更新答案?

买股票(DP)

打家劫舍(DP)

  • 打家劫舍1

    LeetCode198 打家劫舍

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    # 带备忘录
    def rob(nums):
        n = len(nums)
        if n==0: return 0
    	if n==1: return nums[0]
    	dp = [0]*n
        dp[0], dp[1] = nums[0], max(nums[0], nums[1])
        for i in range(2, n):
            dp[i] = max(dp[i-1], dp[i-2]+nums[i])
        return dp[n-1]
    # 优化空间
    def rob(nums):
        prev, curr = 0, 0
        for i in nums:
            prev, curr = curr, max(curr, prev+1)
        return curr

  • 打家劫舍2

    LeetCode213 打家劫舍2

  • 打家劫舍3

    LeetCode337 打家劫舍3

nSum

第一章 数据结构

链表

1

拉宾-卡普

数组

二叉树

图

设计数据结构

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

分享文章

快来参与讨论吧~