Leetcode Exercise Guidence via Python.

• 力扣（LeetCode）官网

本文目录：

零、在线编程常见输入输出练习

一、算法篇

• 贪心算法：分配问题、区间问题
• 双指针：搜索、滑动窗口、快慢指针
• 排序算法
• 二分查找
• 搜索算法：深度优先搜索、回溯法、广度优先搜索
• 动态规划：一维动态规划、二维动态规划、分割问题、并行状态问题、背包问题、股票问题、树形动态规划问题
• 分治法
• 位运算
• 数学问题：模拟求和、数论、几何、随机采样、脑筋急转弯

二、数据结构篇

• 字符串：字符串理解、字符串比较
• 基本数据结构：数组、栈和队列、单调栈、优先队列（堆）、哈希表（字典和集合）
• 基于指针的数据结构：链表、树、图
• 其他数据结构：前缀和与积分图、并查集、设计数据结构

零、在线编程常见输入输出练习

编程题分两种考核方式：

• 核心代码模式：只需要实现函数核心功能并返回结果，无须处理输入输出；
• ACM模式：按照题目输入输出说明和例题给出的输入输出规范处理输入输出，不同的语言有不同的输入输出规范。

本文介绍ACM模式中常用的输入输出写法（以python语言为例）。

⚪ 输入写法

(1) 输入单行

# 接收一个字符串输入
line = input()

# 接收一个整数输入
line = int(input())

# 接收一组字符串输入（空格隔开）
line = input().split(' ')

# 接收一组整数输入（空格隔开）
line = list(map(int, input().split(' ')))

(2) 输入多行

# 接收固定长度的输入，第一次输入为行数
n = int(input())
for _ in range(n):
    line = input()

# 接收不定长度的输入（使用异常处理机制）
while True:
    try:
        lint = input()
    except EOFError:
        break

# 接收不定长度的输入（使用系统库）
import sys
for line in sys.stdin:
    line = line.strip()  # 删除结尾换行符
    pass

⚪ 输出写法

(1) 输出单行

# 输出一个元素
print(x)

# 输出一行字符串（空格隔开）
print(' '.join(alist))
# 或
for a in alist:
    print(a, end=' ')

一、算法篇

⚪ 贪心算法

贪心算法（又称贪婪算法）是指通过选择当前状态下局部最优的操作来获得全局最优的算法。贪心算法不一定能得到全局最优解，能用贪心算法解决的问题需要满足以下条件：

• 最优子结构：规模较大的问题的解由规模较小的子问题的解组成，规模较大的问题的解只由其中一个规模较小的子问题的解决定；
• 无后效性：后面阶段的求解不会修改前面阶段已经计算好的结果；
• 贪心选择性质：从局部最优解可以得到全局最优解。

(1) 分配问题

分配问题是指以一维数组的形式给出一系列物体，要求为每个物体分配一个属性，且每个物体的属性受到其左右物体的约束；这种约束形式可能是预先指定的，也可能是通过排序施加的。

(2) 区间问题

区间问题是指给定一系列区间，通过判断区间是否重叠来解决问题。

若按照区间的左端点进行排序，则可以求得所有重叠区间的并集。反之若按照区间的右端点进行排序，则可以求得所有重叠区间的交集。上述两种过程都可以通过判断当前左端点是否超过记录的右端点来实现：

n = len(alist)

# 按照左端点排序，求并集
alist.sort(key = lambda x: x[0])
ans = []
l, r = alist[0][0], alist[0][1]
for i in range(1, n):
    if alist[i][0] > r: # 区间没有重叠
        ans.append([l, r])
        l, r = alist[i][0], alist[i][1]
    else: #区间重叠
        r = max(r, alist[i][1])
ans.append([l, r])


# 按照右端点排序，求交集
alist.sort(key = lambda x: x[1])
l, r = alist[0][0], alist[0][1]
for i in range(1, n):
    if alist[i][0] >= r: # 区间没有重叠
        ans.append([l, r])
        l, r = alist[i][0], alist[i][1]
    else: #区间重叠
        l = max(l, alist[i][0])
ans.append([l, r])    

⚪ 双指针

双指针算法是指用两个指针变量在线性结构上遍历而解决问题。常见的情况包括：

• 搜索：两个指针指向同一数组，遍历方向相同或相反；此时待搜索的数组往往是排好序的。
• 滑动窗口：两个指针指向同一数组，遍历方向相同且不会相交；此时两个指针包围的区域即为当前的窗口。
• 快慢指针：两个指针在链表上同向移动而解决问题。

(1) 搜索

在相向遍历的双指针搜索中，一个初始指向最小的元素，即数组最左边，向右遍历；一个初始指向最大的元素，即数组最右边，向左遍历。

l, r = 0, len(alist)-1
while l < r:
    if case1:
        return
    elif case2:
        l += 1
    else:
        r -= 1

(2) 滑动窗口

在滑动窗口类型的问题中都会有两个指针，一个用于「延伸」现有窗口的 $r$ 指针，和一个用于「收缩」窗口的 $l$ 指针。在任意时刻，只有一个指针运动，而另一个保持静止。

l, r = 0, 0:
while r < len(alist):
    if case1:
        r += 1
    else:
        l += 1

(3) 快慢指针

快慢指针（Floyd 判圈法）适用于链表找环路的通用解法。给定两个指针，分别命名为 slow 和 fast，起始位置在链表的开头。每次 fast 前进两步，slow 前进一步。如果链表中存在环，则一定存在一个时刻 slow 和 fast 相遇。

设链表中环外部分的长度为 $a$。slow 指针进入环后，又走了 $b$ 的距离与 fast 相遇。此时，fast 指针已经走完了环的 $n$ 圈，因此它走过的总距离为 $a+b+n(b+c)$。

任意时刻，fast 指针走过的距离都为 slow 指针的 $2$ 倍。因此有:

即从相遇点到入环点的距离$c$加上 $n-1$ 圈的环长，恰好等于从链表头部到入环点的距离$a$。

因此当 slow 和 fast 第一次相遇时，将 fast 重新移动到链表开头，并让 slow 和 fast 每次都前进一步。最终，它们会在入环点相遇。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

def detectCycle(head: Optional[ListNode]) -> Optional[ListNode]:
    slow, fast = head.next, head.next.next
    while slow != fast:
        slow = slow.next
        fast = fast.next.next               
    fast = head
    while slow != fast:
        slow, fast = slow.next, fast.next
    return fast

此外快慢指针还可以用于寻找单链表中的第$\frac{n}{k}$个节点（$n$是链表长度）：慢指针一次走一步，快指针一次走$k$步，快慢指针同时出发。当快指针移动到链表的末尾时，慢指针恰好到链表的第$\frac{n}{k}$个节点。

以寻找链表中间节点（$k=2$）为例：

slow, fast = head, head
while fast.next and fast.next.next:
    slow = slow.next
    fast = fast.next.next

⚪ 排序算法

常见的排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。关于这些排序算法的细节介绍请参考Python实现排序算法。

python提供了内置的排序算法：

# 直接排序数组（从小到大）
alist.sort(reverse=False)
alist = sorted(alist)

# 获取排序索引（从小到大）
idx = list(range(len(alist)))
idx.sort(key=lambda i: alist[i])

虽然在python里可以通过alist.sort()快速排序，而且刷题时很少需要自己手写排序算法，但是熟习各种排序算法可以加深对算法的基本理解，以及解出由这些排序算法引申出来的题目。

⚪ 二分查找

二分查找也常被称为二分法或者折半查找，每次查找时通过将待查找区间分成两部分并只取一部分继续查找，将查找的复杂度大大减少。对于一个长度为 $O(n)$ 的数组，二分查找的时间复杂度为 $O(\log n)$。

二分查找时区间的左右端取开区间还是闭区间在绝大多数时候都可以，尝试熟练使用一种写法，比如左闭右开（满足 C++、Python 等语言的习惯）或左闭右闭（便于处理边界条件）；如果某种写法无法跳出死循环，则考虑尝试另一种写法。

二分查找也可以看作双指针的一种特殊情况，但一般会将二者区分。双指针类型的题，指针通常是一步一步移动的；而在二分查找里，指针每次移动半个区间长度。

l, r = 0, n-1
while l <= r:
#    mid = (l+r)//2
    mid = l+(r-l)//2 # 搜索范围较大时，防止下标越界
    if alist[mid] == c:
        return True
    elif alist[mid] < c:
        l = mid + 1
    else:
        r = mid - 1

可以通过bisect库中的bisect.bisect_left函数实现二分查找。该函数接收一个有序数组和一个目标值，返回大于等于目标值的第一个下标(相当于C++中的lower_bound)。

import bisect
idx = bisect.bisect_left(alist, target)
if idx < len(alist) and alist[idx] == target:
    return True
return False

如果题目中有「最大化最小值」或者「最小化最大值」，一般都是二分查找答案。以最大化最小值类型的题目为例，首先给定最小值可能的存在范围$[left, right]$，每次二分查找中值$mid$；判断在给定题目条件下能否取得该最小值；若能够取得，则还有可能取得更大的值，此时更新$left$；若不能够取得，则只能进一步评估更小的最小值，此时更新$right$。

def MaxMin(alist):
    left, right = minVal, maxVal # 设置搜索范围
    ans = -1
    while left <= right:
        mid = left + (right-left)//2
        if check(mid, alist): # 若mid能取得
            ans = mid
            left = mid+1
        else:
            right = mid-1
    return ans

⚪ 搜索算法

(1) 深度优先搜索

深度优先搜索（depth-first search，DFS）在搜索到一个新的节点时，立即对该新节点进行遍历；对于树结构而言，由于总是对新节点调用遍历，因此看起来是向着“深”的方向前进。

DFS遍历需要用先入后出的栈（stack）来实现，也可以通过与栈等价的递归来实现。但因为栈与递归的调用原理相同，而递归相对便于实现，因此刷题时推荐使用递归式写法，同时也方便进行回溯。不过在实际工程上，直接使用栈可能才是最好的选择，一是因为便于理解，二是更不易出现递归栈满的情况。

有时我们可能会需要对已经搜索过的节点进行标记，以防止在遍历时重复搜索某个节点，这种做法叫做状态记录或记忆化（memoization）。

深度优先搜索类型的题可以分为主函数和辅函数，主函数用于遍历所有的搜索位置，判断是否可以开始搜索，如果可以即在辅函数进行搜索。辅函数则负责深度优先搜索的递归调用。

在辅函数内进行递归搜索时，需要注意边界条件的判定。边界判定一般有两种写法，一种是先判定是否越界，只有在合法的情况下才进行下一步搜索（即判断放在调用递归函数前）；另一种是先进行下一步搜索，待下一步搜索开始时再判断是否合法（即判断放在辅函数第一行）。

一般地，使用DFS遍历$m \times n$的$0/1$二维数组中所有值为$1$的连通域的写法如下：

def solve(matrix):
    m, n = len(matrix), len(matrix[0])
    # 状态记录
    visited = set()


    # 写法①：先判定边界条件再进行搜索
    def dfs(i, j):
        visited.add((i,j))
        for di,dj in [(-1,0), (1,0), (0,-1), (0,1)]:
            new_i, new_j = i+di, j+dj
                if (0<=new_i<m) and (0<=new_j<n) and (new_i, new_j) not in visited and matrix[new_i][new_j] == 1:
                    dfs(new_i, new_j)  
                    
    for i in range(m):
        for j in range(n):
            if matrix[i][j]==1 and (i, j) not in visited:
                dfs(i, j)


    # 写法②：先搜索再判定边界条件
    def dfs(i, j):
        if (i<0 or i>=m) or (j<0 or j>=n) or (i, j) in visited or matrix[i][j] == 0:
            return
        visited.add((i,j))
        for di,dj in [(-1,0), (1,0), (0,-1), (0,1)]:
            dfs(i+di, j+dj)  
                    
    for i in range(m):
        for j in range(n):
            dfs(i, j)

(2) 回溯法

回溯法（backtracking）是优先搜索的一种特殊情况，又称为试探法，常用于需要记录节点状态的深度优先搜索。通常来说，排列、组合、选择类问题使用回溯法比较方便。

回溯法的核心是回溯。在搜索到某一节点的时候，如果我们发现目前的节点（及其子节点）并不是需求目标时，我们回退到原来的节点继续搜索，并且把在目前节点修改的状态还原。这样的好处是我们可以始终只对图的总状态进行修改，而非每次遍历时新建一个图来储存状态。

在具体的写法上，它与普通的深度优先搜索一样，都有 [修改当前节点状态]→[递归子节点] 的步骤，只是多了回溯的步骤，变成了 [修改当前节点状态]→[递归子节点]→[回改当前节点状态]。

回溯法修改一般有两种情况，一种是修改最后一位输出，比如排列组合；一种是修改访问标记，比如矩阵里搜字符串。回溯法的两个小诀窍：一是按引用传状态，二是所有的状态修改在递归完成后回改。

以全排列的顺序访问$n$个元素的数组nums的写法：

def solve(nums):
    n = len(nums)
    # 状态记录
    visited = set()

    def backtrack():
        if len(state) == n:
            # state所指向的列表在深度优先遍历的过程中只有一份
            # 在进行值传递的过程中需要做一次拷贝
            res.append(state[:])
            return
        for j in range(n):
            if i not in visited:
                # 修改当前节点状态
                visited.add(j)
                state.append(nums[j])
                # 递归子节点
                backtrack()
                # 回改当前节点状态
                visited.remove(j)
                state.pop()
                
    for i in range(n):
        # 设置初始状态，这一步也可以合并到递归函数中
        state = [nums[i]]
        visited.add(i)
        backtrack()
        visited.remove(i)

此外，也可以通过itertools库直接实现数组的排列与组合：

itertools.permutations(alist)
itertools.combinations(alist, k)

(3) 广度优先搜索

广度优先搜索（breadth-first search，BFS）不同于深度优先搜索，它是一层层进行遍历的，因此需要用先入先出的队列进行遍历。由于是按层次进行遍历，广度优先搜索时按照“广”的方向进行遍历，也常常用来处理最短路径等问题。

深度优先搜索和广度优先搜索都可以处理可达性问题，即从一个节点开始是否能达到另一个节点。因为深度优先搜索可以利用递归快速实现，很多人会习惯使用深度优先搜索刷此类题目。实际软件工程中很少见到递归的写法，因为一方面难以理解，另一方面可能产生栈溢出的情况；而用栈实现的深度优先搜索和用队列实现的广度优先搜索在写法上并没有太大差异，因此使用哪一种搜索方式需要根据实际的功能需求来判断。

在最短路问题中，如果要求多个源点出发的最短路时，一般我们都会建立一个「超级源点」连向所有的源点，用「超级源点」到终点的最短路等价多个源点到终点的最短路。

一般地，使用BFS遍历$m \times n$的$0/1$二维数组中所有值为$1$的连通域的写法如下：

def solve(matrix):
    m, n = len(matrix), len(matrix[0])
    # 建立队列
    from collections import deque
    queue = deque([])
    # 状态记录
    visited = set()

    for i in range(m):
        for j in range(n):
            if (i,j) not in visited and grid[x][y]==1:
                queue.append((i,j))
                while queue:
                    x, y = queue.popleft()
                    if x<0 or x>=m or y<0 or y>=n or (x,y) in visited:
                        continue
                    visited.add((x,y))
                    for (dx, dy) in [(-1,0), (1,0), (0,-1), (0,1)]:
                        queue.append((x+dx, y+dy))

⚪ 动态规划

动态规划（Dynamic Programming, DP）是将原问题拆成多个重叠子问题进行求解。为了避免重复求解子问题，动态规划保存子问题的解，避免重复计算。动态规划只能应用于有最优子结构的问题，即局部最优解能决定全局最优解。

解决动态规划问题的关键是找到状态转移方程，以便于通过计算和储存子问题的解来求解最终问题。同时也可以对动态规划进行空间压缩，起到节省空间消耗的效果；一种常用的空间压缩方法是滚动数组，相比于直接存储所有的$n$个状态，若状态转移方程中当前状态只与前面$k<n$个状态有关，则只使用$k$个变量来存储之前的状态。

动态规划可以看成是带有状态记录（memoization）的优先搜索。状态记录是指如果一个子问题在优先搜索时已经计算过一次，则可以把它的结果储存下来，之后遍历到该子问题时直接返回储存的结果。

动态规划是自下而上的，即先解决子问题，再解决父问题；而带有状态记录的优先搜索是自上而下的，即从父问题搜索到子问题，若重复搜索到同一个子问题则进行状态记录，防止重复计算。

如果题目需求的是最终状态，那么使用动态规划比较方便；如果题目需要输出所有的路径，那么使用带有状态记录的优先搜索会比较方便。

一般地，动态规划的求解思路：

1. 状态定义： $dp[i]$
2. 列出转移方程： $dp[i+1] = f(dp[i],dp[i-1],…)$
3. 给定边界条件： $dp[0]$
4. 返回结果： $dp[n]$

(1) 一维动态规划

以斐波那契数列$f(n)=f(n-1)+f(n-2)$为例，1D DP的写法如下

 def dp1D(n):
     p0, p1 = 0, 1
     for i in range(2, n+1):
         p2 = p0 + p1
         p0, p1 = p1, p2
     return p1

(2) 二维动态规划

(3) 分割问题

对于分割类型的问题，动态规划的状态转移方程通常并不依赖相邻的位置，而是依赖于满足分割条件的位置。

对于分割问题，当遍历到某个状态$i$时，往往需要考虑状态$i$之前的所有状态$j<i$，并对其中满足分割条件的状态进行计算；总时间复杂度一般为$O(N^2)$。

def seg(alist):
    n = len(alist)
    dp = [0]*(n+1)
    dp[1] = init
    for i in range(2, n+1):
        for j in range(1, i):
            if cond(alist[i], alist[j]):
                dp[i] = f(dp[j])

(4) 并行状态问题

并行状态问题是指在定义状态时同时定义多个并行的状态，在每一时刻更新每个状态时，需同时考虑上一时刻的所有状态。

(5) 背包问题

背包问题 (knapsack problem)是一种组合优化的NP-Complete问题：有 $N$ 个物品和容量为 $W$ 的背包，每个物品都有自己的体积 $w$ 和价值 $v$，求拿哪些物品可以使得背包所装下物品的总价值最大。

如果限定每种物品只能选择 $0$ 个或 $1$ 个，则问题称为0-1背包问题；如果不限定每种物品的数量，则问题称为无界背包问题或完全背包问题。

可以用动态规划来解决背包问题。把物品的迭代放在外层，里层对体积或价值进行遍历。（空间压缩后）0-1背包对里层的体积或价值逆向遍历；完全背包对里层的体积或价值正向遍历。

⚪ 0-1背包问题

对于0-1背包，可以定义一个二维数组 $dp$ 存储最大价值，其中 $dp[i][j]$ 表示前 $i$ 件物品体积不超过 $j$ 的情况下能达到的最大价值。

在遍历到第 $i$ 件物品时，在当前背包总容量为 $j$ 的情况下，如果我们不将物品 $i$ 放入背包，那么 $dp[i][j]= dp[i-1][j]$，即前 $i$ 个物品的最大价值等于只取前 $i-1$ 个物品时的最大价值；如果我们将物品 $i$ 放入背包，假设第 $i$ 件物品体积为 $w_i$，价值为 $v_i$，那么我们得到 $dp[i][j] = dp[i-1][j-w_i] + v_i$。只需在遍历过程中对这两种情况取最大值即可，总时间复杂度和空间复杂度都为 $O(NW)$。

def knapsack(weights, values, N, W):
    dp = [[0]*(W+1) for _ in range(N+1)]
    for i in range(1, N+1):
        w, v = weights[i-1], values[i-1]
        for j in range(W+1):
            if j >= w:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w]+v)
            else:
                dp[i][j] = dp[i-1][j]
    return dp[N][W]

我们可以进一步对0-1背包进行空间优化，将空间复杂度降低为 $O(W)$。如图所示，假设我们目前考虑物品 $i = 2$，且其体积为 $w = 2$，价值为 $v = 3$；对于背包容量 $j$，我们可以得到 $dp[2][j]= \max(dp[1][j], dp[1][j-2] + 3)$。这里可以发现我们永远只依赖于上一排 $i = 1$ 的信息，之前算过的其他物品($i<1$)都不需要再使用。因此我们可以去掉 $dp$ 矩阵的第一个维度，在考虑物品 $i$ 时变成 $dp[j]= \max(dp[j], dp[j-w] + v)$。

这里要注意我们在遍历每一行的时候必须逆向遍历，这样才能够调用上一行物品 $i-1$ 时 $dp[j-w]$ 的值；若按照从左往右的顺序进行正向遍历，则 $dp[j-w]$ 的值在遍历到 $j$ 之前就已经被更新成物品 $i$ 的值了。

def knapsack(weights, values, N, W):
    dp = [0]*(W+1)
    for i in range(N):
        w, v = weights[i], values[i]
        for j in range(W, w-1, -1):
            dp[j] = max(dp[j], dp[j-w]+v)
    return dp[W]

⚪ 完全背包问题

在完全背包问题中，一个物品可以拿多次。如图所示，假设我们遍历到物品 $i = 2$，且其体积为 $w = 2$，价值为 $v = 3$；对于背包容量 $j = 5$，最多只能装下 $2$ 个该物品。那么我们的状态转移方程就变成了 $dp[2][5] = max(dp[1][5], dp[1][3] + 3, dp[1][1] + 6)$。如果采用这种方法，假设背包容量无穷大而物体的体积无穷小，则比较次数也会趋近于无穷大，远超 $O(NW)$ 的时间复杂度。

怎么解决这个问题呢？我们发现在 $dp[2][3]$ 的时候其实已经考虑了 $dp[1][3]$ 和 $dp[2][1]$ 的情况，而在 $dp[2][1]$ 时也已经考虑了 $dp[1][1]$ 的情况。因此，如图所示，对于拿多个物品的情况，我们只需考虑 $dp[2][3]$ 即可，即 $dp[2][5] = max(dp[1][5], dp[2][3] + 3)$。

这样，我们就得到了完全背包问题的状态转移方程：$dp[i][j] = \max(dp[i-1][j], dp[i][j-w_i] + v_i)$，其与 0-1 背包问题的差别仅仅是把状态转移方程中的第二个 $i-1$ 变成了 $i$。

def knapsack(weights, values, N, W):
    dp = [[0]*(W+1) for _ in range(N+1)]
    for i in range(1, N+1):
        w, v = weights[i-1], values[i-1]
        for j in range(W+1):
            if j >= w:
                dp[i][j] = max(dp[i-1][j], dp[i][j-w]+v)
            else:
                dp[i][j] = dp[i-1][j]
    return dp[N][W]

同样的，我们也可以利用空间压缩将空间复杂度降低为 $O(W)$，去掉 $dp$ 矩阵的第一个维度，在考虑物品 $i$ 时变成 $dp[j]= \max(dp[j], dp[j-w] + v)$。这里要注意在遍历每一行的时候必须正向遍历，因为我们需要利用当前物品 $i$ 在第 $j-w$ 列的信息。

def knapsack(weights, values, N, W):
    dp = [0]*(W+1)
    for i in range(N):
        w, v = weights[i], values[i]
        for j in range(w, W+1):
            dp[j] = max(dp[j], dp[j-w]+v)
    return dp[W]

(6) 股票问题

股票交易类问题通常可以用动态规划来解决。对于稍微复杂一些的股票交易类问题，比如需要冷却时间或者交易费用，则可以用通过动态规划实现的状态机来解决。

状态机的思想在于列举出所有可能的「状态」，然后穷举更新这些「状态」。具体到每一天，看看总共有几种可能的「状态」，再找出每个「状态」对应的「选择」。我们要穷举所有「状态」，穷举的目的是根据对应的「选择」更新状态。

for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for ...
            dp[状态1][状态2][...] = 择优(选择1，选择2...)

股票类型的通用题目形式为给定一支股票每天的价格$prices$，并限制最大交易次数为$K$，计算能够获得的最大利润。这个问题的「状态」有三个，第一个是天数，第二个是当前的交易次数，第三个是当前的持有状态（rest，用 1 表示持有，0 表示没有持有）。每天都有三种「选择」：买入（buy）、卖出（sell）、无操作（rest）。可以用三维数组存储该问题的三种状态：

dp[i][k][0 or 1]
0 <= i <= n, 0 <= k <= K

for 1 <= i <= n:
    for 1 <= k <= K:
        for s in {0, 1}:
            dp[i][k][s] = max(buy, sell, rest)

股票问题的最终答案是$dp[n][K][0]$，即最后一天，最多进行 $K$ 次交易，最多获得多少利润。注意答案不应是$dp[n][K][1]$，因为最后手上还持有股票得到的利润一定小于手上的股票卖出得到的利润。

根据「状态」的定义可以画出状态转移图，对应一个有限状态机：

并进一步写出状态转移方程：

dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i-1])

解释：今天我没有持有股票，有两种可能：
要么是我昨天就没有持有，然后今天选择 rest，所以我今天还是没有持有；
要么是我昨天持有股票，但是今天我 sell 了，所以我今天没有持有股票了。

dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i-1])

解释：今天我持有着股票，有两种可能：
要么我昨天就持有着股票，然后今天选择 rest，所以我今天还持有着股票；
要么我昨天本没有持有，但今天我选择 buy，所以今天我就持有股票了。

还需要定义状态机的初始条件：

dp[0][k][0] = 0
解释：因为 i 是从 1 开始的，所以 i = 0 意味着还没有开始，这时候的利润当然是 0 。
dp[0][k][1] = -infinity
解释：还没开始的时候，是不可能持有股票的，用负无穷表示这种不可能。
dp[i][0][0] = 0
解释：因为 k 是从 1 开始的，所以 k = 0 意味着根本不允许交易，这时候利润当然是 0 。
dp[i][0][1] = -infinity
解释：不允许交易的情况下，是不可能持有股票的，用负无穷表示这种不可能。

(6) 树形动态规划问题

树形动态规划是指在树上进行的动态规划。因为树固有的递归属性，所以树形动态规划一般都是递归进行的。

判断一个问题是否为树形动态规划问题，首先判断是否是一个树，然后是否符合动态规划要求，也就是去判断父节点和子节点是否存在阶段性的关联关系。通常树形DP的写法有两种：

• 根到叶子: 首先在根节点上进行计算，再将结果传递给子节点。这种动态规划在实际的问题中运用的不多。
• 叶子到根: 根的子节点传递有用的信息给根，然后从根得出最优解的过程。这类的习题比较多。

树形DP的伪代码如下：

def dfs(root):
    # 递归处理root的每一个节点son
    dfs(root.son)
    # 根据转移方程动态更新

(6) 子集枚举问题

如果一个问题中状态的本征维度比较低（比如$n=15$，最多存在$2^{15}=32768$个状态），则可以考虑在构造状态转移方程时枚举所有状态。

在遍历状态时可以通过二进制的子集枚举实现。对于一个有 $k$ 个 $1$ 的二进制表示的正整数 $x$，其非空子集(至少包含一个$1$)有 $2^k - 1$ 个。此时枚举子集的时间复杂度为 $O(2^k)$。子集枚举可以通过位运算实现：

for s in range(1 << k):
    # s表示当前时刻可以取到的所有状态的集合，取值为 [0, 2^k-1]

    # 例①：枚举s的所有非空子集：
    sub = s
    while sub:
        # 处理状态sub
        sub = (sub - 1) & s

    # 例②：

⚪ 分治法

分治问题由“分”（divide）和“治”（conquer）两部分组成，通过把原问题分为子问题，再将子问题进行处理合并，从而实现对原问题的求解。

可以使用数学表达式来表示分治过程。定义 $T(n)$ 表示处理一个长度为 $n$ 的数组的时间复杂度，则分治法的时间复杂度递推公式为 $T(n) = 2T(n/2) + O(n)$。其中 $2T(n/2)$ 表示我们分成了两个长度减半的子问题，$O(n)$ 则为合并两个长度为 $n/2$ 数组的时间复杂度。

可以利用主定理（Master theorem）求解最终的时间复杂度：考虑$T(n) = aT(n/b) + f(n)$，定义 $k=\log_b a$：

1. 如果 $f(n)=O(n^p)$ 且 $p<k$，那么 $T(n)=O(n^k)$；
2. 如果存在 $c\geq 0$ 满足 $f(n)=O(n^k \log^c n)$，那么 $T(n)=O(n^k \log^{c+1} n)$；
3. 如果 $f(n)=O(n^p)$ 且 $p>k$，那么 $T(n)=O(f(n))$。

分治问题可以通过主定理求得时间复杂度。如上文定义的递推公式$T(n) = 2T(n/2) + O(n)$的时间复杂度为$O(n \log n)$。

以归并排序算法为例，分治法的一般写法如下：

def divide(alist):
    if len(alist) <= 1:
        return alist
    num = len(alist)//2
    left = divide(alist[0:num])
    right = divide(alist[num:])
    return conquer(left, right)
	
def conquer(left, right):
    result = []
    l, r = 0, 0
    while l<len(left) and r<len(right):
        if left[l] <= right[r]:
            result.append(left[l])
            l += 1
        else:
            result.append(right[r])
            r += 1
    result += left[l:]  # 切片超界会返回空列表
    result += right[r:]
    return result

⚪ 位运算

位运算是算法题里比较特殊的一种类型，它们利用二进制位运算的特性进行一些奇妙的优化和计算。

Python实现整型与二进制之间的转换：

# 整型 -> 二进制
b = bin(n) # 返回一个整数n的以'0b'开始的二进制表示形式的字符串。
b = '{0:b}'.format(n) # 返回一个整数n的二进制表示形式的字符串。

# 二进制 -> 整型
n = int(b, 2) # 把二进制字符串转换为整型

常用的位运算符号包括：

"""
& 按位与    | 按位或   ^ 按位异或 ~ 按位取反
<< 按位左移：相当于乘以2，运算优先级较低
>> 按位右移：相当于整除2，运算优先级较低
"""

以下是一些常见的位运算特性，其中 0s 和 1s 分别表示只由 0 或 1 构成的二进制数字。

x ^ 0s = x    x & 0s = 0    x | 0s = x
x ^ 1s = ~x   x & 1s = x    x | 1s = 1s
x ^ x = 0     x & x = x     x | x = x

下面是一些位运算的技巧：

• n & 1：可以取出 n 的最后一位。
• n & (n+1)：可以判断 n 的二进制表示是否全为 1。
• n & (n-1)：可以去除 n 的位级表示中为1的最低的那一位，例如对于二进制表示 11110100，减去 1 得到 11110011，这两个数按位与得到 11110000。
• n & (-n)：可以得到 n 的位级表示中1的最低的那一位，例如对于二进制表示 11110100，取负得到 00001100（负数以补码的形式表示，最高位即符号位，剩下的位按位取反，末位加1），这两个数按位与得到 00000100。
• n.bit_count()：统计n在二进制表示中位为$1$的数量

⚪ 数学问题

（1）模拟求和

模拟求和问题通常会涉及到进位以及位数差的处理。

（2）数论

利用辗转相除法，我们可以很方便地求得两个数的最大公因数（greatest common divisor，gcd）；将两个数相乘再除以最大公因数即可得到最小公倍数（least common multiple, lcm）。

def gcd(a, b):
    return a if b == 0 else gcd(b, a%b)

def lcm(a, b):
    return a * b / gcd(a, b)

（3）几何

（4）随机采样

# 从$[0, 1)$中随机采样一个浮点数数
p = random.random()

# 从$[1, n)$中随机采样一个整数
i = random.randrange(1, n, step=1)

# 随机打乱一个数组：
random.shuffle(alist)

（5）脑筋急转弯

二、数据结构篇

数据结构可以用来实现各种算法，因此必须熟悉各种数据结构的特点。

⚪ 字符串

字符串是由字符组成的数组。由于字符串是程序里经常需要处理的数据类型，因此有很多针对字符串处理的题目。

有时需要进行字符的数值运算，可以通过ord()函数把它们转换成ASCII码后再计算：

ord('z') - ord('a') # 25

（1）字符串理解

字符串理解是指按要求处理给定的单个字符串。

寻找字符串中的回文子串通常采用中心扩展算法，枚举所有的「回文中心」（字符串的每个位置），并尝试「扩展」（向左向右延长），直到无法扩展为止（不再满足回文条件）。需要注意回文串长度有奇数和偶数两种情况，需要分开讨论。

n = len(s)
for i in range(n):

   # 奇数情况
   l, r = i-1, i+1
   while l>=0 and r<n:
       if s[l] == s[r]:
           l -= 1
           r += 1
       else:
           break
   # s[l+1:r]是一个长度为r-l-1的回文子串

   # 偶数情况
   l, r = i-1, i
   while l>=0 and r<n:
       if s[l] == s[r]:
           l -= 1
           r += 1
       else:
           break
   # s[l+1:r]是一个长度为r-l-1的回文子串

（2）字符串比较

字符串比较是指按要求比较给定的两个或多个字符串。

⚪ 基本数据结构

（1）数组 array

数组是最常用的数据结构之一，在python中体现为列表list。

（2）栈和队列 Stack and Queue

栈是一种后入先出（last in first out, LIFO）的数据结构，常用于深度优先搜索、一些字符串匹配问题以及单调栈问题。队列是一种先入先出（first in first out, FIFO）的数据结构，常用于广度优先搜索。

栈和队列在python中都可以用列表list实现；为了实现$O(1)$的头部增删和尾部增删，默认基于双端队列collections.deque实现。

from collections import deque

stack = deque([])
stack.append()
stack.pop()

queue = deque([])
queue.append()
queue.popleft()

（3）单调栈

单调栈通过维持栈内值的单调递增（递减）性，在整体 $O(n)$ 的时间内处理需要大小比较的问题。

单调栈经常被用于寻找数组中当前位置对应的下一个更大/小值，此时可以维护一个存储下标的单调递减/递增栈。以寻找更大值为例，维持一个存储下标的单调递减栈，每次有下标进栈时，会将对应数值更小的下标全部出栈，并更新这些下标对应的下一个更大值；同时，栈顶元素也记录了该下标对应的上一个更大值(或相等值)：

stack = []
for i in range(n):
   while stack and nums[stack[-1]] < nums[i]:
       idx = stack.pop()
       nextMaxVal[idx] = nums[i]
       prevMaxVal[idx] = stack[-1]
   stack.append(i)

（4）优先队列（堆）

优先队列 (priority queue) 是一种最大值（或最小值）先出的数据结构。它可以在$O(n \log n)$的时间排序数组，$O(1)$的时间获得最大值，$O(\log n)$的时间插入任意值或删除最大值。优先队列常用于维护数据结构并快速获取最大或最小值。

优先队列是通过堆（queue）这种数据结构实现的。python中的heapq库提供了优先队列的基本操作，相当于最小堆：

import heapq
queue = []

# 注意 Python 默认的优先队列是最小堆
heapq.heappush(queue, elem) # 添加元素
minVal = heapq.heappop(queue) # 弹出最小元素

queue.remove(elem) # 删除任意元素
heapq.heapify(queue) # 删除后要恢复堆的性质

（5）哈希表（字典和集合）

哈希表 (hash)又称散列表，使用 $O(n)$ 空间复杂度存储数据，通过哈希函数映射位置，从而实现近似 $O(1)$ 时间复杂度的插入、查找、删除等操作。

python提供了字典dict和集合set数据结构作为哈希表，可以用来统计频率，记录内容等等。有时需要为不存在的键设置默认值，也可以用collections.defaultdict实现。

from collections import defaultdict
dd = defaultdict(lambda: 0) # 设置value的默认值为0

⚪ 基于指针的数据结构

（1）链表

（单）链表是由节点和指针构成的数据结构，每个节点存有一个值，和一个指向下一个节点的指针。

不同于数组，链表并不能直接获取任意节点的值，必须要通过指针找到该节点后才能获取其值。同理，在未遍历到链表结尾时，我们也无法知道链表的长度，除非依赖其他数据结构储存长度。LeetCode 默认的链表表示方法如下。

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

由于在进行链表操作时，尤其是删除节点时，经常会因为对当前节点进行操作而导致内存或指针出现问题。有两个小技巧可以解决这个问题：一是尽量处理当前节点的下一个节点而非当前节点本身，二是建立一个哑节点 (dummy node)，使其指向当前链表的头节点，这样即使原链表所有节点全被删除，也会有一个 dummy 存在，返回 dummy.next 即可。

建立哑节点：

dummy = ListNode(0)
dummy.next = head
# 处理链表
return dummy.next

很多链表问题可以用递归来处理，比如递归提供了一种优雅的方式来反向遍历节点。

def reverse_node(head):
    if not head:
        return
    reverse_node(head.next)
    return head.val

值得一提的是，在许多语言中，递归堆栈帧的开销很大（如 Python），并且最大的运行时堆栈深度为 $1000$（可以增加，但是有可能导致底层解释程序内存出错）。为每个节点创建堆栈帧极大的限制了算法能够处理的最大链表大小。

（2）树

树是单链表的升级版，如无特别说明，本文主要讨论二叉树（binary tree），即每个节点最多有两个子节点；其与链表的主要差别就是多了一个子节点的指针。LeetCode 默认的树表示方法如下。

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

⚪ 树的递归

树的递归是指首先处理以当前节点为根节点的树，再递归地处理左右子树；其写法与深度优先搜索的递归写法相同。

⚪ 树的前序遍历、中序遍历和后序遍历（深度优先搜索）

利用深度优先搜索遍历二叉树的方式有三种：前序遍历、中序遍历和后序遍历。它们对节点访问的顺序有一点不同，其它完全相同。

# 前序遍历先遍历根结点，再遍历左结点，最后遍历右节点
def preorder(root):
    print(root.val)
    preorder(root.left)
    preorder(root.right)
# 对于任意一颗树而言，前序遍历的形式总是
# [ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]

# 中序遍历先遍历左节点，再遍历根结点，最后遍历右节点
def inorder(root):
    inorder(root.left)
    print(root.val)
    inorder(root.right)
# 对于任意一颗树而言，中序遍历的形式总是
# [ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]

# 后序遍历先遍历左节点，再遍历右结点，最后遍历根节点
def postorder(root):
    postorder(root.left)
    postorder(root.right)
    print(root.val)
# 对于任意一颗树而言，后序遍历的形式总是
# [ [左子树的中序遍历结果], [右子树的中序遍历结果], 根节点 ]

⚪ 树的层次遍历（广度优先搜索）

可以使用广度优先搜索进行层次遍历。注意，不需要使用两个队列来分别存储当前层的节点和下一层的节点，因为在开始遍历一层的节点时，当前队列中的节点数就是当前层的节点数，只要控制遍历这么多节点数，就能保证这次遍历的都是当前层的节点。

from collections import deque
q = deque([root])
while q:
    n = len(q)
    # 处理该层的n个节点
    for i in range(n):
        node = q.popleft()
        q.append(node.left)
        q.append(node.right)

⚪ 二叉查找树

二叉查找树（Binary Search Tree, BST）又称为二叉搜索树，是一种特殊的二叉树：对于每个父节点，其左子节点的值小于等于父结点的值，其右子节点的值大于等于父结点的值。同时因为二叉查找树是有序的，对其中序遍历的结果即为排好序的数组。

因此对于一个二叉查找树，可以在 $O(n \log n)$ 的时间内查找一个值是否存在：从根节点开始，若当前节点的值大于查找值则向左下走，若当前节点的值小于查找值则向右下走。比如寻找二叉查找树中的最小元素对应的节点：

minNode = root
while minNode.left:
    minNode = minNode.left

（3）图

图是树的升级版。图通常分为有向（directed）或无向（undirected），有循环（cyclic）或无循环（acyclic），所有节点相连（connected）或不相连（disconnected）。树即是一个相连的无向无环图，而另一种很常见的图是有向无环图（Directed Acyclic Graph，DAG）。

图通常有两种表示方法。假设图中一共有 $n$ 个节点、$m$ 条边。第一种表示方法是邻接矩阵（adjacency matrix）：我们可以建立一个 $n× n$ 的矩阵 $G$，如果第 $i$ 个节点连向第 $j$ 个节点，则 $G[i][j]= 1$，反之为 $0$；如果图是无向的，则这个矩阵一定是对称矩阵，即 $G[i][j] = G[j][i]$。

第二种表示方法是邻接链表（adjacency list）：我们可以建立一个大小为 $n$ 的数组，每个位置 $i$ 储存一个数组或者链表，表示第 $i$ 个节点连向的其它节点。

邻接矩阵空间开销比邻接链表大，但是邻接链表不支持快速查找 $i$ 和 $j$ 是否相连，因此两种表示方法可以根据题目需要适当选择。除此之外，我们也可以直接用一个 $m × 2$ 的矩阵储存所有的边。

# 构建无向图的邻接矩阵
graph = [[0]*n for _ in range(n)]
for a, b in edges:
    graph[a][b] = 1
    graph[b][a] = 1

# 构建无向图的邻接链表，适用于元素较多的场合
graph = [[] for _ in range(n)]
for a, b in edges:
    graph[a].append(b)
    graph[b].append(a)

⚪ 其他数据结构

（1）前缀和与积分图

一维的前缀和（prefix sum），二维的积分图（integral image），都是把每个位置之前的一维线段或二维矩形预先存储，方便加速计算。

如果需要对前缀和或积分图的值做寻址，则要存在哈希表里；如果要对每个位置记录前缀和或积分图的值，则可以储存到一维或二维数组里，可以通过动态规划实现。

下面是构造一维前缀和的例子。需要注意前缀和索引$i$的含义是数组前$i$项的和，从前$0$个和到前$n$个和，则数组总的长度是$n+1$。

# 写法①
sums = [0]
for num in nums:
    sums.append(sums[-1] + num)

# 写法②
sums = list(accumulate(num))

下面是构造二维积分图的例子。

sums = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
   for j in range(1, n+1):
       sums[i][j] = sums[i][j-1]+sums[i-1][j]-sums[i-1][j-1]+nums[i-1][j-1]

（2）并查集

并查集（union-find）是一种树型的数据结构，用于处理一些不相交集合（disjoint sets）的合并及查询问题。

假设存在 $n$ 个节点，我们先将所有节点的父亲标为自己；每次要连接节点 $i$ 和 $j$ 时，可以将 $i$ 的父亲标为 $j$；每次要查询两个节点是否相连时，可以查找 $i$ 和 $j$ 的祖先是否最终为同一个人。

并查集维护一个数组parent，数组中维护的是元素的下标索引，这个下标索引指向该元素的父元素。并查集主要有三个功能：

1. 寻找根节点：find(u)，也就是判断节点$u$的祖先节点是哪个节点；
2. 将两个节点接入到同一个集合：union(u, v)，将两个节点$u,v$连在同一个根节点上；
3. 判断两个节点是否在同一个集合：same(u, v)，就是判断两个节点是不是属于同一个根节点。

# 并查集初始化
parent = list(range(n))

# 并查集里寻根
def find(u):
    return u if parent[u] == u else find(parent[u])

# 将 v->u 这条边加入并查集
def union(u, v):
    u, v = find(u), find(v)
    if u == v:
        return
    parent[v] = u

# 判断 u 和 v 是否属于同一个根
def same(u, v):
    return find(u) == find(v) # 注意是find不是parent！！

为了加速查找，我们可以使用路径压缩和按秩合并来优化并查集：

• 按秩合并：秩定义为节点的最大深度。在执行union(u, v)时，将秩大的根节点设置为合并后的根节点，避免了树的深度增加（避免后续的节点查询时间长）。
• 路径压缩：在执行find(u)时，当在寻找一个节点的根节点root时，直接将该节点的所有长辈节点全部指向根节点root。后续寻找这些节点的根节点时可以节省很长一段搜索路径。

parent = list(range(n))
rank = [1]*n # 记录每个节点的秩

def find(u):
    # 路径压缩
    if u != parent[u]:
        parent[u] = find(parent[u])
    return parent[u]

def union(u, v):
    u, v = find(u), find(v)
    if u == v:
        return
    # 按秩合并
    if rank[u] < rank[v]:
        parent[u] = v
    elif rank[u] > rank[v]:
        parent[v] = u
    else:
        parent[v] = u
        rank[u] += 1

并查集通常被用于判断节点的连通性问题。

（3）设计数据结构

在设计复合类型的数据结构时，可以通过列表进行数据存储，从而加速连续选址或删除值；也可以通过哈希字典进行辅助记录或加速寻址。