Leetcode

2026/04/22 00:00:00·2026/05/19 10:23:00

AI自回归·16 min read

note

双指针

使用到的常见手段有：

swap 交换 left 和 right 指针的值。
数组两侧交替移动指针
快慢指针

回文链表

移动零

盛最多水的容器

盛最多水的容器盛最多水的容器 python 版两侧交替移动指针。

三个数的和

由于不能有相同的结果，所以需要去重。三个数的和

快慢指针 article

环形链表

(leetcode-solve-problem 141)
(leetcode-solve-problem 287)

哈希表

两数之和

最长连续序列

最长连续序列因为是连续序列，所以需要找到序列的起始处。

先把所有的数字加进列表，再一个个检查这些数字，到到其中的序列起始数字。从起始数字开始向上找，确定最长序列。

和为k 的子数组

(leetcode-solve-problem 567)

子数组

前缀和

将 “耗时的计算” 从 “每次查询时” 转移到 “查询前的准备阶段”，通过牺牲一定的空间复杂度（存储预处理结果）来换取时间复杂度的降低（加速查询）。

新21点

和为 k 的子数组

(leetcode-solve-problem 567)

数学代码题

可能会使用到的手段有：

下界
等价

换水问题

需要转换思路。

换水问题 2

换水问题2

不同路径

(leetcode-solve-problem 62)

子串

排序

排序的作用有以下几条：

方便去重
可以

但一般来说，如果想要应用排序，都需要保证输出结果里面不包括数字在数组中的排序，而只包括结果。

三位数的和

合并区间

带 key 的排序。合并区间

拓扑排序

课程表

print(heapq.heappop(heap)) # 输出 1 #+end_src

注意：

堆中元素可以是元组，按第一个元素排序
默认最小堆，最大堆需取负值

快速排序

滑动窗口

最长无重复子串

找到字符串中所有的字母异位词

滑动窗口最大值

有序列表、最小堆、双向队列，这道题总得用一种特殊数据结构。

单调栈

接雨水2

(leetcode-solve-problem 407)

最小堆

最小堆是一种特殊的完全二叉树，每个节点的值都小于或等于其子节点的值。根节点始终是树中的最小元素。

特点：

父节点值 ≤ 子节点值
常用于快速获取最小值（O(1)）
插入、删除最小值的时间复杂度为 O(log n)

常见应用：

优先队列
堆排序
Dijkstra 算法
合并 K 个有序链表

heapq

heapq 是 Python 内置的最小堆模块，提供基于列表的堆操作。

常用函数：

=heapq.heappush(heap, item)=：插入元素
=heapq.heappop(heap)=：弹出最小元素
=heapq.heapify(x)=：将列表转为堆
=heapq.heappushpop(heap, item)=：插入后弹出最小元素
=heapq.heapreplace(heap, item)=：弹出最小元素后插入

示例：

import heapq

heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 2)
print(heapq.heappop(heap))  # 输出 1

注意：

堆中元素可以是元组，按第一个元素排序
默认最小堆，最大堆需取负值

数组中的第 k 个最大元素

heapq.heappush(heap, 2) print(heapq.heappop(heap)) # 输出 1 #+end_src

注意：

堆中元素可以是元组，按第一个元素排序
默认最小堆，最大堆需取负值

前 k 个高频元素

重构字符串

(leetcode-solve-problem 767)

接雨水2 transclusion

:END:

(leetcode-solve-problem 407)

线段树

最大子数组和

(leetcode-solve-problem 53)

爬楼梯

矩阵

链表

链表相交

反转链表

回文链表

(leetcode-solve-problem 141)
(leetcode-solve-problem 287)

环形链表 transclusion

(leetcode-solve-problem 141)
(leetcode-solve-problem 142)
(leetcode-solve-problem 287)

合并两个有序链表

(leetcode-solve-problem 21)

二叉树

二叉树的中序遍历

二叉树的最大深度

翻转二叉树

(leetcode-solve-problem 141)
(leetcode-solve-problem 287)

对称二叉树

先翻转，再对比是否相同。需要注意的是，不能从 root 开始翻转，不然就完全一样了。

二叉树的直径

(leetcode-solve-problem 543)

二叉树的层序遍历

(leetcode-solve-problem 102)

需要用到堆进行广度优先搜索

将有序数组转化为二叉搜索树

(leetcode-solve-problem 108)

图论

岛屿数量

腐烂的橘子

课程表

岛屿数量

水位上升的游泳池

(leetcode-solve-problem 794)

把所有的方格的高度与位置加进一个最小堆。

从列表里面逐一弹出方格，查看其四周是否有矮于它的方格，如果有，把自己加进它的集合。

每一次合并都需要检测，是不是左上与右下都在这个点内，如果是的话，那么就返回现在的这个方格的高度，否则还需要继续查找。

接雨水

单词搜索

(leetcode-solve-problem 79)

回溯算法

全排列

(leetcode-solve-problem 794)

把所有的方格的高度与位置加进一个最小堆。

从列表里面逐一弹出方格，查看其四周是否有矮于它的方格，如果有，把自己加进它的集合。

每一次合并都需要检测，是不是左上与右下都在这个点内，如果是的话，那么就返回现在的这个方格的高度，否则还需要继续查找。

电话号码的字母组合

(leetcode-solve-problem 794)

把所有的方格的高度与位置加进一个最小堆。

从列表里面逐一弹出方格，查看其四周是否有矮于它的方格，如果有，把自己加进它的集合。

每一次合并都需要检测，是不是左上与右下都在这个点内，如果是的话，那么就返回现在的这个方格的高度，否则还需要继续查找。

括号生成

(leetcode-solve-problem 22)

完全平方数

(leetcode-solve-problem 322)

我本来想用 BFS 的回溯算法解决这道题。但是这道题有一个致命的问题，导致它不能用 BFS 回溯算法解决：每一次加进队列里面的项，它的键值（硬币数）是不一样的。

这就想当于本来每一次都是向下走一层，每一层都是一米，但现在每一次向下走的深度不一样了，有的层是两米，有的层是三米。 (leetcode-solve-problem 279)

标记变量

电话号码的字母组合就是单纯地找到所有的组合。

所谓回溯算法就只是保存上一步的状态以方便恢复而已。

搜索

广度优先搜索

计算深度

腐烂的橘子

:END: 岛屿数量

深度优先搜索

二分查找

与排序有着紧密的关系。

二分查找有两种实现方式，一种是递归，一种是循环。

递归二分查找

递归二分查找是一种通过函数自身调用来实现的二分查找算法。其核心思想是：

基本情况：当搜索区间为空（low > high）时返回 -1（未找到）
递归步骤：
- 计算中间位置 mid
- 如果目标值等于中间元素，返回 mid
- 如果目标值小于中间元素，在左半区间递归搜索
- 如果目标值大于中间元素，在右半区间递归搜索

示例代码：

def binary_search_recursive(arr, target, low, high):
    if low > high:
        return -1  # 未找到

    mid = (low + high) // 2

    if arr[mid] == target: # 基线条件
        return mid
    elif arr[mid] > target:
        return binary_search_recursive(arr, target, low, mid - 1) # 收缩范围
    else:
        return binary_search_recursive(arr, target, mid + 1, high)

特点：

时间复杂度：O(log n)
空间复杂度：O(log n)（递归调用栈）
需要有序数组作为前提条件

相比迭代版本，递归二分查找代码更简洁，但存在递归深度限制和额外的栈空间开销。

循环二分查找

循环二分查找通过 while 循环实现，避免了递归调用的栈空间开销。

/核心步骤/：

初始化 low = 0, high = len(arr) - 1
循环条件：low <= high
计算中间位置 mid
比较目标值与中间元素
根据比较结果调整搜索区间

/示例代码/：

def binary_search_iterative(arr, target):
    low, high = 0, len(arr) - 1

    while low <= high:
        mid = (low + high) // 2

        if arr[mid] == target:
            return mid
        elif arr[mid] > target:
            high = mid - 1
        else:
            low = mid + 1

    return -1  # 未找到

/特点/：

时间复杂度：O(log n)
空间复杂度：O(1)（仅需常数空间）
比递归版本更高效，无递归深度限制

循环版本是实际应用中更常用的二分查找实现方式。

递归二分查找与循环二分查找的对比

特性	递归二分查找	循环二分查找
空间复杂度	O(log n)	O(1)
时间复杂度	O(log n)	O(log n)
代码简洁性	更简洁	稍复杂
性能	有递归开销	更高效
适用场景	教学、小数据量	生产环境、大数据量
栈	溢出风险 : 可能（深度大时）	无

/关键区别/：

递归版本依赖调用栈，深度受系统限制
循环版本空间效率更高，适合大规模数据
实际开发中推荐使用循环版本

搜索插入位置

搜索二维矩阵

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

(leetcode-solve-problem 34)

二进制与位运算

子集

:ID: de03295d-7608-4a86-b7f5-aab378245f55 :END:

全排列

子集

电话号码的字母组合

电话号码的字母组合就是单纯地找到所有的组合。

所谓回溯算法就只是保存上一步的状态以方便恢复而已。

完全平方数

(leetcode-solve-problem 279)

只出现一次的数字

(leetcode-solve-problem 136) #+end_src

队列

括号生成

(leetcode-solve-problem 22)

栈

最小栈

这道题的重点是需要想通：栈有着先进后出的特性。

所以，后进栈的元素如果比之前的最小元素还要大的话，那么这个新元素是不可能在某一个时刻中成为栈内的最小元素的。

我们之前遇到过滑动窗口最大值的问题，应该可以用类似的最小队列的方法来解决。用一个辅助队列来管理最大值，而后有一个定长队列一直进行着先进先出的流程；辅助队列中值的大小降序排列。如果出现一个更大的元素，就把这个元素之前的元素全部出队列。由此保证这个辅助队列从队头到队尾是依次降低的。

最小栈

字符串解码

每日温度

贪心算法

什么是贪心算法？

贪心算法是一种在每一步选择中都采取当前状态下最优（即最有利）的选择，从而希望导致结果是全局最优的算法策略。

特点：

局部最优选择
不可回溯
通常高效但未必得到全局最优解

适用条件：

问题具有最优子结构
贪心选择性质（局部最优能导致全局最优）

常见应用：

霍夫曼编码
最小生成树（Prim、Kruskal）
最短路径（Dijkstra）
区间调度问题

买卖股票的最佳时机

跳跃游戏

跳跃游戏 2

跳路游戏2

划分字母区间

重构字符串

动态规划

动态规划（Dynamic Programming，简称 DP）是一种通过将复杂问题分解为重叠子问题，并利用子问题的解来高效求解原问题的算法思想。它的核心是避免重复计算，通常用于解决具有最优子结构和重叠子问题特性的问题。

将一个数字表示成幂的和的方案数新21点统计全为 1 的正方形子矩阵

多边形三角剖分的最低得分

接雨水

最大子数组和 transclusion

(leetcode-solve-problem 53)

爬楼梯

杨辉三角

打家劫舍

完全平方数

:PROPERTIES: :ID: d6d65a94-54b8-43c2-8b49-c72c53214fa5

(leetcode-solve-problem 322)

零钱兑换

:PROPERTIES: :ID: dc38566a-702c-4e29-b2ac-98b477c2de92

(leetcode-solve-problem 322)

多维动态规划

子串

最小路径和

(leetcode-solve-problem 64)

子串

最长回文子串

(leetcode-solve-problem 5)

要想找到最长回文子串，必然需要两个指针，分别指向子串的头与尾。

也不一定。

从一个点出发，向两边延伸，看能延伸到多长，这也是一个思路。

对于回文子串类的问题，不能忘记有两种情况：一种是奇数长度回文子串，另一种是偶数长度。

对于一个回文子串，我们可以减小问题规模：只需要把回文子串的两端的值给去掉。如果这是一个回文子串，那么它去掉两端的值以后依然是。

最长公共子序列

(leetcode-solve-problem 1250)

重点在于不改变顺序

由于要求两者都按顺序取字母，可以减小问题的规模了

    对于 text1 的前 i 个字母与 text2 的前 j 个字母。

(leetcode-solve-problem 136) #+end_src

技巧

只出现一次的数字

(leetcode-solve-problem 136)

多数元素

投票、随机数

(leetcode-solve-problem 169)
#+begin_src emacs-lisp :tangle yes :comments link :results none
(leetcode-solve-problem 794)

把所有的方格的高度与位置加进一个最小堆。

从列表里面逐一弹出方格，查看其四周是否有矮于它的方格，如果有，把自己加进它的集合。

每一次合并都需要检测，是不是左上与右下都在这个点内，如果是的话，那么就返回现在的这个方格的高度，否则还需要继续查找。

颜色分类

(leetcode-solve-problem 169)

下一个排列

(leetcode-solve-problem 31)

寻找重复数

(leetcode-solve-problem 136)

并查集

水位上升的游泳池

(leetcode-solve-problem 794)

把所有的方格的高度与位置加进一个最小堆。

从列表里面逐一弹出方格，查看其四周是否有矮于它的方格，如果有，把自己加进它的集合。

每一次合并都需要检测，是不是左上与右下都在这个点内，如果是的话，那么就返回现在的这个方格的高度，否则还需要继续查找。