跳到主要内容

核心算法套路详解

本文通过**"人话 + 动图式拆解 + 代码模拟"**来讲解最核心的算法套路。

数组类算法​

1. 动态规划 (Dynamic Programming, DP)​

通俗理解： 它的核心叫"记事本"。

假如你在玩游戏，第 10 关很难打。你打过了第 9 关，把存档保存了。下次打第 10 关失败了，你是从第 1 关重新打，还是直接读取第 9 关的存档？当然是读档！DP 就是把每一步算出来的结果（存档）记在数组里，后面直接用。

经典案例：爬楼梯 (LeetCode 70)​

题目： 你要爬 nn 阶楼梯。每次你可以爬 1 或 2 个台阶。有多少种不同的方法可以爬到楼梯顶端？

解题思路模拟：

  • 假设你要爬到第 10 层。

  • 你最后一步只有两种可能：

    1. 从第 9 层爬 1 步上来。
    2. 从第 8 层爬 2 步上来。

  • 结论： 想知道爬到 10 层的方法数，只要知道（爬到 9 层的方法数 + 爬到 8 层的方法数）。

  • 公式（状态转移方程）： dp[i]=dp[i−1]+dp[i−2]dp[i] = dp[i-1] + dp[i-2]

推导过程：

  1. 第 1 层： 只有 1 种方法 (1)。记为 dp[1]=1dp[1] = 1。
  2. 第 2 层： 有 2 种方法 (1+1, 2)。记为 dp[2]=2dp[2] = 2。
  3. 第 3 层： 等于第 2 层 + 第 1 层的方法数。dp[3]=2+1=3dp[3] = 2 + 1 = 3。
  4. 第 4 层： 等于第 3 层 + 第 2 层的方法数。dp[4]=3+2=5dp[4] = 3 + 2 = 5。 ...一直加到第 N 层。

代码逻辑 (Python):

# dp 数组就是我们的"记事本"
def climbStairs(n):
    if n <= 2: return n

    # 初始化记事本
    dp = [0] * (n + 1)
    dp[1] = 1
    dp[2] = 2

    # 从第 3 层开始算，利用之前的存档
    for i in range(3, n + 1):
        dp[i] = dp[i-1] + dp[i-2]

    return dp[n]

2. 双指针 (Two Pointers)​

通俗理解： 核心叫**"包抄"**。

就像你在书架上找两本书，它们的厚度加起来要等于 10cm，而且书是按厚度从小到大排好的。你用左手指着最薄的，右手指着最厚的，看加起来是不是 10，不对就移动手指。

经典案例：两数之和 II - 输入有序数组 (LeetCode 167)​

题目： 给一个从小到大排序的数组 [2, 7, 11, 15]，找到两个数，让它们相加等于目标值 9。

解题思路模拟：

  • 初始状态： 左指针 L 指向 2 (最小)，右指针 R 指向 15 (最大)。

  • 第一轮： 计算 2 + 15 = 17。

    • 结果 17 > 9 (太大了)。
    • 思考： 15 就算跟最小的 2 加起来都嫌大，那 15 肯定没戏了。
    • 操作： 右指针 R 往左移一位，指向 11。

  • 第二轮： 计算 2 + 11 = 13。

    • 结果 13 > 9 (还是大)。
    • 操作： 右指针 R 再往左移，指向 7。

  • 第三轮： 计算 2 + 7 = 9。

    • 结果： 9 == 9。找到了！

代码逻辑:

def twoSum(numbers, target):
    left = 0
    right = len(numbers) - 1

    while left < right:
        current_sum = numbers[left] + numbers[right]

        if current_sum == target:
            return [left, right] # 找到了
        elif current_sum > target:
            right -= 1 # 太大了，让右边变小点
        else:
            left += 1  # 太小了，让左边变大点

3. 滑动窗口 (Sliding Window)​

通俗理解： 核心叫**"毛毛虫伸缩"**。

想象你在吃自助餐，盘子（窗口）只能装这么点东西。你想吃更多，就得把盘子这一头往前伸（进食），如果盘子满了或者不符合规定了，那一头就要吐出来（排出），保持盘子里的东西始终符合要求。

经典案例：长度最小的子数组 (LeetCode 209)​

题目： 数组 [2, 3, 1, 2, 4, 3]，找到一个连续子数组，它的和 ≥7\geq 7，并且长度最小。

解题思路模拟：

定义窗口 window，左边界 L，右边界 R。

  1. 进食 (R 向右移)：

    • [2] (sum=2) -> 不够
    • [2, 3] (sum=5) -> 不够
    • [2, 3, 1] (sum=6) -> 不够
    • [2, 3, 1, 2] (sum=8) -> 够了！(>=7)。当前长度是 4。

  2. 缩窗 (L 向右移，试图优化)：

    • 既然 [2, 3, 1, 2] 已经达标，那我们试试把最左边的 2 扔掉行不行？
    • 扔掉 2，变成 [3, 1, 2] (sum=6) -> 不够了。
    • 说明刚才那个长度 4 已经是这一轮的极限了。

  3. 继续进食 (R 继续右移)：

    • R 移到 4。窗口变成 [3, 1, 2, 4] (sum=10) -> 够了！

  4. 再次缩窗 (L 向右移)：

    • 扔掉左边的 3，变成 [1, 2, 4] (sum=7) -> 够了！ 长度为 3 (比刚才的 4 更短，更新答案)。
    • 再扔掉左边的 1，变成 [2, 4] (sum=6) -> 不够了。
    • 停止缩窗，继续 R 往右...

代码逻辑:

def minSubArrayLen(target, nums):
    left = 0
    current_sum = 0
    min_length = float('inf') # 无穷大

    # R 主动向右走 (进食)
    for right in range(len(nums)):
        current_sum += nums[right]

        # 当满足条件时，L 尝试向右缩 (减肥/优化)
        while current_sum >= target:
            current_len = right - left + 1
            min_length = min(min_length, current_len) # 更新最小长度记录

            current_sum -= nums[left] # 把左边的吐出来
            left += 1 # 左边界收缩

    return min_length

树与图类算法​

4. 深度优先搜索 (DFS - Depth First Search)​

通俗理解： 性格叫**"不撞南墙不回头"**。

想象你在走迷宫。你是一个非常有原则的人：只要前面有路，就一直往深处走。直到走到死胡同（撞墙了），才回头退到上一个路口，换一条路继续走到黑。

  • 核心工具： 递归 (Recursion) —— 自己调用自己。

经典案例：二叉树的最大深度 (LeetCode 104)​

题目： 给一颗树，算出它最高有多少层。

解题思路模拟：

你可以把自己想象成一个只有**"微观视角"**的机器人，你站在任何一个节点上，只知道一件事：

  • "我的深度 = 1 (我自己) + max(左边孩子的深度, 右边孩子的深度)"

推导过程：

  1. 根节点问： "我多深？" 先得问左孩子和右孩子。
  2. 左孩子问： "我多深？" 它下面没孩子了（死胡同，Base Case）。
  3. 左孩子答： "我是叶子，深度是 1"。汇报给根节点。
  4. 右孩子继续往下问... 直到所有死胡同都探完。
  5. 根节点总结： 左边深还是右边深？挑个大的 +1+1。

代码逻辑:

def maxDepth(root):
    # 1. 死胡同（Base Case）：如果没有节点了，深度就是 0
    if not root:
        return 0

    # 2. 递归（一直往下问）：
    left_depth = maxDepth(root.left)   # 问左边
    right_depth = maxDepth(root.right) # 问右边

    # 3. 总结
    return max(left_depth, right_depth) + 1

5. 广度优先搜索 (BFS - Breadth First Search)​

通俗理解： 性格叫**"地毯式搜索"**。

这次你不再是一条路走到黑了。想象往平静的湖里扔一颗石头，涟漪是一圈一圈向外扩散的。BFS 就是先看完离我最近的一圈，再看稍微远一点的一圈，层层推进。

  • 核心工具： 队列 (Queue) —— 先进先出，像排队买票。

经典案例：二叉树的层序遍历 (LeetCode 102)​

题目： 给一颗树，把每一层的节点数字打印出来。比如 [[3], [9, 20], [15, 7]]。

解题思路模拟：

我们要用一个队列 (Queue) 来模拟"排队"。

  1. 初始： 只有 根节点 在排队。

  2. 第一轮：

    • 根节点 出队（处理它）。
    • 关键点： 根节点离开前，把它的左孩子和右孩子拉进队伍里排队。

  3. 第二轮：

    • 现在的队伍里是 左孩子 和 右孩子。
    • 它们依次出队，离开前，把它们的儿子孙子们拉进队伍...

  4. 循环： 只要队伍不空，就一直处理。

代码逻辑:

import collections

def levelOrder(root):
    if not root: return []

    # 初始化队列，先把老大放进去
    queue = collections.deque([root])
    result = []

    while queue:
        level_nodes = []
        # 看当前这一层有多少人
        level_size = len(queue)

        # 这一层的人依次出列
        for _ in range(level_size):
            node = queue.popleft() # 出队
            level_nodes.append(node.val)

            # 把下一层的人拉进来
            if node.left: queue.append(node.left)
            if node.right: queue.append(node.right)

        result.append(level_nodes)

    return result

6. 回溯法 (Backtracking)​

通俗理解： 核心叫**"虽然我也试错，但我会撤销"**。

它其实就是 DFS 的一种，但多了一个**"后悔药"**的步骤。 想象你在玩填字游戏或者把家具摆进房间。

  • 尝试： 把沙发摆左边。
  • 发现： 哎呀，挡住门了（不符合条件）。
  • 回溯（关键）： 把沙发搬回原位（撤销刚才的操作），恢复现场。
  • 尝试： 把沙发摆右边...

经典案例：全排列 (LeetCode 46)​

题目： 给定数字 [1, 2, 3]，列出所有可能的排列组合（比如 [1,2,3], [1,3,2], [2,1,3]...）。

解题思路模拟：

手里有三个空盒子 [_] [_] [_]，手里有牌 1, 2, 3。

  1. 走到第一个盒子：

    • 选择： 放 1。剩余牌 [2, 3]。

    • 走到第二个盒子：

      • 选择： 放 2。剩余牌 [3]。

      • 走到第三个盒子：

        • 选择： 放 3。
        • 结果： 此时盒子是 [1, 2, 3]。记录下来！
        • 回溯（撤销）： 把 3 拿出来，回到上一步。

      • 换个选择： 在第二个盒子改放 3...

    • 回溯（撤销）： 把 1 从第一个盒子拿出来，恢复原样。

  2. 换个选择： 在第一个盒子放 2...

代码逻辑 (重点看撤销那一步):

def permute(nums):
    res = []

    # path: 当前已经做出的选择 (盒子里的牌)
    def backtrack(path, available_nums):
        # 1. 结束条件：没有可选的牌了
        if not available_nums:
            res.append(path)
            return

        # 2. 遍历做选择
        for i in range(len(available_nums)):
            # 做选择：拿出一张牌，加到 path 里
            current_num = available_nums[i]
            remaining_nums = available_nums[:i] + available_nums[i+1:]

            # 递归进入下一层
            backtrack(path + [current_num], remaining_nums)

            # 注意：这里其实隐含了回溯。
            # 因为我们传给递归的是新的列表 path + [num]，
            # 本层的 path 变量并没有变，所以循环进入下一次时，path 还是干净的。
            # 如果用全局变量 list，就需要显式的 path.pop()。

    backtrack([], nums)
    return res

总结速记表​

算法核心动作场景比喻必背代码结构
动态规划记 (Memo)游戏存档，查表填表dp[i] = dp[i-1] + ...
双指针夹 (Pinch)两头堵，包抄夹击while left < right
滑动窗口伸缩 (Slide)毛毛虫，一伸一缩for right + while left
DFS钻 (Deep)走迷宫，一条路走到黑递归(node.left); 递归(node.right)
BFS推 (Breadth)水波纹，一圈圈扩散Queue + While 循环
回溯悔 (Undo)摆家具，摆错了搬回来Loop + Recursion + 撤销选择

递归的信心​

写 DFS 和回溯时最重要的心态是**"递归的信心"**。

什么是递归的信心？

当你写递归函数时，你要相信你调用的那个函数（即使它是自己）一定能正确完成任务。

以二叉树最大深度为例：

def maxDepth(root):
    if not root:
        return 0
    return max(maxDepth(root.left), maxDepth(root.right)) + 1

写 maxDepth(root.left) 时，你不需要去想它内部是怎么递归的。你只需要相信：调用它，它就会返回左子树的最大深度。就像调用别人写好的函数一样。

核心要点：

  1. 明确函数定义： maxDepth(node) 返回以 node 为根的树的最大深度
  2. 相信递归调用： maxDepth(root.left) 一定能正确返回左子树深度
  3. 只关注当前层： 当前节点该做什么？—— 取左右子树深度的最大值 +1
  4. 写好 Base Case： 空节点返回 0

不要试图在脑子里展开递归！ 那会让你崩溃。就像你不会去想 print() 函数内部是怎么把字符显示到屏幕上的一样。

推荐练习顺序​

  1. 入门： LeetCode 70 (爬楼梯) - 感受 DP 的"存档"思想
  2. 双指针： LeetCode 167 (两数之和 II) - 感受"包抄"
  3. 滑动窗口： LeetCode 209 (长度最小的子数组) - 感受"毛毛虫"
  4. DFS： LeetCode 104 (二叉树最大深度) - 建立"递归的信心"
  5. BFS： LeetCode 102 (二叉树层序遍历) - 感受"水波纹"
  6. 回溯： LeetCode 46 (全排列) - 感受"后悔药"