基础算法精讲笔记

0.Python笔记

collection库

Counter

dict的子类（python的字典是优化的hashmap）

from collections import Counter

cnt = Counter()
cnt['a'] += 1 # 与dict不同之处

Defaultdict

dict的子类

from collections import defaultdict

dic = defaultdict(list) # 创建默认值为列表的字典

deque

队列数据结构，先进先出

from collections import deque

q = deque()
q.append(root)
node = q.popleft()

时空复杂度

循环里切片很费时间

复制的时间不能忽略

排序的时间复杂度：O(nlogn)

哈希的时间复杂度：O(1)

语法

• is：比较是否同一对象，即相同内存地址

  ==：比较值是否相等

• global：全局变量。要修改就要声明，否则不用

  nonlocal：上一层函数中的局部变量

• all()函数：全真为真，一假为假

  any()函数：一真为真，全假为假

• 创建一个m*n的二维列表

  f = [[0]*(n) for _ in range(m)] #正确
  f = [[0]*(n)]*(m) # 错误，里面的所有列表地址相同，改一个其他会跟着变

技巧

1. 多使用目标数去累减，而不是生成的数累加再与目标数比较

其他笔记

GPU分支（if-else）：多个线程串行执行，会出现线程空跑

CPU分支（if-else）：分支预测，判断条件的同时提前准备后续指令

bank conflict：在访问shared memory时，多个线程同时读写同一个bank中的不同数据地址时导致shared memory并发读写 退化 成顺序读写的现象

1.相向双指针

使用场景

两数之和、三数之和（或最接近）

解题思路

利用有序性，用O(1)的时间获得O(n)的信息

两边都是，动了之后就不要复位了

2.滑动窗口（同向双指针）

使用场景

1.统计次数

2.求子串

3.子数组越长越能满足要求

解题思路

维护一个有条件的滑动窗口

右移：扩大窗口，目的是破坏条件

左移：缩小窗口，目的是重新满足条件

3.二分查找（红蓝染色法）

使用场景

1.有单调性，可以二分答案：最小化最大值、最大化最小值。如果k=4可以那k=5,6…也可以，并且如果k=3不可以那k=2,1…也不可以。

2.峰值搜索、循环排序数组

时间复杂度：O(logn)

循环不变量：

check[left]==false && check[right]==true # 求最小
check[left]==true && check[right]==false # 求最大

解题思路

1.定义红为不满足要求（或目标左侧），蓝为满足要求（或目标及其右侧）

2.初始化指针区间：看有哪些元素可以被染成红/蓝色

3.判断条件：是否为红/蓝色，是则移动对应侧的指针

4.返回指针：蓝色

代码示例

注意开区间闭区间的问题

整数数组可以总结为4种类型：

1. ≥x：最基础的写法lower_bound
2. ＞x：转换成(≥x+1)
3. ＜x：转换成(≥x)-1
4. ≤x：转换成(＞x)-1 = (≥x+1)-1

# 手写二分
def lower_bound(nums, target):
        left, right = -1, len(nums)  # 开区间 (left, right)
        while left + 1 < right:  # 区间不为空
            mid = (left + right) // 2
            # 循环不变量：
            # nums[left] < target
            # nums[right] >= target
            if nums[mid] >= target:
                right = mid  # 范围缩小到 (left, mid)
            else:
                left = mid  # 范围缩小到 (mid, right)
        # 循环结束后 left+1 = right
        # 此时 nums[left] < target 而 nums[right] >= target
        # 所以 right 就是第一个 >= target 的元素下标
        return right

# 库函数
from bisect import bisect_left,bisect_right
index1 = bisect_left(nums,8) # 返回大于等于8的第一个索引
index2 = bisect_right(nums,8) # 返回大于8的第一个索引
index3 = bisect_right(nums,8,0,n) # 在[0,n-1]的区间二分

4.链表

原：pre指向空，cur指向头节点，nxt指向cur.next

反转后：pre指向尾节点，cur指向空

注意

dummy = ListNode(next=head)
p0 = dummy

此时p0和dummy只是指针，指向的是同一个链表节点对象。当修改p0.next时dummy.next也会改变，直至p0被指向其他对象

什么时候需要dummy node：对头节点进行操作时

删除链表节点时，每次循环只需执行一步操作：删除或移动指针

解题思路

1.先考虑是否需要使用哨兵节点

2.是否能使用技巧：反转链表、快慢指针（找中间节点、环形链表）

3.考虑递归还是迭代

代码示例

反转链表

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        dummy = ListNode(next=head) # 哨兵节点
        p0 = dummy
        for _ in range(left-1):
            p0 = p0.next
        pre = None
        cur = p0.next
        for _ in range(right-left+1):
            nxt = cur.next
            cur.next = pre
            pre = cur
            cur = nxt
        p0.next.next = cur
        p0.next = pre
        return dummy.next

5.二叉树

DFS深度优先搜索：栈，递归，时间复杂度O(n)，空间复杂度O(n)

BFS广度优先搜索：队列

1.前序遍历（递）：先访问节点值，再递归左右子树

1.中序遍历：左中右（例：大于上一个节点）

1.后序遍历（归）：前递归左右子树，再访问节点值

递归

1.看整体：根节点与左右子树。左右子树为子问题

注意：不要想递归是怎么一层一层走的，去思考代码的边界条件和非边界条件的逻辑

2.父子之间传递信息分类：自底向上、自顶向下（维护一个全局变量）

公共祖先：

分类讨论

6.回溯

相当于暴力解法。有一个增量构造答案的过程，通常用递归实现：构造搜索树，用dfs遍历这棵树

恢复现场：在哪个递归中 push，就在哪个递归中 pop。“自己做的事自己解决”

什么时候不需要恢复现场：所有答案长度固定为n，且初始化path长度也为n，会覆盖

回溯三问

1.当前问题：枚举path[i]要填入的字母

2.子问题：构造字符串≥i的部分

3.下一个子问题：构造字符串≥i+1的部分

分类

1.子集型回溯

从输入视角：每次枚举第i个数选或不选（叶子节点才是答案）

从答案视角：每次必须枚举一个（每个节点都是答案），或者枚举子串结束的位置

时间复杂度：一般而言，每次枚举的数组长度为a共递归a^n次，最后每次path加入答案（复制）花费O(n)，总共O(n*a^n)

2.组合型回溯

从n个数选k个数的组合：可以看作长度固定的子集，在子集型基础上加判断条件（剪枝）

时间复杂度：剪枝后叶子个数C(k,n)乘上从根到叶子的路径长度k（即copy时间） kC_n^k 剪枝技巧

3.排列型回溯

全排列

时间复杂度：若跟组合型一样O(n*n!)的话，根节点会统计很多次

更精确：算节点个数

高等数学：该树精确总节点个数 ⌊e * n!⌋ 初等数学：大O记号下不用精确，即O(n*n!)，其中n为copy时间，n!为估计节点个数

7.动态规划

DP萌新三步

回溯+记忆化搜索=>递推

1.思考回溯怎么写（入参和返回值、递归到哪里、递归边界和入口）

2.改成记忆化搜索

3.1:1翻译成递推

自顶向下算：记忆化搜索

将结果作为返回值

有重复的计算结果：@cache装饰器，或cache数组记录返回值

时间复杂度：状态个数*单个状态所需时间

自底向上算：递推

在记忆化搜索的基础上，我们已经知道了哪两个节点会返回值，那可以去掉递的过程只保留归的过程，即递推

1:1翻译：

• dfs -> f数组

• 递归 -> 循环

• 递归边界 -> 数组初始值

0-1背包、完全背包

0-1背包

有n个物品，第i个物品的体积为w[i]，价值为[i]，每个物品至多选一个，求体积和不超过capacity时的最大价值和

# 记忆化搜索
# 时间复杂度O(n*capacity)，空间复杂度O(n*capacity)
def zero_one_knapsack(capacity:int, w:List[int], v: List[int])->int:
    n = len(w)
    @cache
    def dfs(i, c):
        if i < 0:
            return 0
        if c < w[i]:
    		return dfs(i-1，c)
        return max(dfs(i-1,c), dfs(i-1,c-w[i]) + v[i])
    return dfs(n-1,capacity)

# 递推，1:1翻译
# 时间复杂度O(n*capacity)，空间复杂度O(n*capacity)
def zero_one_knapsack(capacity:int, w:List[int], v:List[int]) -> int:
    n=len(w)
    f = [[0]*(capacity+1) for _ in range(n+1)]
    for i,x in enumerate(w):
        for c in range(capacity+1):
            if c < x:
                f[i+1][c] = f[i][c]
            else:
                f[i+1][c] = max(f[i][c], f[i][c-x] + v[i])
    return f[n][capacity]

# 递推，滚动数组
# 时间复杂度O(n*capacity)，空间复杂度O(capacity)
def unbounded_knapsack(capacity:int, w:List[int], v:List[int]) -> int:
    n=len(w)
    f = [[0]*(capacity+1) for _ in range(2)]
    for i,x in enumerate(w):
        for c in range(capacity+1):
            if c < x:
                f[(i+1)%2][c] = f[i%2][c]
            else:
                f[(i+1)%2][c] = max(f[i%2][c], f[i%2][c-x] + v[i])
    return f[n%2][capacity]

# 递推，只用一个数组
# 时间复杂度O(n*capacity)，空间复杂度O(capacity)
def zero_one_knapsack(capacity:int, w:List[int], v:List[int]) -> int:
    n=len(w)
    f = [[0]*(capacity+1) for _ in range(2)]
    for x in w:
        for c in range(capacity, x-1, -1): # 倒序遍历，因为f[i+1][c]的结果来自f[i][c]和f[i][c-x]，前面先算会覆盖掉
            f[c] = max(f[c], f[c-x] + v[i])
    return f[capacity]

完全背包

有n种物品，第i种物品的体积为w[i]，价值为v[i]，每种物品无限次重复选，求体积和不超过capacity时的最大价值和

# 记忆化搜索
# 时间复杂度O(n*capacity)，空间复杂度O(n*capacity)
def unbounded_knapsack(capacity:int, w:List[int], v: List[int]) -> int:
    n=len(w)
    @cache
    def dfs(i, c):
        if i < 0:
        	return 0
        if c < w[i]:
        	return dfs(i-1,c)
        return max(dfs(i-1,c), dfs(i,c-w[i]) + v[i]) # 跟0-1背包唯一的区别就是i-1换成i，表示可以递推到自己
    return dfs(n-1,capacity)

# 递推，1:1翻译
# 时间复杂度O(n*capacity)，空间复杂度O(n*capacity)
def unbounded_knapsack(capacity:int, w:List[int], v:List[int]) -> int:
    n=len(w)
    f = [[0]*(capacity+1) for _ in range(n+1)]
    for i,x in enumerate(w):
        for c in range(capacity+1):
            if c < x:
                f[i+1][c] = f[i][c]
            else:
                f[i+1][c] = max(f[i][c], f[i+1][c-x] + v[i]) # 跟0-1背包的区别：i换成i+1
    return f[n][capacity]

# 递推，滚动数组
# 时间复杂度O(n*capacity)，空间复杂度O(capacity)
def unbounded_knapsack(capacity:int, w:List[int], v:List[int]) -> int:
    n=len(w)
    f = [[0]*(capacity+1) for _ in range(2)]
    for i,x in enumerate(w):
        for c in range(capacity+1):
            if c < x:
                f[(i+1)%2][c] = f[i%2][c]
            else:
                f[(i+1)%2][c] = max(f[i%2][c], f[(i+1)%2][c-x] + v[i]) # 跟0-1背包的区别：i换成i+1
    return f[n%2][capacity]

# 递推，只用一个数组
# 时间复杂度O(n*capacity)，空间复杂度O(capacity)
def unbounded_knapsack(capacity:int, w:List[int], v:List[int]) -> int:
    n=len(w)
    f = [[0]*(capacity+1) for _ in range(2)]
    for x in w:
        for c in range(x, capacity+1): # 跟0-1背包的区别：正序遍历就行。因为f[i+1][c]的结果来自f[i][c]和f[i+1][c-x]，需要先算前面给后面做铺垫
            f[c] = max(f[c], f[c-x] + v[i])
    return f[capacity]

常见变形

1.至多装 capacity，求方案数/最大价值和

2.恰好装 capacity，求方案数/最大/最小价值和

3.至少装 capacity，求方案数/最小价值和

循环顺序

看状态转移方程

例：假设c=3

f[i+1][c] = max(f[i][c], f[i+1][c-x] + v[i])

倒序：从下面这两块区域转移而来

行号/列号	0	1	2	3	4	5
i	0	1	2	3	4	5
i+1	0	1	2	3	4	5

正序：从下面这两块区域转移而来

行号/列号	0	1	2	3	4	5
i	0	1	2	3	4	5
i+1	0	1	2	3	4	5