09 · 算法思维（Algorithm Thinking）

📅 预计 90 分钟　|　⭐ 常用算法与数据结构
✍️ 本讲配套练习：本地 python grader.py 09，或网页练习

9.1 什么是算法：把「怎么做」写成代码

算法不是数学课里的天书，它就是你每天在生活里都在用的做事步骤。比如「泡一杯奶茶」：拿杯子 → 倒茶 → 加糖 → 搅拌。把这一串步骤写成 Python，让别人（电脑）照着做，就是算法。

好的算法看两点：正确（结果对）和高效（跑得快、省内存）。怎么衡量快不快？用时间复杂度，用大 O 表示「当数据变大 n 倍时，时间大约变几倍」。

复杂度 生活比喻 例子
O(1) 一秒钟完成，和数量无关 取列表第一个元素
O(log n) 猜数字，每猜一次范围砍半 二分查找
O(n) 挨个看一遍 线性查找、遍历
O(n log n) 先分组再合并，比 n² 快很多 归并排序、快排
O(n²) 每两个人都要比一次 嵌套两层循环 
# O(n)：一趟遍历求最大值
nums = [4, 7, 2, 9, 5]
mx = nums[0]
for x in nums:
    if x > mx:
        mx = x
print(mx)          # 输出 9

# O(n²)：两层循环全比较（冒泡排序的雏形）
a = [3, 1, 2]
for i in range(len(a)):
    for j in range(i + 1, len(a)):
        if a[i] > a[j]:
            a[i], a[j] = a[j], a[i]
print(a)           # 输出 [1, 2, 3]

⚠️ 常见错误

  • 把 O(2n)、O(n/2) 当回事：大 O 只关心数量级，2n 和 n 都写成 O(n)。两层循环嵌套（即使其中一层只走一半）也是 O(n²)。
  • 只求对，不求快：笔试里「数据量 10 万」直接提醒你 O(n²) 大概率超时，要想着优化。

9.2 二分查找：猜数字游戏的高级版 ⭐

你玩过「1~100 猜数字」吗？最聪明的玩法不是从 1 猜到 100，而是每次猜中间：对方说大了，范围立刻砍半。二分查找就是这个思路——只不过猜的对象是有序列表里的下标。

前提：序列必须有序。每次取中间下标 mid，和目标比大小，直接丢掉一半，所以 O(n) 变成 O(log n)。数据量翻 100 倍，二分只多查几次。

def binary_search(nums, target):
    left, right = 0, len(nums) - 1        # 左右夹逼
    while left <= right:
        mid = (left + right) // 2         # 取中间（防下标越界）
        if nums[mid] == target:
            return mid                    # 找到了，返回下标
        elif nums[mid] < target:
            left = mid + 1                # 目标在右半，砍掉左半
        else:
            right = mid - 1               # 目标在左半，砍掉右半
    return -1                             # 没找到

print(binary_search([1, 3, 5, 7, 9], 7))  # 输出 3
print(binary_search([1, 3, 5, 7, 9], 2))  # 输出 -1

⭐ 二分模板三要素：while 条件（left <= right）、mid 取中间、左右边界更新（mid ± 1）。三者错一步就会死循环或漏解。

Python 内置 bisect.bisect_left(nums, target) 就是二分的现成实现，竞赛里可以直接用。

⚠️ 常见错误

  • 边界写成 left = mid 或 right = mid：当区间只剩 1 个元素时，mid 永远不变 → 死循环。记住要 mid + 1 / mid - 1。
  • while 条件写成 left < right：会漏掉只剩一个元素时恰好是目标的情况。配套练习 ex02 专门测这个。
  • 忘了列表要先排序：二分只对有序序列成立，乱序直接二分结果全错。

9.3 穷举：暴力出奇迹

穷举（brute force）= 把所有可能性都试一遍。思路简单、代码好写，数据量小时它就是最优解。经典题「两数之和」：找哪两个数加起来等于 target，那就两层循环把每对都试一次。

def two_sum(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):   # j 从 i+1 开始，避免自己和自己的下标对
            if nums[i] + nums[j] == target:
                return [i, j]               # 题目要求小下标在前
    return [-1, -1]

print(two_sum([2, 7, 11, 15], 9))   # 输出 [0, 1]
print(two_sum([2, 7, 11, 15], 30))  # 输出 [-1, -1]

刷题口诀：先想暴力能不能过，再想能不能优化。能过就直接交，不能过再上双指针/哈希。

⚠️ 常见错误

  • j 从 0 开始：会算上 i == j 的「自己+自己」，还可能重复输出 [i,j] 和 [j,i]。j 从 i+1 开始，天然去重。
  • 直接 return [-1,-1] 放错位置：要放到两层循环外面，否则第一次比较不相等就提前返回了。配套练习 ex04 考察这个。
  • 把下标当值比较：比的是 nums[i] + nums[j]，不是 i + j。

9.4 排序：从冒泡到快排

排序是算法里最经典的入门战场。考试常考手写冒泡和选择，面试爱问快排思想，工程里直接用内置 sorted()。先记住这张速览表：

算法 复杂度 特点
冒泡/选择/插入 O(n²) 简单，入门必会
归并/快排 O(n log n) 高效，常考思想
内置 sorted() O(n log n) 最常用，直接用

9.4.1 冒泡排序：气泡上浮

想象气泡从水底往上浮，越往上气泡越大。冒泡排序就是相邻两个比大小，大的往右「冒」，每一轮把当前最大数推到末尾。

def bubble_sort(lst):
    arr = lst[:]                            # 复制一份，不改原列表
    n = len(arr)
    for i in range(n):                      # 进行 n 轮
        for j in range(n - 1 - i):          # 已排好的末尾不用再比
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]   # 交换
    return arr

print(bubble_sort([3, 1, 2]))     # 输出 [1, 2, 3]
print(bubble_sort([1, 1, 2, 1]))  # 输出 [1, 1, 1, 2]

9.4.2 选择排序：每轮挑最小的放前面

像挑西瓜：先挑出全场最小的放第一位，再从剩下里挑最小的放第二位……每轮只做一次交换。

def selection_sort(lst):
    arr = lst[:]
    n = len(arr)
    for i in range(n):
        m = i                               # 假设 i 是最小值位置
        for j in range(i + 1, n):
            if arr[j] < arr[m]:
                m = j                       # 记下真正最小值的下标
        arr[i], arr[m] = arr[m], arr[i]     # 放到正确位置
    return arr

print(selection_sort([4, 2, 3, 1]))   # 输出 [1, 2, 3, 4]

9.4.3 插入排序：像打扑克理牌

抓一张新牌，插入到手里已经排好序的牌里。插入排序就是从第 2 个元素开始，把它往左边已经有序的部分里插。

def insertion_sort(lst):
    arr = lst[:]
    for i in range(1, len(arr)):
        key = arr[i]                        # 手里的新牌
        j = i - 1
        while j >= 0 and arr[j] > key:      # 把比 key 大的牌往后挪
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key                    # 新牌落位
    return arr

print(insertion_sort([5, 2, 4, 1, 3]))   # 输出 [1, 2, 3, 4, 5]

9.4.4 归并思想：先拆两半，排好再合并

归并排序分三步：拆 → 各自排 → 合并。最核心的「合并两个有序列表」就是经典的双指针套路——两个指针各自指向有序列表开头，谁小谁进结果，谁的后移。

def merge_lists(a, b):
    i = j = 0
    res = []
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            res.append(a[i]); i += 1
        else:
            res.append(b[j]); j += 1
    res.extend(a[i:])                       # 剩下的直接接上
    res.extend(b[j:])
    return res

print(merge_lists([1, 3, 5], [2, 4, 6]))   # 输出 [1, 2, 3, 4, 5, 6]

9.4.5 快速排序：选个「基准」，小的站左大的站右

快排是分治思想的主角：选一个数当基准（pivot），比它小的放左边，比它大的放右边，然后对左右各自再排。写法有很多种，最易懂的版本直接用列表推导式划分：

def quick_sort(lst):
    if len(lst) <= 1:
        return lst[:]                       # 递归出口
    pivot = lst[0]
    left  = [x for x in lst if x < pivot]    # 严格小于
    right = [x for x in lst if x > pivot]    # 严格大于
    mid   = [x for x in lst if x == pivot]   # 相等的单独放一起，避免死循环
    return quick_sort(left) + mid + quick_sort(right)

print(quick_sort([6, 3, 8, 5, 2]))   # 输出 [2, 3, 5, 6, 8]
print(quick_sort([3, 1, 3, 2]))      # 输出 [1, 2, 3, 3]

9.4.6 哈希计数：用字典当计数器

很多排序/去重问题其实不用排序，用字典统计次数更直接——这叫哈希计数。遍历一遍，每个元素在字典里加一，就是 O(n)。

def char_frequency(s):
    counts = {}
    for ch in s:
        counts[ch] = counts.get(ch, 0) + 1   # get 取不到就默认 0
    return counts

print(char_frequency("hello"))
# 输出 {'h': 1, 'e': 1, 'l': 2, 'o': 1}

⚠️ 常见错误（排序）

  • 直接改原列表：面试官一问「原列表变了吗」就露馅。写 arr = lst[:] 复制一份再排。
  • 冒泡内层 range(n-1-i) 写成 range(n)：会把已经排好的末尾再比一次，浪费但不算错；写成 range(n-i) 会导致 arr[j+1] 越界报 IndexError。
  • 插入排序漏掉 j >= 0 条件：key 比左边所有牌都小时，j 会一直减到 -1，arr[j] 越界。
  • 快排对重复元素死循环：如果只分 <= 和 >，全相等的列表会无限递归。用 mid 单独装相等元素是标准解法。
  • 归并忘记接剩余部分：某个列表先走完，另一个剩下的要 extend 进去。

9.5 递归与分治：套娃的艺术

递归就是函数调用自己，像俄罗斯套娃：打开最大的娃，里面套着一样的、但更小的娃，直到最小的那个是实心的（这就是终止条件）。任何递归都要回答两个问题：① 终止条件是什么（出口）？② 这一步和更小的一步有什么关系（递推式）？

经典例子：斐波那契数列 f(n) = f(n-1) + f(n-2)，出口是 n < 2 时 f(n) = n。

def fib(n):
    if n < 2:              # 出口：0 和 1 直接返回
        return n
    return fib(n - 1) + fib(n - 2)   # 递推：拆成两个更小的子问题

print(fib(6))    # 输出 8
print(fib(10))   # 输出 55

汉诺塔：把 n 个盘子从 A 挪到 C

三根柱子 A、B、C，一次只能挪一个，大的不能压小的。n 个盘子怎么挪？把上面的 n-1 个先挪到 B（借助 C），把最底下那个挪到 C，再把 n-1 个从 B 挪到 C（借助 A）——这就是把大问题拆成两个规模 n-1 的小问题。

def hanoi(n, src, dst, mid):
    if n == 1:
        print(f"{src} -> {dst}")
        return
    hanoi(n - 1, src, mid, dst)    # 先把 n-1 个挪到中转柱
    print(f"{src} -> {dst}")       # 把最大的挪到目标柱
    hanoi(n - 1, mid, dst, src)    # 再把 n-1 个挪回目标柱

hanoi(2, 'A', 'C', 'B')
# 输出：
# A -> B
# A -> C
# B -> C

最大公约数：辗转相除

gcd(a, b) = gcd(b, a % b)，直到 b == 0 时返回 a。这是递归思想的教科书例子。

def gcd(a, b):
    if b == 0:            # 出口
        return a
    return gcd(b, a % b)  # 递推

print(gcd(12, 18))   # 输出 6
print(gcd(7, 13))    # 输出 1

⚠️ 常见错误（递归）

  • 忘了写出口 → 无限递归，RecursionError: maximum recursion depth exceeded（爆栈）。先写出口再写递推。
  • 出口写错：比如 fib 出口写成 if n == 1，那 fib(0) 会一直递归直到爆栈。
  • 无脑递归不优化：fib(40) 朴素的 f(n-1)+f(n-2) 会指数级膨胀，慢到怀疑人生。大 n 用循环或动态规划（见 9.8）。
  • 汉诺塔打印顺序错：打印要放在「两次递归之间」，不是开头也不是结尾。

9.6 双指针与滑动窗口：让遍历不回头

双指针：一头一尾往中间夹

很多时候暴力要 O(n²)，用两个指针一左一右同时动，一趟就搞定 O(n)。最经典的就是反转列表：

def reverse_list(lst):
    arr = lst[:]
    i, j = 0, len(arr) - 1
    while i < j:
        arr[i], arr[j] = arr[j], arr[i]   # 左右交换
        i += 1
        j -= 1                            # 同时向中间走
    return arr

print(reverse_list([1, 2, 3, 4]))   # 输出 [4, 3, 2, 1]

双指针还有另一种形态：一快一慢（快指针负责前进，慢指针记录位置），用于原地去重等。思路一样：两个指针互相配合，省掉一层循环。

滑动窗口：一根窗口在数组上滑

滑动窗口适合「找满足条件的连续子数组」。想象一扇可以伸缩的窗，right 端往前扩把数加进来，一旦和满足条件，就试着从 left 端收缩找更短的窗口——两个指针都只往前走，不回头，所以是 O(n)。

经典题「最短子数组」（LeetCode 209）：

def min_window(target, nums):
    left = 0
    total = 0
    best = len(nums) + 1                   # 用一个很大的初始值
    for right in range(len(nums)):
        total += nums[right]               # 窗口右端扩张
        while total >= target:             # 满足条件就尝试收缩
            best = min(best, right - left + 1)
            total -= nums[left]
            left += 1
    return best if best <= len(nums) else 0   # 没有答案返回 0

print(min_window(7, [2, 3, 1, 2, 4, 3]))   # 输出 2 （子数组 [4,3]）
print(min_window(11, [1, 1, 1, 1]))        # 输出 0 （全加起来都不够）

⚠️ 常见错误（双指针）

  • 交换后忘记让两个指针同时动：只 i += 1 不 j -= 1，指针会交叉越界或死循环。
  • while 条件写成 i <= j：两个指针相遇后还会再交换一次，把已反转的部分又翻回来。
  • 滑动窗口的 while 写成了 if：窗口可能需要收缩多次，if 只收缩一次会漏掉更短答案。
  • 窗口收缩时忘了扣掉 nums[left]：total 不更新，left 再前进也没意义。

9.7 贪心：每步都吃最大那一口

贪心（greedy）的策略是：每一步都做当前看起来最优的选择，从不回头。很多问题这样就能得到全局最优——但不是所有问题都行，所以「判断能不能贪」本身就是考点。

最典型的例子是找零钱：面额 1、5、10、25 美分，凑 38 美分要最少硬币。贪心做法是优先用大面额：一个 25、一个 10、三个 1，共 5 枚。

def min_coins(coins, amount):
    coins = sorted(coins, reverse=True)     # 从大到小
    count = 0
    for c in coins:
        count += amount // c                # 这个面额最多用几个
        amount %= c                         # 剩下多少
    return count if amount == 0 else -1     # 凑不出返回 -1

print(min_coins([1, 5, 10, 25], 38))   # 输出 5
print(min_coins([5, 10], 3))           # 输出 -1 （凑不出）

另一个经典是区间调度：选最多的不重叠区间。做法：按结束时间排序，每次选「结束最早且和上一个不冲突」的区间——因为结束越早，给后面留的余地越大。

⚠️ 常见错误（贪心）

  • 以为贪心永远正确：比如面额 [1, 3, 4] 凑 6，贪心会选 4+1+1（3 枚），但正确答案是 3+3（2 枚）。贪心错了就是错了，这类题要用动态规划。配套练习 ex12 用的都是贪心成立的标准面额。
  • 忘了面额要先排序：不排序从大到小，第一个面额可能不是最大的。
  • 凑不出时返回 0 而不是 -1：约定清楚，练习里凑不出要返回 -1。

9.8 动态规划初探：记住算过的，别重复算

动态规划（DP）的核心就一句话：把子问题的答案存起来，后面的答案由前面的拼出来。它和递归的区别是：递归是「从上往下拆」，DP 是「从下往上垒」，用数组把每一步记下来。

经典入门「爬楼梯」：一次能爬 1 级或 2 级，到第 n 级有几种方法？到第 n 级，要么从第 n-1 级爬 1 级上来，要么从第 n-2 级爬 2 级上来，所以：

f(n) = f(n-1) + f(n-2)，f(1)=1, f(2)=2。

它和斐波那契长得很像，但用循环写就不会爆栈、也不会重复计算：

def climb_stairs(n):
    if n <= 2:
        return n
    a, b = 1, 2                  # a=f(1), b=f(2)
    for _ in range(3, n + 1):
        a, b = b, a + b          # 滚动递推，只记住前两个
    return b

print(climb_stairs(4))    # 输出 5
print(climb_stairs(10))   # 输出 89

看到题先找状态（存什么）和转移方程（怎么从前面推出来），DP 就有了骨架。

⚠️ 常见错误（DP）

  • 初始值定义错：爬楼梯 f(1)=1, f(2)=2，写成 f(1)=1, f(2)=1 整个数列全错。
  • 范围没含端点：循环 range(3, n) 少了第 n 项，漏一。
  • 用递归写 DP 但不记忆化：climb_stairs(35) 指数级超时。DP 的意义就在于用循环/数组避免重复计算。
  • 滚动变量顺序搞反：a, b = b, a + b 是同时赋值；写成 a = b; b = a + b 会让 b 变成 2b，全错。

9.9 二维列表与矩阵：一张表格的遍历

二维列表就是「列表的列表」，像一张表格。matrix[i][j] 表示第 i 行第 j 列。遍历口诀：外层管行，内层管列。

matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
for i in range(len(matrix)):          # 行
    for j in range(len(matrix[i])):   # 列
        print(matrix[i][j], end=' ')
# 输出 1 2 3 4 5 6 7 8 9

矩阵转置：行变列

转置就是 result[j][i] = matrix[i][j]。做法：先造一个 列数×行数 的空矩阵，再逐个填。

def transpose(matrix):
    rows, cols = len(matrix), len(matrix[0])
    res = [[0] * rows for _ in range(cols)]   # 注意维度交换
    for i in range(rows):
        for j in range(cols):
            res[j][i] = matrix[i][j]
    return res

print(transpose([[1, 2, 3], [4, 5, 6]]))
# 输出 [[1, 4], [2, 5], [3, 6]]

螺旋遍历：绕着圈走

高级玩法：顺时针螺旋遍历矩阵，像剥洋葱，一层层从外往里。用 top/bottom/left/right 四个边界控制，每走完一条边就收缩边界——这是综合题 ex15 的考点。

def spiral_matrix(matrix):
    if not matrix:
        return []
    top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1
    res = []
    while top <= bottom and left <= right:
        for j in range(left, right + 1):      # 上边，向右
            res.append(matrix[top][j])
        top += 1
        for i in range(top, bottom + 1):      # 右边，向下
            res.append(matrix[i][right])
        right -= 1
        if top <= bottom:                     # 下边，向左
            for j in range(right, left - 1, -1):
                res.append(matrix[bottom][j])
            bottom -= 1
        if left <= right:                     # 左边，向上
            for i in range(bottom, top - 1, -1):
                res.append(matrix[i][left])
            left += 1
    return res

print(spiral_matrix([[1, 2, 3], [4, 5, 6], [7, 8, 9]]))
# 输出 [1, 2, 3, 6, 9, 8, 7, 4, 5]

⚠️ 常见错误（矩阵）

  • 用 [[0] * rows] * cols 造矩阵：这是同一个列表被复制了 cols 次，改一行其他行跟着变！必须用 [[0] * rows for _ in range(cols)]。
  • 转置忘记交换行列数：rows×cols 转置后是 cols×rows，维度反了就 IndexError。
  • 螺旋遍历少了 if top <= bottom 判断：奇数行/列时边界会交叉，重复添加元素。螺旋题先写 if not matrix 处理空矩阵。

9.10 质数判断与素数筛选

质数（素数）= 大于 1 且只有 1 和它本身两个约数的数。判断 n 是不是质数，最朴素的做法是从 2 试到 sqrt(n)——因为如果 n 有约数，必然有一个不超过它的平方根。

def is_prime(n):
    if n < 2:
        return False
    i = 2
    while i * i <= n:          # 只试到根号 n
        if n % i == 0:
            return False
        i += 1
    return True

print(is_prime(7))    # 输出 True
print(is_prime(1))    # 输出 False
print(is_prime(4))    # 输出 False

埃氏筛：一次筛出很多质数

要快速得到「2 到 n 里所有质数」，用埃拉托斯特尼筛法：先假设全是质数，从 2 开始，把每个质数的倍数全部划掉，剩下的就是质数。

def sieve(n):
    ok = [True] * (n + 1)
    ok[0] = ok[1] = False            # 0 和 1 不是质数
    for i in range(2, int(n ** 0.5) + 1):
        if ok[i]:                    # i 是质数
            for j in range(i * i, n + 1, i):   # 划掉它的倍数
                ok[j] = False
    return [x for x in range(2, n + 1) if ok[x]]

print(sieve(20))   # 输出 [2, 3, 5, 7, 11, 13, 17, 19]

⚠️ 常见错误（质数）

  • 忘了处理 n < 2：1 不是质数，负数也不是，先判掉。
  • 循环到 n 而不是 sqrt(n)：能算对，但数据大时慢到超时。i * i <= n 是正确的边界。
  • 埃氏筛下标越界：ok 长度是 n+1，循环要 range(2, n+1)，别漏最后一个。
  • 把筛法里 if ok[i] 写反：只在 i 是质数时筛它的倍数，写成「是合数才筛」就全错了。

9.11 刷题建议

  • 用 Python 刷题比 C++ 快得多，直接刷 LeetCode 入门 100 题，优先数组/字符串/哈希/双指针。
  • 与数据结构的关系：排序、查找、链表、树等数据结构，用 Python 各写一遍，能加深对算法与数据结构之间关系的理解。
  • 每道题先想「暴力能不能过」，再想「能不能优化」，最后对照标准解看思路差距。
  • 做不出来很正常：先看 5 分钟想不出，就看思路再自己写一遍。写不出来 ≠ 看不懂，看懂并重写一遍才是真的会。

📌 双语术语表（本讲）

中文 English
算法 algorithm
复杂度 complexity
二分查找 binary search
穷举 brute force
排序 sorting
冒泡排序 bubble sort
选择排序 selection sort
插入排序 insertion sort
归并排序 merge sort
快速排序 quick sort
哈希计数 hash counting
递归 recursion
分治 divide and conquer
双指针 two pointers
滑动窗口 sliding window
贪心 greedy
动态规划 dynamic programming
矩阵 matrix
埃氏筛 Sieve of Eratosthenes

💡 记忆口诀

  • 二分：有序先二分，while 左右夹，边界 ±1 别忘啦。
  • 冒泡：两两比大小，大的往上冒，末尾先排好。
  • 选择：每轮挑最小，跟头一位交换掉。
  • 插入：像打扑克，摸一张，往有序的牌里插。
  • 归并：先拆两半排，合并用双指针。
  • 快排：选个基准，小的站左大的站右，左右再递归。
  • 双指针：一头一尾往中间夹，一趟搞定省一层循环。
  • 滑动窗口：右端扩张，左端收缩，窗口滑过 O(n)。
  • 贪心：每步吃最大一口，不回头——先确认对不对。
  • 动态规划：记住算过的，后面由前面推。
  • 递归：先想出口，再想怎么拆成更小的自己。
  • 矩阵：外层管行内层管列，造空矩阵要用推导式。

⭐ 本讲考点清单

  1. 复杂度量级判断（嵌套循环 → O(n²)，二分 → O(log n)）
  2. 二分查找模板（有序序列，边界 mid ± 1）
  3. 冒泡/选择/插入排序手写（不改原列表）
  4. 归并思想：合并两个有序列表
  5. 快速排序思想（基准划分 + 递归）
  6. 哈希计数：用字典统计频次
  7. 双指针：反转列表、滑动窗口最短子数组
  8. 贪心：找零钱（标准面额）、区间调度
  9. 递归：斐波那契、汉诺塔、最大公约数
  10. 动态规划：爬楼梯递推
  11. 二维列表遍历、矩阵转置、螺旋矩阵
  12. 质数判断（试到 sqrt(n)）与埃氏筛
  13. 两数之和（穷举 + 进阶哈希）