1. 哈希表

哈希表（Hash Table）是一种基于数组的集合数据结构，它能够通过一个哈希函数将元素映射到数组的索引上，从而使得数据存储和检索变得非常高效。

哈希表的最大优势在于其快速的查找、插入和删除操作，每个操作的平均时间复杂度为 O(1)。在处理大量数据时，哈希表能够直接通过哈希函数计算出数据的位置，因此不需要像其他数据结构（如链表、树等）一样进行顺序查找。

哈希表在 Python 中通常就是指字典（dict），此外 collections 模块中的 defaultdict 也是 python 中哈希表的高效实现

1.1 python 字典

创建一个字典: my_dict = {'apple': 1, 'banana': 2, 'cherry': 3}
查找元素: print(my_dict['apple']) # 输出: 1
插入新的键值对: my_dict['orange'] = 4
删除元素: del my_dict['banana']
检查字典是否包含某个键: print('cherry' in my_dict) # 输出: True

1.2 defaultdict

collections 是 Python 标准库中的一个模块，提供了一些特殊的容器类型，这些容器类型是内置容器类型（如列表、字典、元组）的替代品。它们提供了一些额外的功能，使得在某些特定场景下更加方便和高效。defaultdict 是 collections 模块中的一个类，用于创建带有默认值的字典。它继承自 dict 类，并提供了一个默认值，当访问一个不存在的键时，会自动返回这个默认值。

from collections import defaultdict

d = defaultdict(int) # 创建一个带有默认值的字典
print(d['a'])  # 输出: 0

d = defaultdict(list) # 创建一个带有默认值的列表
d['a'].append(1)
d['a'].append(2)
print(d['a'])  # 输出: [1, 2]

d = defaultdict(set) # 创建一个带有默认值的集合
d['a'].add(1)
d['a'].add(2)
print(d['a'])  # 输出: {1, 2}

d = defaultdict(lambda: 'default') # 创建一个带有默认值的函数
print(d['a'])  # 输出: default

1.3 Counter

Counter 是 collections 模块中的另一个常用类，用于统计可迭代对象中元素的出现次数。它本质上是一个字典的子类，键是元素，值是该元素出现的次数。Counter 提供了许多便捷的方法用于处理频率统计，是处理字符串、列表等计数问题的利器。

from collections import Counter

# 统计字符串中字符的出现频率
c = Counter('aabbc')
print(c)  # 输出: Counter({'a': 2, 'b': 2, 'c': 1})

# 统计列表中元素的频率
nums = [1, 2, 2, 3, 3, 3]
count = Counter(nums)
print(count)  # 输出: Counter({3: 3, 2: 2, 1: 1})

# 获取出现频率最高的前两个元素
print(count.most_common(2))  # 输出: [(3, 3), (2, 2)]

# 可以像字典一样访问和修改元素频率
print(count[2])  # 输出: 2
count[2] += 1
print(count[2])  # 输出: 3

# 可以将两个 Counter 相加、相减、取交集和并集
c1 = Counter('aabb')
c2 = Counter('bccd')
print(c1 + c2)  # 输出: Counter({'b': 3, 'a': 2, 'c': 2, 'd': 1})
print(c1 & c2)  # 输出: Counter({'b': 1, 'c': 1})

2. 双指针

双指针是一种常见的算法技术，通常用来优化涉及数组或链表等数据结构的问题，尤其是当问题要求我们同时遍历数据结构的两个不同部分时。通过使用两个指针，我们可以在一个或多个序列中高效地进行查找、排序、删除等操作。

双指针技术通常会用到两个指针（或下标），这两个指针分别指向数据结构的不同位置，通常有以下几种常见的应用模式：

相向指针：两个指针从序列的两端出发，朝着中间汇聚，常用于解决一些“查找目标值”或“对撞”的问题。例如，在有序数组中寻找两个数的和为目标值的问题。
同向指针：两个指针从同一位置出发，其中一个指针用于遍历数组，另一个指针根据条件做相应的操作，常用于滑动窗口的技术。比如，窗口大小可变的情况下，左右指针的移动可以帮助我们高效地解决问题。
快慢指针：通过让一个指针以较快的速度遍历数据结构，而另一个指针以较慢的速度遍历，从而实现一些问题的优化，比如链表中找环、数组中找重复元素等。

3. 滑动窗口

滑动窗口（Sliding Window）是一种优化算法，通常用于处理数组或字符串类问题，特别是当问题要求我们寻找连续子数组或子字符串时。滑动窗口的核心思想是使用两个指针（或下标）来表示一个“窗口”，这个窗口可以随着算法的进行而扩展或收缩，通常通过左指针和右指针的移动来动态调整窗口大小。

滑动窗口常见的应用场景是当我们需要寻找一个子数组或子字符串，并且这个子数组或子字符串满足某些条件（如最小和、最大长度、满足某种规则等）。滑动窗口技术通常依赖于以下步骤：

初始化窗口：定义一个窗口区间，通常由两个指针（left 和 right）来表示，left 和 right 都指向数组的某个位置，初始时通常都指向数组的开始位置。
扩展窗口：通过移动右指针（right），扩展窗口的大小，并更新窗口内的状态（如元素的和、平均值等）。
收缩窗口：当窗口满足某些条件时，移动左指针（left）来收缩窗口，直到不再满足条件为止。窗口的大小随着左指针和右指针的调整而变化。
更新结果：根据当前窗口内的元素状态更新最终结果。

滑动窗口的类型：

固定大小的窗口：窗口的大小是固定的，一般用来处理诸如“最小子数组和”或“最长子数组”的问题。例如，给定一个数组和一个固定大小的窗口，求窗口中元素的和或最大值。
可变大小的窗口：窗口的大小是动态变化的，可以根据条件来扩展或收缩窗口的大小。常用于解决一些动态条件下的子数组问题，比如在一定条件下找到一个满足某些规则的最长子数组。

4. 动态规划

动态规划（Dynamic Programming，简称DP）是一种把复杂问题分解成更简单子问题，并利用子问题的最优解构建原问题最优解的算法思想。

动态规划的本质就是“记住历史，避免重复劳动”。
很多问题用暴力递归会重复算同一个子问题，动态规划就是把这些结果存起来，下次遇到直接用。

过程大致分为三步：

定义状态：用一个变量（或数组、表）表示子问题的解。
状态转移方程：找到状态之间的递推关系（也叫“状态转移”）。
初始化和遍历顺序：设置初始值，按照依赖关系计算所有状态，最终得到原问题的解。

举例：

斐波那契数列：f(n) = f(n-1) + f(n-2)，用dp数组存结果，避免重复递归。
最短路径、最大子数组和、背包问题等，都是动态规划的典型应用。

什么情况下用动态规划？

最优子结构（Optimal Substructure）：问题的最优解可以由其子问题的最优解推导出来。
- 求最大和，一定是前面的最大和加上当前数得到。
- 求最短路径，也是前面的最短路径加上当前这一步。
重叠子问题（Overlapping Subproblems）：大问题拆分出来的子问题会重复出现。
- 斐波那契数列：f(n) = f(n-1) + f(n-2)，计算f(n-1)、f(n-2)时会反复计算相同的f(k)。
编辑距离问题，不同子串之间会重复对比同样的位置。
无后效性：当前决策只依赖于历史状态，不受未来选择影响。

总结

当一个问题能拆成较小的子问题，且这些子问题会反复被用到，原问题的最优解可以通过子问题的最优解组合出来，这时候就可以用动态规划。

4.2 动态规划的解题步骤

定义状态：用一个变量（或数组、表）表示子问题的解。
状态转移方程：找到状态之间的递推关系（也叫“状态转移”）。
初始化和遍历顺序：设置初始值，按照依赖关系计算所有状态，最终得到原问题的解。

4.3 动态规划的解题步骤

斐波那契数列

题目：给定 $n$，求 $F(n) = F(n-1) + F(n-2)$，初始 $F(0)=0, F(1)=1$。

最优子结构：$F(n)$ 由 $F(n-1)$ 和 $F(n-2)$ 得到。
重叠子问题：不同路径会重复计算 $F(k)$。

dp = [0, 1]
for i in range(2, n+1):
    dp.append(dp[i-1] + dp[i-2])
return dp[n]

最大子数组和（LeetCode 53）

题目：给定数组，求连续子数组最大和。

最优子结构：以 $i$ 结尾的最大和由 $(i-1)$ 结尾的最大和推导。
重叠子问题：不同起点终点间的最优和会有重合部分。

curr_sum = max_sum = nums[0]
for i in range(1, len(nums)):
    curr_sum = max(nums[i], curr_sum + nums[i])
    max_sum = max(max_sum, curr_sum)
return max_sum

背包问题（0/1 背包）

题目：有 N 个物品，每个有重量和价值，背包最大容量 W，求最大总价值。

最优子结构：前 i 个物品装到容量 j 的最优解，可由前 i-1 个物品装容量 j 或 j-物品i重得到。
重叠子问题：不同选择下会遇到同样剩余容量、物品组合的子问题。

dp = [0] * (W+1)
for weight, value in items:
    for j in range(W, weight-1, -1):
        dp[j] = max(dp[j], dp[j-weight] + value)

最长公共子序列（LCS）

题目：给定两个字符串，求它们的最长公共子序列长度。

最优子结构：如果最后一位相同，转为前一位的 LCS，否则等于前两种方案的较大者。
重叠子问题：许多位置会反复比较同样的子串对。

m, n = len(text1), len(text2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(m):
    for j in range(n):
        if text1[i] == text2[j]:
            dp[i+1][j+1] = dp[i][j] + 1
        else:
            dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
return dp[m][n]

爬楼梯问题

题目：每次可以爬1或2阶楼梯，问到达第n阶有多少种爬法。

最优子结构：爬到n阶的方法=爬到n-1和n-2的方法之和。
重叠子问题：不同爬法会遇到同样的“剩余多少阶”子问题。

a, b = 1, 1
for _ in range(n):
    a, b = b, a+b
return a

4.4 总结表

题型	例题	状态转移方式
序列递推	斐波那契数列、爬楼梯	dp[i] = dp[i-1] + dp[i-2]
区间最值	最大子数组和	dp[i] = max(dp[i-1]+a[i], a[i])
背包组合优化	0/1背包	dp[j] = max(dp[j], dp[j-w]+v)
序列匹配	最长公共子序列（LCS）	if s[i]==t[j], else max(…)

1.1 python 字典

1.2 Counter

from collections import Counter

# 统计字符串中字符的出现频率
c = Counter('aabbc')
print(c)  # 输出: Counter({'a': 2, 'b': 2, 'c': 1})

# 统计列表中元素的频率
nums = [1, 2, 2, 3, 3, 3]
count = Counter(nums)
print(count)  # 输出: Counter({3: 3, 2: 2, 1: 1})

# 获取出现频率最高的前两个元素
print(count.most_common(2))  # 输出: [(3, 3), (2, 2)]

# 可以像字典一样访问和修改元素频率
print(count[2])  # 输出: 2
count[2] += 1
print(count[2])  # 输出: 3

# 可以将两个 Counter 相加、相减、取交集和并集
c1 = Counter('aabb')
c2 = Counter('bccd')
print(c1 + c2)  # 输出: Counter({'b': 3, 'a': 2, 'c': 2, 'd': 1})
print(c1 & c2)  # 输出: Counter({'b': 1, 'c': 1})

5. 链表

链表（Linked List）是一种常见的线性数据结构，由一组节点（Node）按顺序连接而成，每个节点包含数据部分和指向下一个节点的指针（或引用）。链表最大的特点是插入和删除操作非常高效，只需要改变指针指向即可，不像数组那样需要整体移动元素。

5.1 链表的基本结构

链表中的每个节点通常包含两个部分：

数据域（value/data）：存储节点的具体内容。
指针域（next）：指向下一个节点的地址。

常见的链表结构如下（以单链表为例）：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

5.2 链表的种类

单链表（Singly Linked List）

每个节点只有一个指向下一个节点的指针。
只能单向遍历。

双向链表（Doubly Linked List）

每个节点有两个指针，分别指向前驱和后继节点。
支持双向遍历，插入和删除更灵活。

循环链表（Circular Linked List）

最后一个节点的指针指向头节点，形成一个环。
可用于处理循环队列等场景。

5.3 链表的常见操作

•	遍历链表

通过指针从头结点逐个访问所有节点，直到 next 为空。
• 插入节点
• 头插法：在链表头部插入新节点。
• 尾插法：在链表末尾插入新节点。
• 指定位置插入：在任意位置插入新节点。
• 删除节点
• 删除头节点、尾节点或指定节点。
• 查找节点
• 根据值查找节点或判断链表中是否存在某个值。

def traverse(head):
    cur = head
    while cur:
        print(cur.val)
        cur = cur.next

5.4 常见面试题

反转链表（LeetCode 206）

合并两个有序链表（LeetCode 21）
链表中环的检测（LeetCode 141）
删除链表的倒数第 N 个节点（LeetCode 19）
两两交换链表中的节点（LeetCode 24）

def reverseList(head):
    prev = None
    cur = head
    while cur:
        next_node = cur.next
        cur.next = prev
        prev = cur
        cur = next_node
    return prev

检测链表是否有环（快慢指针法）

def hasCycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

5.5 链表的优缺点

优点：
- 插入、删除操作时间复杂度为 O(1)（已知节点的前驱时）。
- 动态申请内存，不需要预先分配空间。
- 缺点：
- 查找效率低，访问第 k 个元素需要 O(k) 时间。
- 需要额外的指针（引用）空间。

5.6 适用场景

需要频繁插入、删除元素，且对随机访问效率要求不高。
实现栈、队列、哈希表的链式结构等。

5.7 小结表

链表类型	结构特性	优点	缺点	典型应用
单链表	单向指针	内存利用高，插删快	只能单向遍历	基础链表、哈希冲突链表
双向链表	前后双指针	可双向遍历，灵活插删	空间占用更大	LRU缓存、队列实现
循环链表	尾节点指向头节点	适合循环处理	需防止死循环	循环队列、约瑟夫环

二叉树

图论

200. 岛屿数量

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid: return 0

        def dfs(i, j):
            if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] == "0":
                return
            
            grid[i][j] = "0"
            dfs(i + 1, j)
            dfs(i - 1, j)
            dfs(i, j - 1)
            dfs(i, j + 1)

        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == "1":
                    dfs(i, j)
                    count += 1
        return count

回溯

你问得非常好！这其实是很多同学在刷题/面试“回溯法”时的核心困惑：

“我怎么知道该怎么写 backtrack？参数、入口怎么设计？是不是有一套模板？”

答案是：有的！
回溯（Backtracking）问题本质是“递归枚举所有方案”，所以其实有一套“通用设计模板”。
下面我用通俗+实用的方式帮你总结，掌握之后你遇到大部分回溯题都能“对号入座”。

⸻

回溯法的通用模板

最通用的结构：

def backtrack(参数):
if 终止条件:
记录/返回结果
return

for 选择 in 当前所有可选集合:
    做选择
    backtrack(新的参数)
    撤销选择

拆解说明：
• 参数设计：
你需要保存“当前走到哪一步”，比如：
• 当前的路径（已经选了哪些元素，path）
• 当前决策的位置/下标/层数（start, index 等）
• 是否有标记（如 used[]）
• 递归出口：
到达题目要求的“最终状态”时，收集结果，然后 return
• 枚举选择：
当前这一步可以选哪些元素？常见有：
• 全排列：所有没用过的数
• 子集/组合：当前及后面的数
• 字符组合题：当前数字对应的所有字母
• 做选择：
path.append(x) / 标记 used[] / 参数推进
• 撤销选择：
path.pop() / 恢复 used[] / 恢复现场

⸻

三个经典例子拆解
全排列（46）
• 参数：path（路径），隐含每层深度是“选了几个数”
• 递归终止条件：len(path) == len(nums)
• for循环：所有未被用过的数
• 做选择/撤销：append/pop
子集（78）
• 参数：start（起始下标），path（路径）
• 终止条件：无（每一步都收集 path 到结果）
• for循环：从 start 到 nums 末尾（避免重复）
• 做选择/撤销：append/pop
电话号码的字母组合（17）
• 参数：index（数字下标），path（路径）
• 终止条件：index == len(digits)
• for循环：当前数字对应的所有字母
• 做选择/撤销：append/pop

⸻

怎么从题目出发推导 backtrack 参数？

问自己两个问题：
1. 当前“状态”需要什么？（比如：走了哪些数、当前下标等）
2. 下一步的“选择空间”由什么决定？（比如：是所有没选的？还是后面没选的？还是数字对应的字母？）

用这两点去设计 backtrack 的参数和 for 循环的内容。

⸻

“怎么写出 backtrack(0, [])”？
• 起点（入口）：一般是“啥都没选”或“从0开始”
• 比如 path=[]、start=0、index=0、used全False 等
• 每层递归负责一件事：选下一个/枚举下一个/扩展可能性

⸻

典型题目的模板对比（总结表）

题目递归参数 for循环枚举终止条件做选择撤销选择
全排列46 path, used[] 所有未被用数 len(path)==n append,used pop,used
子集78 start, path 从start到n-1 每步都res.append append pop
电话号码17 index, path 当前数字的所有字母 index==len(digits) append pop

⸻

一句话口诀

“递归+for枚举，每层决定选什么；递归到底收结果，回溯撤销试别的。”

⸻

总结步骤
1. 明确“路径”与“选择列表”
2. 设计 backtrack 的参数（一般有 path/索引/used 标记等）
3. 确定递归终止条件
4. 编写 for 循环枚举选择，递归进入下一层
5. 递归回来后撤销选择

⸻

如果你有具体的题目，想让我现场“模板化”分析，也可以直接发过来！
如果你还想看几道题的递归展开/流程，也随时可以说~

46. 全排列

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res = []

        def backtrace(path):
            if len(path) == len(nums):
                res.append(path[:])
                return
            
            for num in nums:
                if num in path:
                    continue
                path.append(num)
                backtrace(path)
                path.pop()
        
        backtrace([])
        return res

78. 子集

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        path = []
        def backtrace(start):
            res.append(path[:])
            for i in range(start, len(nums)):
                path.append(nums[i])
                backtrace(i+1)
                path.pop()

        backtrace(0)
        return res

17. 电话号码的字母组合

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if digits == "": return []

        phone = {
            "2": "abc", "3": "def", "4": "ghi",
            "5": "jkl", "6": "mno", "7": "pqrs",
            "8": "tuv", "9": "wxyz"
        }
        res = []

        def backtrace(index, string):
            if index == len(digits):
                res.append("".join(string))
                return

            for s in phone[digits[index]]:
                string.append(s)
                backtrace(index + 1, string)
                string.pop()

        backtrace(0, [])
        return res

39. 组合总和

这些题目多多少少都有点绕

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        n = len(candidates)
        candidates.sort()
        res = []

        def backtrace(s, path, target_left):
            if target_left == 0:
                res.append(path[:])
                return

            for i in range(s, n):
                if candidates[i] > target_left:
                    break

                path.append(candidates[i])
                backtrace(i, path, target_left - candidates[i])
                path.pop()
            
        backtrace(0, [], target)
        return res

举一个例子

candidates = [2, 3, 6, 7]
target = 7


backtrack(0, [], 7)
  └─ 选 2 → path = [2], target_left = 5
      └─ backtrack(0, [2], 5)
          └─ 选 2 → path = [2,2], target_left = 3
              └─ backtrack(0, [2,2], 3)
                  └─ 选 2 → path = [2,2,2], target_left = 1
                      └─ backtrack(0, [2,2,2], 1)
                          └─ 选 2 → 2 > 1 剪枝
                          └─ 选 3 → 3 > 1 剪枝
                  └─ 撤销 2 → path = [2,2]
                  └─ 选 3 → path = [2,2,3], target_left = 0 ✅ 收集结果
                  └─ 撤销 3 → path = [2,2]
              └─ 撤销 2 → path = [2]
              └─ 选 3 → path = [2,3], target_left = 2
                  └─ backtrack(1, [2,3], 2)
                      └─ 选 3 → 3 > 2 剪枝
              └─ 撤销 3 → path = [2]
              └─ 选 6 → 6 > 5 剪枝
              └─ 选 7 → 7 > 5 剪枝
      └─ 撤销 2 → path = []
      └─ 选 3 → path = [3], target_left = 4
          └─ backtrack(1, [3], 4)
              └─ 选 3 → path = [3,3], target_left = 1
                  └─ backtrack(1, [3,3], 1)
                      └─ 选 3 → 3 > 1 剪枝
              └─ 撤销 3 → path = [3]
              └─ 选 6 → 6 > 4 剪枝
              └─ 选 7 → 7 > 4 剪枝
      └─ 撤销 3 → path = []
      └─ 选 6 → path = [6], target_left = 1
          └─ backtrack(2, [6], 1)
              └─ 选 6 → 6 > 1 剪枝
              └─ 选 7 → 7 > 1 剪枝
      └─ 撤销 6 → path = []
      └─ 选 7 → path = [7], target_left = 0 ✅ 收集结果
      └─ 撤销 7 → path = []

22. 括号生成

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res = []

        def backtrace(path, left, right):
            if len(path) == 2*n:
                res.append(path)
                return

            if left < n:
                backtrace(path + '(', left + 1, right)
            if right < left:
                backtrace(path + ')', left, right + 1)
        
        backtrace("", 0, 0)
        return res

n = 3

backtrack("", 0, 0)
  -> "("
    -> "(("
      -> "((("
        -> "((()"
          -> "((())"
            -> "((()))" ✅
          -> "(()("
            -> "(()()"
              -> "(()())" ✅
            -> "(())("
              -> "(())()" ✅
    -> "()"
      -> "()("
        -> "()()("
          -> "()()()" ✅
        -> "()(()"
          -> "()(())" ✅

79. 单词搜索

这些题目完全没有头绪

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        m, n = len(board), len(board[0])

        def backtrace(i, j, k):
            if not ((0 <= i < m) and (0 <= j < n)):
                return False
            if board[i][j] != word[k]:
                return False
            if k == len(word) - 1:
                return True
            
            tmp, board[i][j] = board[i][j], "#"
            res = (backtrace(i - 1, j, k + 1) or
                    backtrace(i, j - 1, k + 1) or 
                    backtrace(i, j + 1, k + 1) or 
                    backtrace(i + 1, j, k + 1))
            board[i][j] = tmp
            return res

        for i in range(m):
            for j in range(n):
                if backtrace(i, j, 0):
                    return True
        
        return False

131. 分割回文串

51. N 皇后

二分查找

35. 搜索插入位置

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        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 left

74. 搜索二维矩阵

将上面的一维转化为二维来理解即可

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])
        left, right = 0, m * n - 1

        while left <= right:
            mid = (left + right) // 2
            row, col = mid // n, mid % n
            if matrix[row][col] == target:
                return True
            elif matrix[row][col] < target:
                left = mid + 1
            else:
                right = mid - 1
        return False

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

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        left, right = 0, n - 1

        flag = 0
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                flag = 1
                break
            elif nums[mid] < target:
                left += 1
            else:
                right -= 1
        
        if flag == 0:
            return [-1, -1]
        else:
            min_index = mid
            max_index = mid
            while min_index >= 0 and min_index <= n-1 and nums[min_index] == target:
                min_index -= 1
            min_index += 1
            while max_index >= 0 and max_index <= n-1 and nums[max_index] == target:
                max_index += 1
            max_index -= 1
            return [min_index, max_index]


'''
# 可参考 GPT
class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def findLeft():
            left, right = 0, len(nums) - 1
            while left <= right:
                mid = (left + right) // 2
                if nums[mid] < target:
                    left = mid + 1
                else:
                    right = mid - 1
            return left
        
        def findRight():
            left, right = 0, len(nums) - 1
            while left <= right:
                mid = (left + right) // 2
                if nums[mid] <= target:
                    left = mid + 1
                else:
                    right = mid - 1
            return right
        
        left_idx = findLeft()
        right_idx = findRight()
        
        # 检查是否 target 存在
        if left_idx <= right_idx:
            return [left_idx, right_idx]
        else:
            return [-1, -1]
'''

33. 搜索旋转排序数组

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums)-1

        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                return mid
            
            if nums[left] <= nums[mid]:
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1
            
        return -1

153. 寻找旋转排序数组中的最小值

这些二分法的边界很绕？

class Solution:
    def findMin(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1

        while left < right:
            mid = (left + right) // 2

            if nums[mid] > nums[right]:
                left = mid + 1
            else:
                right = mid
            
        return nums[left]

4. 寻找两个正序数组的中位数

hard，比较难，没怎么捣鼓明白

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        # 如果二分长数组，可能导致划分位置超出短数组范围，甚至越界或逻辑错误。
        if len(nums1) > len(nums2):
            nums1, nums2 = nums2, nums1
        
        m, n = len(nums1), len(nums2)
        left, right = 0, m
        while left <= right:
            i = (left + right) // 2
            j = (m + n + 1) // 2 - i

            maxleft1 = nums1[i-1] if i!=0 else float("-inf")
            minright1 = nums1[i] if i!=m else float("inf")

            maxleft2 = nums2[j-1] if j!=0 else float("-inf")
            minright2 = nums2[j] if j!=n else float("inf")

            if maxleft1 <= minright2 and maxleft2 <= minright1:
                if (m + n) % 2 == 0:
                    return (max(maxleft1, maxleft2) + min(minright1, minright2)) / 2
                else:
                    return max(maxleft1, maxleft2)
            elif maxleft1 > minright2:
                right -= 1
            else:
                left += 1

栈

20. 有效的括号

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        for _s in s:
            if _s == "(" or _s == "[" or _s == "{":
                stack.append(_s)
            else:
                if _s == ")" and stack and stack[-1] == "(":
                    stack.pop()
                elif _s == "]" and stack and stack[-1] == "[":
                    stack.pop()
                elif _s == "}" and stack and stack[-1] == "{":
                    stack.pop()
                else:
                    return False
        
        return not stack

394. 字符串解码

需要多看一下

class Solution:
    def decodeString(self, s: str) -> str:
        count_stack = []
        string_stack = []
        num = 0
        string = ""

        for _s in s:
            if _s.isdigit():
                num = num * 10 + int(_s)
            elif _s == "[":
                count_stack.append(num)
                string_stack.append(string)
                num = 0
                string = ""
            elif _s == "]":
                _num = count_stack.pop()
                prev_str = string_stack.pop()
                string = prev_str + string * _num
            else:
                string += _s
        return string

739. 每日温度

需要多看一下

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        ans = [0] * n
        stack = []

        for i, t in enumerate(temperatures):
            while stack and t > temperatures[stack[-1]]:
                pre = stack[-1]
                ans[pre] = i - pre
                stack.pop()
            stack.append(i)
        
        return ans

84. 柱状图中最大的矩形

很难啊，hard，得好好看看

🌟 先复述你的疑问

你说得很好，大致是：

如果右边还有一个更低或等高的柱子，为什么我们不等到它再去计算矩形？提前弹出是不是会漏掉更大的矩形？

⸻

🌟 关键点：单调栈为什么正确

我们先想象一根柱子 heights[i]：
• 它左边已经有一堆柱子（比它高或相等），这些柱子的最大矩形都可以扩展到这里。
• 当前柱子 heights[i] 就是它们的右边界了。

💡 因为：
• 如果有更矮或等高的柱子出现在当前柱子右边，这些柱子自己会在后续被处理。
• 当前柱子或更矮的柱子不可能帮助之前栈顶的柱子扩展出更大面积，因为高度限制住了。

⸻

🌟 形象理解：矩形不能跨过它右边第一个比它矮的柱子

假设柱子序列：

高高高矮

对于前面的高柱子，它们的矩形最多扩展到这根矮柱子的位置，因为再往右，它们就被挡住了（矩形高度被卡住）。

如果右边还有更低柱子，或等高柱子，那：
• 更低柱子：本柱子的矩形本来就到不了那么远，因为先被现在这根矮柱子截断了。
• 等高柱子：等高柱子不影响当前矩形的右边界，因为你是在比它矮的柱子这里截断的，而等高的柱子在后面会自己被处理。

⸻

🌟 提前弹出会漏掉更优解吗？不会！

每根柱子：
✅ 都只在它的右边第一个更矮柱子处被结算最大矩形面积。

✅ 如果右边还有更矮柱子，将来也会把它的矩形算出来，它自己的矩形高度更小，宽度或许更大，但高已经不可能再比之前高了（之前更高的柱子被先算掉了）。

✅ 面积 = 宽度 × 高度
高被右边第一个更矮柱子截断后，继续向右的矩形高度只能更小。即使宽度变大，总面积也不可能更大，因为高度更小了。

⸻

🌟 举个例子：

假设 heights = [3,3,3,1]

[0,3,3,3,1,0]

•	当到 1 时，栈里的 3 全部被弹出。
•	每个 3 的矩形最多只能扩到 index=3 的位置。
•	右边那个更矮的柱子（1）并不能帮这些 3 扩展更远了，因为高度被卡住。

如果我们不弹出，等着 0 的时候再去算，结果是一样的，只不过逻辑上变复杂，而且效率低。

⸻

🌟 总结

✅ 单调栈弹出时，当前柱子就是之前柱子的右边第一个更矮的柱子。
✅ 右边还有没有更矮或等高柱子不影响，因为之前柱子的矩形只能扩到这里为止。
✅ 弹出时面积是它能覆盖到的最大矩形面积。
✅ 每根柱子都会在它的“生死时刻”被结算，保证没有漏算。

⸻

🌟 图示理解（简单画一下矩形边界）

柱子高度: 3 3 3 1
位置索引: 0 1 2 3

到柱子 1 时：
• 三根 3 只能扩到它左边能到的位置（0），右边到柱子 1。
• 矩形高度 = 3，宽度 = 3。

柱子 1 以后，再高的矩形都扩不过去了，因为被 1 卡住了。

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        heights = [0] + heights + [0]
        stack = []
        n = len(heights)
        max_area = 0

        for i in range(n):
            while stack and heights[i] < heights[stack[-1]]:
                h = heights[stack.pop()]
                w = i - stack[-1] - 1
                max_area = max(max_area, w * h)
            stack.append(i)
        
        return max_area

堆

215. 数组中的第K个最大元素

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        import heapq
        min_heap = []

        for num in nums:
            heapq.heappush(min_heap, num)
            if len(min_heap) > k:
                heapq.heappop(min_heap)
        
        return min_heap[0]

347. 前 K 个高频元素

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        import heapq
        from collections import Counter

        freq = Counter(nums)
        min_heap = []
        for num, count in freq.items():
            heapq.heappush(min_heap, (count, num))
            if len(min_heap) > k:
                heapq.heappop(min_heap)
        
        return [num for count, num in min_heap]

295. 数据流的中位数

此题为 hard

class MedianFinder:

    def __init__(self):
        self.maxheap_small = []  # 最大堆：存较小一半，取最大（用负数实现）
        self.minheap_large = []  # 最小堆：存较大一半，取最小
        import heapq

    def addNum(self, num: int) -> None:
        # 先构建最大堆
        heapq.heappush(self.maxheap_small, -num)

        # 最大堆的最大值 小于 最小堆的最小值
        # 这样 最大堆的最大值 和 最小堆的最小值 就是中间的两个数字
        if self.maxheap_small and self.minheap_large and \
            -self.maxheap_small[0] > self.minheap_large[0]:
            val = -heapq.heappop(self.maxheap_small)
            heapq.heappush(self.minheap_large, val)

        # 注意，由于上述的修改，可能导致两个堆数量不一样，所以要进一步调整
        if len(self.maxheap_small) > len(self.minheap_large) + 1:
            val = -heapq.heappop(self.maxheap_small)
            heapq.heappush(self.minheap_large, val)
        elif len(self.maxheap_small) < len(self.minheap_large):
            val = -heapq.heappop(self.minheap_large)
            heapq.heappush(self.maxheap_small, val)


    def findMedian(self) -> float:
        if len(self.maxheap_small) > len(self.minheap_large):
            return -self.maxheap_small[0]
        else:
            return (-self.maxheap_small[0] + self.minheap_large[0]) / 2


# Your MedianFinder object will be instantiated and called as such:
# obj = MedianFinder()
# obj.addNum(num)
# param_2 = obj.findMedian()

贪心算法

当然可以，以下是一个适用于博客的 Markdown 格式内容，简要介绍了**贪心算法（Greedy Algorithm）**的概念、核心思想、适用场景，并附有一个经典例题作为示例：

⸻

什么是贪心算法？一文理解 Greedy Algorithm

在解决算法问题时，贪心算法（Greedy Algorithm）是一种常用且高效的策略，它通过每一步都做出当前看起来最优的选择，希望最终得到全局最优解。

⸻

📌 一、贪心算法的定义

贪心算法是一种在每一步选择中都采取在当前状态下最优或最有利的选择的算法，而不从整体上进行考虑。这种算法的核心是：

局部最优 -> 全局最优

但需要注意的是：不是所有问题都适合贪心算法，它只在某些具有贪心性质（Greedy Property）的问题中能得到正确的最优解。

⸻

🧠 二、贪心算法的核心思想
1. 贪心选择性质：通过局部最优选择，能得到全局最优解。
2. 无后效性：某一步的选择不会影响后续的选择，即未来的决策不受过去状态影响。
3. 最优子结构：一个问题的最优解包含其子问题的最优解。

⸻

💡 三、贪心算法的基本模板

通用贪心算法框架

def greedy_algorithm(data):
# 初始化答案
result = 0

# 排序（如果需要）
data.sort()

for item in data:
    if 满足贪心选择条件(item):
        做出当前选择
        更新答案或状态

return result

⸻

📘 四、经典例题：121. 买卖股票的最佳时机

题目简述：

你只能选择一天买入股票，并选择未来某一天卖出，返回你能获得的最大利润。

贪心思路：
• 记录下到目前为止的最低价格。
• 对每一天，计算“今天卖出”带来的利润，并和当前最大利润作比较。
• 每一步只做当前最优：更新最低价 / 最大利润。

Python 实现：

class Solution:
def maxProfit(self, prices: List[int]) -> int:
min_price = float(‘inf’)
max_profit = 0

    for price in prices:
        if price < min_price:
            min_price = price
        else:
            max_profit = max(max_profit, price - min_price)

    return max_profit

⸻

✅ 五、常见的贪心算法应用场景

问题类型经典例题
区间覆盖 435. 无重叠区间
最小路径 Dijkstra 算法（贪心 + 堆）
钱币找零 322. 零钱兑换（注意：有些不适合贪心）
Huffman 编码优先队列实现最优前缀编码
活动安排 452. 用最少数量的箭引爆气球

⸻

⚠️ 六、贪心算法的注意事项
• 贪心算法并不保证所有问题都能得到最优解。
• 使用前必须验证问题是否满足贪心选择性质和无后效性。
• 对于某些问题（如背包问题），贪心算法可能得到次优解，此时应使用动态规划。

⸻

📎 七、小结

贪心算法是一种高效、直观的解题方法，适用于许多实际问题。然而，它并非万能，在使用之前需要对问题性质进行深入分析，确保贪心策略是合理且正确的。

⸻

如果你觉得贪心算法有点抽象，不妨从简单的题目练起，比如买卖股票、活动安排、零钱兑换等，逐步建立直觉！

📘 推荐练习：
• LeetCode 121. 买卖股票的最佳时机
• LeetCode 455. 分发饼干
• LeetCode 435. 无重叠区间

⸻

如需我为你生成博客封面图、流程图或拓展成系列文章，可以继续告诉我！

121. 买卖股票的最佳时机

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        min_price = float("inf")
        max_profit = 0

        for price in prices:
            if price < min_price:
                min_price = price
            else:
                profit = price - min_price
                max_profit = max(max_profit, profit)
    
        return max_profit

55. 跳跃游戏

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        farthest = 0
        n = len(nums)

        for i in range(n):
            if i > farthest:
                return False
            else:
                farthest = max(farthest, i + nums[i])

        return True

45. 跳跃游戏II

class Solution:
    def jump(self, nums: List[int]) -> int:
        farthest = 0
        current_end = 0
        n = len(nums)
        step = 0

        for i in range(n - 1):
            farthest = max(farthest, i+nums[i])
            if i >= current_end:
                step += 1
                current_end = farthest
        
        return step

763. 划分字母区间

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        last = {char: i for i, char in enumerate(s)}
        start = end = 0
        n = len(s)
        res = []

        for i in range(n):
            end = max(end, last[s[i]])
            if i == end:
                res.append(end - start + 1)
                start = i + 1

        return res

动态规划

70. 爬楼梯

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 1:
            return 1

        dp = [0 for _ in range(n+1)]
        dp[0] = 1
        dp[1] = 1
        for i in range(2, n+1):
            dp[i] = dp[i - 1] + dp[i - 2]
        
        return dp[-1]

118. 杨辉三角

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        res = []

        for i in range(numRows):
            dp = [1] * (i+1)
            for j in range(1, i):
                dp[j] = res[i-1][j-1] + res[i-1][j]
            res.append(dp)
        
        return res

198 打家劫舍

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 0: return 0
        if n == 1: return nums[0]
        if n == 2: return max(nums[0], nums[1])


        dp = [0] * (n)
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])

        for i in range(2, n):
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
        
        return dp[-1]

279. 完全平方数

class Solution:
    def numSquares(self, n: int) -> int:
        dp = [float("inf")] * (n + 1)
        if n == 1: return 1
        if n == 2: return 2
        dp[0] = 0
        dp[1] = 1

        for i in range(2, n + 1):
            for j in range(1, int(math.sqrt(i)) + 1):
                dp[i] = min(dp[i], dp[i - j * j] + 1)
        
        return dp[-1]

322. 零钱兑换

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [float("inf")]  * (amount + 1)

        dp[0] = 0
        for i in range(1, amount + 1):
            for coin in coins:
                if i - coin >= 0:
                    dp[i] = min(dp[i], dp[i - coin] + 1)
            
        return dp[-1] if dp[-1] != float("inf") else -1

139. 单词拆分

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        n = len(s)
        dp = [False] * (n + 1)
        dp[0] = True

        for i in range(1, n + 1):
            for word in wordDict:
                n_word = len(word)
                if s[:i-n_word] + word == s[:i]:
                    dp[i] = dp[i] or dp[i - n_word]
        return dp[-1]

300. 最长递增子序列

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [1] * (n)

        for i in range(1, n):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return max(dp)

152. 乘积最大子数组

相对较难

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        n = len(nums)
        min_dp = [0] * n
        max_dp = [0] * n

        min_dp[0] = max_dp[0] = res = nums[0]
        for i in range(n):
            max_dp[i] = max(nums[i], min_dp[i - 1] * nums[i], max_dp[i - 1] * nums[i])
            min_dp[i] = min(nums[i], min_dp[i - 1] * nums[i], max_dp[i - 1] * nums[i])
            res = max(res, max_dp[i])
        
        return res

416. 分割等和子集

相对较难

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        if total % 2 != 0:
            return False
        
        half = total // 2
        dp = [False] * (half + 1)
        dp[0] = True
        for num in nums:
            for j in range(half, num - 1, -1):
                dp[j] = dp[j] or dp[j - num]

        return dp[-1]

32. 最长有效括号

hard 题目，不是很会，有点复杂

我们正在处理形如 …)) 的情况：

if s[i] == ')' and s[i - 1] == ')':
    if s[i - dp[i - 1] - 1] == '(':
        dp[i] = dp[i - 1] + 2
        if i - dp[i - 1] - 2 >= 0:
            dp[i] += dp[i - dp[i - 1] - 2]

🔍 每一部分解释

i - dp[i - 1] - 2 是谁？

我们之前说过：
• dp[i - 1] 是以 i-1 结尾的合法括号长度
• i - dp[i - 1] - 1 就是找到这段合法括号左边的那个字符，即我们要匹配的 ‘(’

那 i - dp[i - 1] - 2 就是：

➡️ 这对括号前面的那个位置

为什么还要加上 dp[i - dp[i - 1] - 2]？

如果这之前也有合法括号，我们应该把它们一起接上。

举个更复杂的例子你就能看清楚这个用意：

📌 示例解释

示例字符串：

s = “()(()())”
下标: 01234567

我们逐步来算：
• dp[1] = 2 → ()
• dp[6] = 4 → (())
• 到 i = 7，s[7] == ‘)’，且 s[6] == ‘)’，满足我们这类情况

我们继续：
• dp[6] = 4，说明 s[3:6] = (()) 是合法的
• 看 s[2] = ‘(’，满足匹配 ✅
• 此时：

dp[7] = dp[6] + 2 = 4 + 2 = 6

但别忘了，在 s[0:1] = () 也是合法的！

那么 dp[1] = 2 应该也算进来：

dp[7] += dp[1] # 所以最终 dp[7] = 8

也就是说：

dp[7] = dp[6] + 2 + dp[1] = 4 + 2 + 2 = 8

这就是那一行代码的作用：

if i - dp[i - 1] - 2 >= 0:
dp[i] += dp[i - dp[i - 1] - 2]

✅ 总结作用
• 这一句是为了补上：“当前新配对的括号之前的那段合法括号”。
• 有点像拼接多个合法区间：(…(()))…)
• 如果不加这句，算法就只会算最后一段，漏掉前面连接的部分。

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        n = len(s)
        dp = [0] * n
        max_len = 0

        for i in range(1, n):
            if s[i] == ")":
                if s[i - 1] == '(':
                    dp[i] = (dp[i - 2] if i >= 2 else 0) + 2
                else:
                    prev_index = i - dp[i - 1] - 1
                    if prev_index >= 0 and s[prev_index] == "(":
                        dp[i] = dp[i - 1] + 2
                        if prev_index - 1 >= 0:
                            dp[i] += dp[prev_index - 1]
                max_len = max(max_len, dp[i])
        return max_len

多维动态规划

动态规划（Dynamic Programming, DP）是解决最优化问题的重要工具，其中多维动态规划是指使用二维或更高维度的状态数组 dp[i][j][k]… 来描述状态转移过程。这种方法常用于需要同时记录多个变量维度的子问题状态。

6.1 多维 DP 的定义

当问题的最优解依赖于多个变量时，我们可以使用多维数组来表示状态。例如：

dp[i][j] 表示状态依赖于两个维度，如位置 i 与资源限制 j
dp[i][j][k] 表示状态依赖三个变量

多维 DP 的关键在于：

每一维都代表一个对最终状态有影响的重要变量。

6.2 多维 DP 的常见场景

场景	示例题目	状态定义
网格路径问题	LeetCode 62/63	`dp[i][j]` 表示走到 (i,j) 的路径数
背包问题	LeetCode 494/416	`dp[i][j]` 表示前 i 个物品能否凑成和为 j
记忆化搜索（多个参数）	LeetCode 10（正则表达式匹配）	`dp[i][j]` 表示字符串 i 和模式 j 是否匹配
区间 DP	LeetCode 312（戳气球）	`dp[i][j]` 表示开区间 (i, j) 的最大得分
博弈类问题	LeetCode 877	`dp[i][j]` 表示从区间 [i,j] 中选择的最大差值

6.3 多维 DP 的编写步骤

明确状态定义

每一维代表的问题子状态是什么？

确定状态转移方程

当前状态如何从已有状态推导？是否存在边界情况？

初始化边界条件

dp[0][0] = ... 取决于问题含义

遍历顺序设计

是否有顺序要求？

6.4 示例：二维网格路径（简要）

# dp[i][j] 表示从 (0,0) 到 (i,j) 的路径数
for i in range(m):
    for j in range(n):
        dp[i][j] = dp[i-1][j] + dp[i][j-1]

6.5 空间优化技巧

在某些问题中，如果状态 dp[i][j] 只依赖于 dp[i-1][j] 或 dp[i][j-1]，可以使用滚动数组压缩空间：

dp = [1] * n
for _ in range(1, m):
    for j in range(1, n):
        dp[j] += dp[j - 1]

对于三维及以上的 DP，有时可以按状态转移图依赖关系降维或合并状态，提升效率。

6.6 多维 DP 的小结表

特点	描述
状态维度	用多个维度描述状态变量依赖
复杂度	时间和空间复杂度随维度提升快速增长
空间优化	滚动数组或状态合并可降维
应用广泛	网格、背包、区间、博弈、多序列对比等

6.7 常见多维 DP 题型推荐

类型	题目编号	简要说明
网格类	62、63、64	路径计数、障碍路径、最小路径和
背包类	494、416、322	子集和、能否分割、硬币兑换
区间类	312、1000	戳气球、石头合并
博弈类	486、877	先手策略、最大差值
字符串类	10、44、115	正则匹配、通配符匹配、子序列计数

多维动态规划

62. 不同路径

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[1] * n for _ in range(m)]

        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
        
        return dp[-1][-1]

64. 最小路径和

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [[0] * n for _ in range(m)]

        # 初始化 0,0
        dp[0][0] = grid[0][0]
        # 初始化第一行
        for i in range(1, n):
            dp[0][i] = dp[0][i - 1] + grid[0][i]
        # 初始化第一列
        for j in range(1, m):
            dp[j][0] = dp[j - 1][0] + grid[j][0]

        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]

        return dp[-1][-1]

5. 最长回文子串

class Solution:
    def longestPalindrome(self, s: str) -> str:
        # dp[i][j] 表示 s[i:j+1] 是否为回文
        # 状态转移方程
        # dp[i][j]
        # 1. s[i]==s[j] and dp[i+1][j-1]
        # 2. j - i <= 1
        n = len(s)
        res = ""
        dp = [[False] * n for _ in range(n)]
        for j in range(n):
            for i in range(j + 1):
                if s[i]==s[j] and (j - i <= 2 or dp[i+1][j-1]):
                    dp[i][j] = True
                    if j - i + 1 > len(res):
                        res = s[i:j+1]
        return res

1143. 最长公共子序列

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m, n = len(text1), len(text2)
        dp = [[0] * (n+1) for _ in range(m+1)]

        for i in range(1, m+1):
            for j in range(1, n+1):
                if text1[i-1] == text2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        
        return dp[-1][-1]

72. 编辑距离

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]

        for i in range(m + 1):
            dp[i][0] = i
        for j in range(n + 1):
            dp[0][j] = j

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if word1[i-1] == word2[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = min(
                        dp[i-1][j] + 1,
                        dp[i][j-1] + 1,
                        dp[i-1][j-1] + 1,
                    )
        return dp[m][n]

技巧题

136. 只出现一次的数字

给你一个非空整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

示例 1 ：输入：nums = [2,2,1] 输出：1
示例 2 ：输入：nums = [4,1,2,1,2] 输出：4
示例 3 ：输入：nums = [1] 输出：1

解题思路：

一个数和自己异或等于 0，一个数和 0 异或等于它本身。异或满足交换律与结合律。

性质总结：

a ^ a = 0
a ^ 0 = a
a ^ b ^ a = (a ^ a) ^ b = 0 ^ b = b

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        pre = 0

        for num in nums:
            pre ^= num
        return pre

169. 多数元素

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数大于 $\frac{n}{2}$ 的元素。你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：输入：nums = [3,2,3] 输出：3
示例 2：输入：nums = [2,2,1,1,1,2,2] 输出：2

解题思路：

最经典高效的解法是摩尔投票算法（Boyer-Moore Majority Vote Algorithm）：

初始化一个候选元素 candidate 和一个计数器 count。并遍历数组：

若当前元素等于候选元素，则 count++；
否则，count–；
若 count 归零，则更换候选元素为当前元素，并重置计数器为 1。
最终的候选元素即为所求的多数元素。

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        count = 0
        candidate = None

        for num in nums:
            if count == 0:
                candidate = num
            count += 1 if num == candidate else -1
        
        return candidate

75. 颜色分类

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。必须在不使用库内置的 sort 函数的情况下解决这个问题。

示例 1：输入：nums = [2,0,2,1,1,0] 输出：[0,0,1,1,2,2]
示例 2：输入：nums = [2,0,1] 输出：[0,1,2]

解题思路：

双指针（三指针）法，设置三个指针：

left 指针指向下一个放置 0 的位置。
right 指针指向下一个放置 2 的位置。
current 指针遍历数组。

遍历规则：

若当前元素为 0，则与 left 位置元素交换，left++, current++。
若当前元素为 2，则与 right 位置元素交换，right--（current 不动，检查交换后的元素）。
若当前元素为 1，则直接 current++。

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        low, i, high = 0, 0, len(nums) - 1

        while i <= high:
            if nums[i] == 0:
                nums[i], nums[low] = nums[low], nums[i]
                i += 1
                low += 1
            elif nums[i] == 1:
                i += 1
            else:
                nums[i], nums[high] = nums[high], nums[i]
                high -= 1

31. 下一个排列

整数数组的一个排列就是将其所有成员以序列或线性顺序排列。例如，arr = [1,2,3]，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1]。整数数组的下一个排列是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的下一个排列就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。
例如，arr = [1,2,3] 的下一个排列是 [1,3,2]。
类似地，arr = [2,3,1] 的下一个排列是 [3,1,2]。
而 arr = [3,2,1] 的下一个排列是 [1,2,3]，因为 [3,2,1] 不存在一个字典序更大的排列。
给你一个整数数组 nums ，找出 nums 的下一个排列。必须原地修改，只允许使用额外常数空间。

示例 1：输入：nums = [1,2,3] 输出：[1,3,2]
示例 2：输入：nums = [3,2,1] 输出：[1,2,3]
示例 3：输入：nums = [1,1,5] 输出：[1,5,1]

解题思路：

从后向前找到第一个满足 nums[i] < nums[i+1] 的数，记下标为 i。
如果未找到，表示序列为降序排列，则直接翻转整个序列。
如果找到了位置 i，则从数组末尾向前找到第一个比 nums[i] 大的数，记为位置 j。
交换位置 i 和位置 j 的元素。
翻转位置 i+1 到数组末尾的部分，使其变为升序。

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        n = len(nums)
        i = n - 2
        
        while i >= 0 and nums[i] >= nums[i+1]:
            i -= 1

        if i >= 0:
            j = n - 1
            while nums[j] <= nums[i]:
                j -= 1
            nums[i], nums[j] = nums[j], nums[i]
        
        left, right = i+1, n-1
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

这个比较难理解，需要加一个例子来理解，假设数组是：nums = [1, 2, 7, 4, 3, 1]

步骤 1：从后往前，找到第一个满足nums[i] < nums[i+1]的位置：

nums = [1, 2, 7, 4, 3, 1]
              ↑
            nums[1]=2 < nums[2]=7（成立）

但我们要的是最右边的符合条件的位置：
nums[2]=7 > nums[3]=4 不满足
nums[3]=4 > nums[4]=3 不满足
nums[4]=3 > nums[5]=1 不满足
nums[1]=2 < nums[2]=7 满足，位置为 i = 1

步骤 2：从数组末尾往前找第一个比nums[i]大的数字：nums[i]=nums[1]=2，从后往前找第一个比2大的：nums[5]=1 不满足。nums[4]=3 满足，找到位置 j = 4
步骤 3：交换 nums[i] 和 nums[j]：交换 nums[1] 和 nums[4]，数组变成：nums = [1, 3, 7, 4, 2, 1]
步骤 4：翻转位置 i+1 到数组末尾的所有元素：翻转 nums[2] 到 nums[5] 部分 [7,4,2,1] -> [1,2,4,7]，nums = [1, 3, 1, 2, 4, 7]。因此最终答案：[1, 3, 1, 2, 4, 7]

287. 寻找重复数

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。假设 nums 只有一个重复的整数，返回这个重复的数。你设计的解决方案必须不修改数组 nums 且只用常量级 O(1) 的额外空间。

示例 1：输入：nums = [1,3,4,2,2] 输出：2
示例 2：输入：nums = [3,1,3,4,2] 输出：3
示例 3：输入：nums = [3,3,3,3,3] 输出：3

解题思路：（快慢指针法）

由于数组中的数字范围在 1 到 n，可以把数组看作一个特殊的链表结构，其中数组的值表示链表的下一个节点。利用“快慢指针”找到链表中的环，环的入口即为重复的数。
具体步骤：

初始慢指针和快指针均指向数组开头。
慢指针每次走一步，快指针每次走两步，直到相遇。
然后再用两个指针分别从起点和相遇点同时出发，每次走一步，再次相遇的位置即为环入口（重复数字）

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        slow = fast = nums[0]
        while True:
            slow = nums[slow]
            fast = nums[nums[fast]]
            if slow == fast:
                break
        
        slow = nums[0]
        while slow != fast:
            slow = nums[slow]
            fast = nums[fast]
        return slow

本文由 Yonghui Wang 创作，采用知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Jun 24, 2025 01:34 pm

LeetCode-hot100

1. 哈希表

1.1 python 字典

1.2 defaultdict

1.3 Counter

2. 双指针

3. 滑动窗口

4. 动态规划

4.2 动态规划的解题步骤

4.3 动态规划的解题步骤

4.4 总结表

1.1 python 字典

1.2 Counter

5. 链表

5.1 链表的基本结构

5.2 链表的种类

5.3 链表的常见操作

5.4 常见面试题

5.5 链表的优缺点

5.6 适用场景

5.7 小结表

二叉树

图论

200. 岛屿数量

回溯

46. 全排列

78. 子集

17. 电话号码的字母组合

39. 组合总和

22. 括号生成

79. 单词搜索

131. 分割回文串

51. N 皇后

二分查找

35. 搜索插入位置

74. 搜索二维矩阵

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

33. 搜索旋转排序数组

153. 寻找旋转排序数组中的最小值

4. 寻找两个正序数组的中位数

栈

20. 有效的括号

394. 字符串解码

739. 每日温度

84. 柱状图中最大的矩形

堆

215. 数组中的第K个最大元素

347. 前 K 个高频元素

295. 数据流的中位数

贪心算法

通用贪心算法框架

121. 买卖股票的最佳时机

55. 跳跃游戏

45. 跳跃游戏II

763. 划分字母区间

动态规划

70. 爬楼梯

118. 杨辉三角

198 打家劫舍

279. 完全平方数

322. 零钱兑换

139. 单词拆分

300. 最长递增子序列

152. 乘积最大子数组

416. 分割等和子集

32. 最长有效括号

多维动态规划

6.1 多维 DP 的定义

6.2 多维 DP 的常见场景

6.3 多维 DP 的编写步骤

6.4 示例：二维网格路径（简要）

6.5 空间优化技巧

6.6 多维 DP 的小结表

6.7 常见多维 DP 题型推荐

多维动态规划

62. 不同路径

64. 最小路径和

5. 最长回文子串

1143. 最长公共子序列

72. 编辑距离