## 一、补充的5个核心方向

在掌握了算法面试中最常见的几大类题型（如动态规划、DFS/BFS、贪心、字符串、树）之后，还有一些非常重要的补充知识点也常常出现在高频面试题中。以下是五大进阶方向及对应的必刷题目推荐。

---



### 1. **堆（Heap）与优先队列**

> 堆是一种高效的优先级数据结构，常用于 Top-K、合并排序链表等场景。

#### 🔥 必刷题目：
- 🧱 [215. 数组中的第K个最大元素](https://leetcode.cn/problems/kth-largest-element-in-an-array/)  
  - 可用快速选择或最小堆实现
- 📊 [347. 前K个高频元素](https://leetcode.cn/problems/top-k-frequent-elements/)  
  - 哈希计数 + 最小堆构建 Top-K 频率词
- ⚙️ [23. 合并K个升序链表](https://leetcode.cn/problems/merge-k-sorted-lists/)  
  - 使用优先队列优化多路归并

---

### 2. **图算法（DFS/BFS进阶）**

> 图是树的扩展，涉及拓扑排序、连通分量、路径查找等复杂问题。

#### 🔥 必刷题目：
- 🎓 [207. 课程表](https://leetcode.cn/problems/course-schedule/)  
  - 判断是否可以完成所有课程 → 拓扑排序判环
- 📚 [210. 课程表 II](https://leetcode.cn/problems/course-schedule-ii/)  
  - 输出可行的学习顺序 → 拓扑排序+路径输出
- ÷ [399. 除法求值](https://leetcode.cn/problems/evaluate-division/)  
  - 构建带权图模型，使用 DFS 或 BFS 进行查询

---

### 3. **并查集（Union-Find）**

> 并查集是处理集合合并与查询问题的高效工具，适用于连通性判断和图的划分。

#### 🔥 必刷题目：
- 🏝️ [200. 岛屿数量](https://leetcode.cn/problems/number-of-islands/)  
  - 可用 DFS/BFS 或并查集解决
- 🗺️ [547. 省份数量](https://leetcode.cn/problems/number-of-provinces/)  
  - 并查集模板题，判断朋友圈数量
- 🔁 [684. 冗余连接](https://leetcode.cn/problems/redundant-connection/)  
  - 寻找使图出现环的那条边，典型并查集应用

---

### 4. **位运算与数学题**

> 位操作和数学技巧是提升代码效率的关键，尤其在系统编程和嵌入式开发中非常重要。

#### 🔥 必刷题目：
- 🔁 [136. 只出现一次的数字](https://leetcode.cn/problems/single-number/)  
  - 异或性质：a ^ a = 0, a ^ 0 = a
- 💡 [191. 位1的个数](https://leetcode.cn/problems/number-of-1-bits/)  
  - 位移运算或 `n & (n - 1)` 技巧统计1的数量
- 📈 [50. Pow(x, n)](https://leetcode.cn/problems/powx-n/)  
  - 快速幂算法实现 O(log n) 的指数计算

---

### 5. **设计题（OOD & 系统设计基础）**

> 设计类题目考察面向对象设计能力、数据结构组合能力，也是中高级岗位的高频考点。

#### 🔥 必刷题目：
- 🧠 [146. LRU缓存](https://leetcode.cn/problems/lru-cache/)  
  - 哈希表 + 双向链表实现 O(1) 时间复杂度的 LRU 缓存机制
- 🎲 [380. O(1)时间插入、删除和获取随机元素](https://leetcode.cn/problems/insert-delete-getrandom-o1/)  
  - 哈希表 + 动态数组结合实现随机访问
- 🧮 [155. 最小栈](https://leetcode.cn/problems/min-stack/)  
  - 使用辅助栈记录当前最小值，实现 O(1) 获取最小元素

---

## ✅ 总结建议

| 方向 | 核心技能 | 推荐练习策略 |
|------|----------|--------------|
| 堆 | 优先队列、Top-K问题 | 掌握 Python `heapq` 模块，理解堆调整过程 |
| 图算法 | 拓扑排序、DFS/BFS进阶 | 多做图建模题，熟练写邻接表/矩阵 |
| 并查集 | 集合合并、连通性判断 | 理解路径压缩与按秩合并优化 |
| 位运算 | 异或、位移、状态压缩 | 熟悉常见位操作技巧 |
| 设计题 | 数据结构组合、面向对象设计 | 注重接口设计与性能分析 |

---

📌 **建议学习顺序**：  
堆 ➜ 图算法 ➜ 并查集 ➜ 位运算 ➜ 设计题

这些方向虽然不如 DP 或 BFS 出现频率高，但却是区分候选人深度理解和工程能力的重要标志。建议每个方向至少掌握 2~3 道经典题，并尝试自己实现完整解法。

【算法刷题】查漏补缺

# 树（Tree）结构题目分类与详解

> **树（Tree）** 是算法面试中非常核心的数据结构，广泛涉及遍历、递归、DFS/BFS、二叉搜索树（BST）、平衡树、字典树（Trie）等知识点。本文将对树类常见题型进行系统分类与经典题目解析，帮助你快速掌握解题思路。



---

## 一、树的遍历（前序、中序、后序、层序）

### 1. 递归遍历

#### 🧭 [144. 二叉树的前序遍历](https://leetcode.cn/problems/binary-tree-preorder-traversal/)
```python
def preorderTraversal(root):
    res = []
    def dfs(node):
        if not node: return
        res.append(node.val)  # 前序
        dfs(node.left)
        dfs(node.right)
    dfs(root)
    return res
```

#### 🌀 [94. 二叉树的中序遍历](https://leetcode.cn/problems/binary-tree-inorder-traversal/)
```python
def inorderTraversal(root):
    res = []
    def dfs(node):
        if not node: return
        dfs(node.left)
        res.append(node.val)  # 中序
        dfs(node.right)
    dfs(root)
    return res
```

### 2. 迭代遍历（栈实现）

#### 🧱 [145. 二叉树的后序遍历](https://leetcode.cn/problems/binary-tree-postorder-traversal/)
```python
def postorderTraversal(root):
    res = []
    stack = []
    prev = None
    while root or stack:
        while root:
            stack.append(root)
            root = root.left
        root = stack[-1]
        if not root.right or root.right == prev:
            res.append(root.val)
            stack.pop()
            prev = root
            root = None
        else:
            root = root.right
    return res
```

### 3. 层序遍历（BFS）

#### 🌳 [102. 二叉树的层序遍历](https://leetcode.cn/problems/binary-tree-level-order-traversal/)
```python
def levelOrder(root):
    if not root: return []
    queue = collections.deque([root])
    res = []
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            if node.left: queue.append(node.left)
            if node.right: queue.append(node.right)
        res.append(level)
    return res
```

---

## 二、二叉树递归问题

### 1. 树的深度与高度

#### 📏 [104. 二叉树的最大深度](https://leetcode.cn/problems/maximum-depth-of-binary-tree/)
```python
def maxDepth(root):
    if not root: return 0
    return 1 + max(maxDepth(root.left), maxDepth(root.right))
```

#### ⚖️ [110. 平衡二叉树](https://leetcode.cn/problems/balanced-binary-tree/)
```python
def isBalanced(root):
    def height(node):
        if not node: return 0
        left = height(node.left)
        right = height(node.right)
        if left == -1 or right == -1 or abs(left - right) > 1:
            return -1
        return 1 + max(left, right)
    return height(root) != -1
```

### 2. 路径问题

#### 🛤️ [112. 路径总和](https://leetcode.cn/problems/path-sum/)
```python
def hasPathSum(root, targetSum):
    if not root: return False
    if not root.left and not root.right:
        return targetSum == root.val
    return hasPathSum(root.left, targetSum - root.val) or \
           hasPathSum(root.right, targetSum - root.val)
```

#### 🎯 [437. 路径总和 III](https://leetcode.cn/problems/path-sum-iii/)
```python
def pathSum(root, targetSum):
    from collections import defaultdict
    prefix = defaultdict(int)
    prefix[0] = 1
    def dfs(node, curr_sum):
        if not node: return 0
        curr_sum += node.val
        res = prefix[curr_sum - targetSum]
        prefix[curr_sum] += 1
        res += dfs(node.left, curr_sum) + dfs(node.right, curr_sum)
        prefix[curr_sum] -= 1
        return res
    return dfs(root, 0)
```

---

## 三、二叉搜索树（BST）

### 1. BST性质验证

#### 🔍 [98. 验证二叉搜索树](https://leetcode.cn/problems/validate-binary-search-tree/)
```python
def isValidBST(root):
    def helper(node, lower=float('-inf'), upper=float('inf')):
        if not node: return True
        if node.val <= lower or node.val >= upper:
            return False
        return helper(node.left, lower, node.val) and \
               helper(node.right, node.val, upper)
    return helper(root)
```

### 2. BST操作

#### ➕ [701. 插入操作](https://leetcode.cn/problems/insert-into-a-binary-search-tree/)
```python
def insertIntoBST(root, val):
    if not root: return TreeNode(val)
    if val < root.val:
        root.left = insertIntoBST(root.left, val)
    else:
        root.right = insertIntoBST(root.right, val)
    return root
```

#### ➖ [450. 删除节点](https://leetcode.cn/problems/delete-node-in-a-bst/)
```python
def deleteNode(root, key):
    if not root: return None
    if key < root.val:
        root.left = deleteNode(root.left, key)
    elif key > root.val:
        root.right = deleteNode(root.right, key)
    else:
        if not root.left: return root.right
        if not root.right: return root.left
        min_node = root.right
        while min_node.left:
            min_node = min_node.left
        root.val = min_node.val
        root.right = deleteNode(root.right, min_node.val)
    return root
```

---

## 四、字典树（Trie）

### 1. 前缀匹配

#### 🧩 [208. 实现 Trie (前缀树)](https://leetcode.cn/problems/implement-trie-prefix-tree/)
```python
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word):
        node = self.root
        for c in word:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
        node.is_end = True
    
    def search(self, word):
        node = self.root
        for c in word:
            if c not in node.children:
                return False
            node = node.children[c]
        return node.is_end
    
    def startsWith(self, prefix):
        node = self.root
        for c in prefix:
            if c not in node.children:
                return False
            node = node.children[c]
        return True
```

### 2. 单词搜索 II

#### 🧠 [212. 单词搜索 II](https://leetcode.cn/problems/word-search-ii/)
```python
def findWords(board, words):
    trie = Trie()
    for word in words:
        trie.insert(word)
    res = set()
    m, n = len(board), len(board[0])
    for i in range(m):
        for j in range(n):
            dfs(board, i, j, trie.root, "", res)
    return list(res)

def dfs(board, i, j, node, path, res):
    if node.is_end:
        res.add(path)
    if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or board[i][j] not in node.children:
        return
    tmp = board[i][j]
    board[i][j] = "#"  # 标记已访问
    for dx, dy in [(-1,0),(1,0),(0,-1),(0,1)]:
        dfs(board, i+dx, j+dy, node.children[tmp], path+tmp, res)
    board[i][j] = tmp  # 回溯
```

---

## 五、高频树结构题目列表

| 类型               | 经典题目                                                                                     |
|--------------------|--------------------------------------------------------------------------------------------|
| 树的遍历           | [144. 前序](https://leetcode.cn/problems/binary-tree-preorder-traversal/)、[102. 层序](https://leetcode.cn/problems/binary-tree-level-order-traversal/) |
| 递归问题           | [104. 最大深度](https://leetcode.cn/problems/maximum-depth-of-binary-tree/)、[112. 路径总和](https://leetcode.cn/problems/path-sum/) |
| BST操作            | [98. 验证BST](https://leetcode.cn/problems/validate-binary-search-tree/)、[450. 删除节点](https://leetcode.cn/problems/delete-node-in-a-bst/) |
| 字典树（Trie）     | [208. 实现Trie](https://leetcode.cn/problems/implement-trie-prefix-tree/)、[212. 单词搜索 II](https://leetcode.cn/problems/word-search-ii/) |

---

## 六、总结

> 树结构类题目的核心在于**递归思想与结构特性的结合应用**。

**常用技巧包括：**

1. ✅ **递归分治**：如求深度、路径和
2. 💡 **DFS/BFS遍历**：前序、中序、后序、层序
3. 🔍 **BST特性**：左子树 < 根节点 < 右子树，中序遍历有序
4. 🧠 **Trie树**：高效字符串前缀匹配与查找

---

📌 **学习建议路径**：  
树的遍历 → 递归问题 → BST性质 → Trie结构

【算法刷题】关于树的算法题目

# 字符串算法题目分类与详解

> **字符串（String）** 是算法面试中占比极高的题型，涉及模式匹配、子串/子序列、哈希计数、回文、滑动窗口等多个核心知识点。本文将对字符串常见题型进行系统分类与经典题目解析，帮助你快速掌握解题思路。

---



## 一、字符串基础操作

### 1. 反转与变形

#### 🧭 [344. 反转字符串](https://leetcode.cn/problems/reverse-string/)
```python
def reverseString(s):
    left, right = 0, len(s) - 1
    while left < right:
        s[left], s[right] = s[right], s[left]
        left += 1
        right -= 1
```

#### 🔁 [541. 反转字符串 II](https://leetcode.cn/problems/reverse-string-ii/)
```python
def reverseStr(s, k):
    s = list(s)
    for i in range(0, len(s), 2 * k):
        s[i:i+k] = reversed(s[i:i+k])
    return ''.join(s)
```

---

## 二、字符串匹配与搜索

### 1. 子串匹配（KMP算法）

#### 🔍 [28. 实现 strStr()](https://leetcode.cn/problems/implement-strstr/)
- **核心思想**：预处理模式串，利用 `next` 数组避免主串回溯
```python
def strStr(haystack, needle):
    if not needle: return 0
    n, m = len(haystack), len(needle)
    # 构建 next 数组
    next_arr = [0] * m
    j = 0
    for i in range(1, m):
        while j > 0 and needle[i] != needle[j]:
            j = next_arr[j - 1]
        if needle[i] == needle[j]:
            j += 1
            next_arr[i] = j
    # 匹配过程
    j = 0
    for i in range(n):
        while j > 0 and haystack[i] != needle[j]:
            j = next_arr[j - 1]
        if haystack[i] == needle[j]:
            j += 1
        if j == m:
            return i - m + 1
    return -1
```

### 2. 通配符匹配

#### ⭐ [44. 通配符匹配](https://leetcode.cn/problems/wildcard-matching/)
- **动态规划实现**：
```python
def isMatch(s, p):
    dp = [[False] * (len(p) + 1) for _ in range(len(s) + 1)]
    dp[0][0] = True
    for j in range(1, len(p) + 1):
        if p[j - 1] == '*':
            dp[0][j] = dp[0][j - 1]
    for i in range(1, len(s) + 1):
        for j in range(1, len(p) + 1):
            if p[j - 1] == '*':
                dp[i][j] = dp[i - 1][j] or dp[i][j - 1]
            elif p[j - 1] == '?' or s[i - 1] == p[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
    return dp[-1][-1]
```

---

## 三、子串与子序列问题

### 1. 最长公共子序列（LCS）

#### 📊 [1143. 最长公共子序列](https://leetcode.cn/problems/longest-common-subsequence/)
```python
def longestCommonSubsequence(text1, text2):
    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[m][n]
```

### 2. 最长回文子串

#### 🌀 [5. 最长回文子串](https://leetcode.cn/problems/longest-palindromic-substring/)
```python
def longestPalindrome(s):
    def expand(l, r):
        while l >= 0 and r < len(s) and s[l] == s[r]:
            l -= 1
            r += 1
        return s[l + 1:r]
    
    res = ""
    for i in range(len(s)):
        odd = expand(i, i)      # 奇数长度
        even = expand(i, i + 1) # 偶数长度
        res = max(res, odd, even, key=len)
    return res
```

---

## 四、哈希与计数问题

### 1. 字母异位词

#### 🧩 [242. 有效的字母异位词](https://leetcode.cn/problems/valid-anagram/)
```python
def isAnagram(s, t):
    return sorted(s) == sorted(t)
    # 或使用 collections.Counter
```

### 2. 最小覆盖子串（滑动窗口）

#### 🎯 [76. 最小覆盖子串](https://leetcode.cn/problems/minimum-window-substring/)
```python
def minWindow(s, t):
    from collections import defaultdict
    need = defaultdict(int)
    for c in t:
        need[c] += 1
    left = 0
    min_len = float('inf')
    start = 0
    missing = len(t)

    for right, c in enumerate(s):
        if need[c] > 0:
            missing -= 1
        need[c] -= 1

        if missing == 0:
            while left < right and need[s[left]] < 0:
                need[s[left]] += 1
                left += 1
            if right - left + 1 < min_len:
                min_len = right - left + 1
                start = left

    return s[start:start + min_len] if min_len != float('inf') else ""
```

---

## 五、字符串编码与解码

### 1. 字符串压缩

#### 🧱 [443. 压缩字符串](https://leetcode.cn/problems/string-compression/)
```python
def compress(chars):
    write = 0
    read = 0
    n = len(chars)
    while read < n:
        current_char = chars[read]
        count = 0
        while read < n and chars[read] == current_char:
            read += 1
            count += 1
        chars[write] = current_char
        write += 1
        if count > 1:
            for c in str(count):
                chars[write] = c
                write += 1
    return write
```

### 2. 字符串解码（栈）

#### 🧩 [394. 字符串解码](https://leetcode.cn/problems/decode-string/)
```python
def decodeString(s):
    stack = []
    num = 0
    res = ""
    for c in s:
        if c.isdigit():
            num = num * 10 + int(c)
        elif c == '[':
            stack.append((res, num))
            res, num = "", 0
        elif c == ']':
            prev_str, repeat = stack.pop()
            res = prev_str + res * repeat
        else:
            res += c
    return res
```

---

## 六、高频字符串题目列表

| 类型               | 经典题目                                                                                     |
|--------------------|--------------------------------------------------------------------------------------------|
| 反转与变形         | [344. 反转字符串](https://leetcode.cn/problems/reverse-string/)、[541. 反转字符串 II](https://leetcode.cn/problems/reverse-string-ii/) |
| 子串匹配           | [28. 实现 strStr()](https://leetcode.cn/problems/implement-strstr/)、[44. 通配符匹配](https://leetcode.cn/problems/wildcard-matching/) |
| 子序列问题         | [1143. 最长公共子序列](https://leetcode.cn/problems/longest-common-subsequence/)、[5. 最长回文子串](https://leetcode.cn/problems/longest-palindromic-substring/) |
| 哈希与计数         | [242. 字母异位词](https://leetcode.cn/problems/valid-anagram/)、[76. 最小覆盖子串](https://leetcode.cn/problems/minimum-window-substring/) |
| 编码与解码         | [443. 压缩字符串](https://leetcode.cn/problems/string-compression/)、[394. 字符串解码](https://leetcode.cn/problems/decode-string/) |

---

## 七、总结

> 字符串类题目的核心在于**灵活运用多种技巧组合解决问题**。

**常用技巧包括：**

1. ✅ **滑动窗口**：如最小覆盖子串
2. 💡 **动态规划**：如最长公共子序列
3. 🔍 **KMP算法**：高效子串匹配
4. 🧮 **哈希计数**：统计字符频率
5. 🔁 **中心扩展法**：解决回文问题

---

📌 **学习建议路径**：  
字符串反转 → 子串匹配 → 滑动窗口 → 动态规划 → 字符串编码

【算法刷题】字符串相关算法

# 贪心算法（Greedy Algorithm）系统分类与经典题型详解

> **贪心算法（Greedy Algorithm）** 是一种在每一步选择中都采取当前状态下最优决策的算法思想，常用于解决最优化问题。其核心在于：局部最优解能否推导出全局最优解。

本文从基础概念到经典题型进行系统分类与解析，涵盖从入门到进阶的所有常见问题。

---

## 一、贪心算法的三大核心要素

1. ✅ **贪心选择性质**：每一步的局部最优选择能导致全局最优解  
2. 🔁 **无后效性**：当前的选择不会影响后续子问题的结构  
3. ⚡ **高效性**：时间复杂度通常为 $O(n)$ 或 $O(n \log n)$，优于动态规划  



---

## 二、贪心算法经典题型分类

### 1. 区间调度问题

#### （1）不相交区间选择

##### 📅 [435. 无重叠区间](https://leetcode.cn/problems/non-overlapping-intervals/)
- **策略**：按结束时间升序排序，优先选择结束早的区间
- **代码实现**：
```python
def eraseOverlapIntervals(intervals):
    if not intervals: return 0
    intervals.sort(key=lambda x: x[1])
    count = 1
    end = intervals[0][1]
    for i in range(1, len(intervals)):
        if intervals[i][0] >= end:
            count += 1
            end = intervals[i][1]
    return len(intervals) - count
```

#### （2）合并区间

##### 🧩 [56. 合并区间](https://leetcode.cn/problems/merge-intervals/)
- **策略**：按起始时间排序，合并重叠区间
- **代码实现**：
```python
def merge(intervals):
    intervals.sort(key=lambda x: x[0])
    merged = []
    for interval in intervals:
        if not merged or merged[-1][1] < interval[0]:
            merged.append(interval)
        else:
            merged[-1][1] = max(merged[-1][1], interval[1])
    return merged
```

---

### 2. 分配问题

#### （1）饼干分配

##### 🍪 [455. 分发饼干](https://leetcode.cn/problems/assign-cookies/)
- **策略**：将最小的饼干分配给最小需求的孩子（双指针贪心）
- **代码实现**：
```python
def findContentChildren(g, s):
    g.sort()
    s.sort()
    i = j = 0
    while i < len(g) and j < len(s):
        if s[j] >= g[i]: i += 1
        j += 1
    return i
```

#### （2）任务调度

##### 📋 [621. 任务调度器](https://leetcode.cn/problems/task-scheduler/)
- **策略**：优先安排出现次数最多的任务，用空闲时间填充其他任务

---

### 3. 跳跃游戏问题

#### （1）能否到达终点

##### 🏃‍♂️ [55. 跳跃游戏](https://leetcode.cn/problems/jump-game/)
- **策略**：维护当前能到达的最远距离，逐步扩展
- **代码实现**：
```python
def canJump(nums):
    max_reach = 0
    for i in range(len(nums)):
        if i > max_reach: return False
        max_reach = max(max_reach, i + nums[i])
    return True
```

#### （2）最少跳跃次数

##### 🐾 [45. 跳跃游戏 II](https://leetcode.cn/problems/jump-game-ii/)
- **策略**：在每一步选择能跳到最远范围的位置
- **代码实现**：
```python
def jump(nums):
    steps = 0
    cur_end = 0
    max_reach = 0
    for i in range(len(nums) - 1):
        max_reach = max(max_reach, i + nums[i])
        if i == cur_end:
            steps += 1
            cur_end = max_reach
    return steps
```

---

### 4. 买卖股票问题

#### （1）无限次交易

##### 💰 [122. 买卖股票的最佳时机 II](https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/)
- **策略**：所有上升区间的利润累加
- **代码实现**：
```python
def maxProfit(prices):
    profit = 0
    for i in range(1, len(prices)):
        if prices[i] > prices[i-1]:
            profit += prices[i] - prices[i-1]
    return profit
```

#### （2）含手续费

##### 💰🧮 [714. 最佳时机含手续费](https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/)
- **策略**：在价格上涨时卖出，但需扣除手续费

---

### 5. 字符串问题

#### （1）分割字符串

##### 🔤 [763. 划分字母区间](https://leetcode.cn/problems/partition-labels/)
- **策略**：记录每个字母的最后出现位置，按区间分割
- **代码实现**：
```python
def partitionLabels(s):
    last = {c: i for i, c in enumerate(s)}
    start = end = 0
    res = []
    for i, c in enumerate(s):
        end = max(end, last[c])
        if i == end:
            res.append(end - start + 1)
            start = end + 1
    return res
```

#### （2）移除重复字母

##### 🧹 [316. 去除重复字母](https://leetcode.cn/problems/remove-duplicate-letters/)
- **策略**：维护单调栈，保证字典序最小且每个字母至少出现一次

---

## 三、贪心算法解题技巧总结

1. 📊 **排序预处理**：多数贪心问题需要先排序（如按起始时间、结束时间、数值大小等）
2. 🧠 **反证法验证**：通过假设“非贪心选择更优”来推导矛盾，证明贪心策略的正确性
3. 👆 **双指针技巧**：常用于区间或分配问题（如饼干分配、跳跃游戏）
4. 🔍 **观察数据规律**：例如股票问题中“所有上升区间和=总利润”

---

## 四、高频贪心算法题目列表

| 类型           | 经典题目                                                                                     |
|----------------|--------------------------------------------------------------------------------------------|
| 区间问题       | [435. 无重叠区间](https://leetcode.cn/problems/non-overlapping-intervals/)、[56. 合并区间](https://leetcode.cn/problems/merge-intervals/) |
| 分配问题       | [455. 分发饼干](https://leetcode.cn/problems/assign-cookies/)、[621. 任务调度器](https://leetcode.cn/problems/task-scheduler/) |
| 跳跃游戏       | [55. 跳跃游戏](https://leetcode.cn/problems/jump-game/)、[45. 跳跃游戏 II](https://leetcode.cn/problems/jump-game-ii/) |
| 买卖股票       | [122. 买卖股票 II](https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/)、[714. 含手续费](https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/) |
| 字符串问题     | [763. 划分字母区间](https://leetcode.cn/problems/partition-labels/)、[316. 去除重复字母](https://leetcode.cn/problems/remove-duplicate-letters/) |

---

## 五、总结

> 贪心算法的核心在于通过局部最优选择构造全局最优解。

**掌握要点：**

1. ✅ **严格证明贪心策略的正确性**（如区间问题结束时间排序的合理性）
2. 🧱 **掌握经典问题的模板**（如跳跃游戏的双指针、股票问题的利润累加）
3. 🔀 **区分贪心与动态规划**：贪心不可回溯，动态规划需要状态转移

---

📌 **推荐练习顺序**：区间问题 → 分配问题 → 跳跃游戏 → 买卖股票 → 字符串问题

【算法刷题】贪心算法

# 广度优先搜索（BFS）系统分类与经典题型详解

> **广度优先搜索（Breadth-First Search, BFS）** 是一种基于队列实现的层次遍历算法，适用于最短路径、状态转移、连通性等问题。其核心思想是“层层扩展”，从起点出发，逐层访问所有可达节点。

本文从基础概念到经典题型进行系统分类与解析，涵盖从入门到进阶的所有常见问题。

---

## 一、BFS的三大核心要素

1. ✅ **队列（Queue）**：存储待访问节点，保证先进先出（FIFO）的遍历顺序  
2. 🧭 **已访问标记（Visited）**：避免重复访问（如哈希表、二维数组）  
3. 🔁 **层数统计（Level）**：记录当前遍历的层数（用于最短路径问题）



---

## 二、BFS经典题型分类

### 1. 树的层次遍历

#### （1）基础层序遍历

##### 🌳 [102. 二叉树的层序遍历](https://leetcode.cn/problems/binary-tree-level-order-traversal/)
```python
def levelOrder(root):
    if not root: return []
    queue = collections.deque([root])
    res = []
    while queue:
        level_size = len(queue)
        level = []
        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)
            if node.left: queue.append(node.left)
            if node.right: queue.append(node.right)
        res.append(level)
    return res
```

#### （2）变形问题

##### 🌀 [103. 二叉树的锯齿形层序遍历](https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/)
- **关键点**：偶数层反转结果（`level[::1 if len(res) % 2 == 0 else -1]`）

---

### 2. 图的最短路径

#### （1）无权图最短路径

##### 📚 [127. 单词接龙](https://leetcode.cn/problems/word-ladder/)
- **策略**：用 BFS 找从 `beginWord` 到 `endWord` 的最短转换序列  
- **优化**：双向 BFS（从起点和终点同时搜索）

#### （2）带权图最短路径

##### 🏙️ [1334. 阈值距离内邻居最少的城市](https://leetcode.cn/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance/)
- **变种**：Dijkstra 算法（优先队列实现）

---

### 3. 网格类BFS（岛屿 / 迷宫）

#### （1）连通区域计数

##### 🏝️ [200. 岛屿数量](https://leetcode.cn/problems/number-of-islands/)
```python
def numIslands(grid):
    if not grid: return 0
    directions = [(-1,0),(1,0),(0,-1),(0,1)]
    m, n = len(grid), len(grid[0])
    count = 0
    
    for i in range(m):
        for j in range(n):
            if grid[i][j] == '1':
                queue = collections.deque([(i,j)])
                grid[i][j] = '0'  # 标记已访问
                while queue:
                    x, y = queue.popleft()
                    for dx, dy in directions:
                        nx, ny = x + dx, y + dy
                        if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == '1':
                            queue.append((nx, ny))
                            grid[nx][ny] = '0'
                count += 1
    return count
```

#### （2）最短路径搜索

##### 🧭 [1091. 二进制矩阵中的最短路径](https://leetcode.cn/problems/shortest-path-in-binary-matrix/)
- **关键点**：8方向遍历，记录层数作为路径长度

---

### 4. 状态转移问题

#### （1）数字变换

##### 🔐 [752. 打开转盘锁](https://leetcode.cn/problems/open-the-lock/)
- **策略**：将每个密码（如"0000"）的8种变换（每位±1）加入队列  
- **优化**：用哈希表快速判断死亡数字

#### （2）滑动拼图

##### 🧩 [773. 滑动谜题](https://leetcode.cn/problems/sliding-puzzle/)
- **关键点**：将棋盘状态转化为字符串，记录0的位置和移动方向

---

### 5. 多源BFS

#### （1）多起点同时扩散

##### 🧱 [542. 01 矩阵](https://leetcode.cn/problems/01-matrix/)
```python
def updateMatrix(mat):
    m, n = len(mat), len(mat[0])
    queue = collections.deque()
    for i in range(m):
        for j in range(n):
            if mat[i][j] == 0:
                queue.append((i,j))
            else:
                mat[i][j] = -1  # 未访问标记
    
    directions = [(-1,0),(1,0),(0,-1),(0,1)]
    while queue:
        x, y = queue.popleft()
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < m and 0 <= ny < n and mat[nx][ny] == -1:
                mat[nx][ny] = mat[x][y] + 1
                queue.append((nx, ny))
    return mat
```

#### （2）腐烂的橘子

##### 🍊 [994. 腐烂的橘子](https://leetcode.cn/problems/rotting-oranges/)
- **同类型**：多源 BFS 统计感染轮数

---

## 三、BFS解题技巧总结

1. 🧭 **方向数组**：网格问题用 `directions = [(-1,0),(1,0),(0,-1),(0,1)]` 简化代码  
2. 🔁 **层数记录**：通过 `level_size = len(queue)` 控制当前层遍历  
3. 🧠 **状态压缩**：将复杂状态（如棋盘）转化为字符串或数字存储  
4. ⚡ **双向BFS**：当起点和终点明确时，双向搜索可大幅减少时间复杂度  

---

## 四、高频BFS题目列表

| 类型           | 经典题目                                                                                     |
|----------------|--------------------------------------------------------------------------------------------|
| 树遍历         | [102. 层序遍历](https://leetcode.cn/problems/binary-tree-level-order-traversal/)、[103. 锯齿遍历](https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/) |
| 图最短路径     | [127. 单词接龙](https://leetcode.cn/problems/word-ladder/)、[1334. 阈值距离城市](https://leetcode.cn/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance/) |
| 网格问题       | [200. 岛屿数量](https://leetcode.cn/problems/number-of-islands/)、[1091. 最短路径](https://leetcode.cn/problems/shortest-path-in-binary-matrix/) |
| 状态转移       | [752. 打开转盘锁](https://leetcode.cn/problems/open-the-lock/)、[773. 滑动谜题](https://leetcode.cn/problems/sliding-puzzle/) |
| 多源BFS        | [542. 01矩阵](https://leetcode.cn/problems/01-matrix/)、[994. 腐烂橘子](https://leetcode.cn/problems/rotting-oranges/) |

---

## 五、总结

> BFS 的核心在于**层次遍历与最短路径搜索**。

**掌握要点：**

1. ✅ **队列控制遍历顺序**，确保先访问的节点距离更短  
2. 🧱 **灵活处理状态**（如字符串密码、棋盘布局）  
3. 🔀 **区分DFS与BFS**：DFS适合连通性检测，BFS适合最短路径  

---

📌 **推荐练习顺序**：树的层序遍历 → 网格类问题 → 状态转移 → 多源BFS → 图最短路径