在有序数组 [1, 3, 5, 7, 9, 11, 13, 15] 中找 7：

[1, 3, 5, 7, 9, 11, 13, 15]  left=0, right=7, mid=3 → nums[3]=7 ✅ 找到
                         ↑mid

如果找 6：
[1, 3, 5, 7, 9, 11, 13, 15]  left=0, right=7, mid=3 → nums[3]=7 >6
 left=0, right=2, mid=1 → nums[1]=3 <6
 left=2, right=2, mid=2 → nums[2]=5 <6
 left=3, right=2 → 退出，找不到

int binarySearchClose(const vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;         // ① [left, right] 闭区间

    while (left <= right) {                        // ② 区间非空
        int mid = left + (right - left) / 2;       // ③ 取中点（防溢出）
        if (nums[mid] == target) return mid;       // ④ 命中
        if (nums[mid] < target) left = mid + 1;    // ⑤ target 在右半
        else right = mid - 1;                      // ⑥ target 在左半
    }

    return -1;                                     // ⑦ 未找到
}

int binarySearchOpen(const vector<int>& nums, int target) {
    int left = 0, right = nums.size();             // ① [left, right) 右开区间

    while (left < right) {                         // ② 区间非空
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) return mid;
        if (nums[mid] < target) left = mid + 1;
        else right = mid;                          // ③ 右开，mid 作为新右边界
    }

    return -1;
}

// lower_bound：第一个 >= target 的位置
// 在 [1, 2, 3, 5, 5, 5, 7, 9] 中：
// lower_bound(5) → 指向第一个 5（位置 3）
// lower_bound(4) → 指向第一个 5（第一个 >=4 的元素）
// lower_bound(10) → 指向 end()（所有元素 < 10）

// upper_bound：第一个 > target 的位置
// upper_bound(5) → 指向 7（第一个 >5 的元素）
// upper_bound(5) - lower_bound(5) = 3（5 的个数）

**整体操作流程**：

1. **初始化**：`left = 0`，`right = n`，采用左闭右开区间 `[left, right)`。
2. **循环**：`while (left < right)`。
3. **判断**：如果 `nums[mid] < target`，目标在 `mid` 右侧，`left = mid + 1`；否则 `nums[mid] >= target`，目标在 `mid` 或左侧，`right = mid`。
4. **返回**：循环结束时 `left == right`，指向第一个 `>= target` 的元素位置。

```cpp
int lowerBound(const vector<int>& nums, int target) {
    int left = 0, right = nums.size();             // ① [left, right) 区间

    while (left < right) {                         // ② 区间非空
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;                        // ③ mid < target，答案在右侧
        } else {
            right = mid;                           // ④ mid >= target，答案在左侧含 mid
        }
    }

    return left;                                   // ⑤ 第一个 >=target 的位置
}

nums = [4, 5, 6, 7, 0, 1, 2], target = 0

mid = 3, nums[3] = 7
左半 [4,5,6,7] 有序，右半 [0,1,2] 有序？— 不对！

准确说：nums[left] <= nums[mid] → 左半有序
          nums[4]=4 <= nums[3]=7 ✅ 左半有序
          
          target=0 在左半 [4,7] 范围内？0 < 4 → 不在，去右半
          left = mid + 1 = 4
          
mid = 5, nums[5] = 1
nums[4]=0 <= nums[5]=1 → 左半 [0,1] 有序
target=0 在 [0,1] 内 → 去左半
right = mid = 5
...

int search(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;

    while (left <= right) {                        // ① 标准二分框架
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) return mid;

        if (nums[left] <= nums[mid]) {             // ② 左半有序
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1;                   // ③ target 在左半
            } else {
                left = mid + 1;                    // ④ target 在右半
            }
        } else {                                   // ⑤ 右半有序
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1;                    // ⑥ target 在右半
            } else {
                right = mid - 1;                   // ⑦ target 在左半
            }
        }
    }

    return -1;
}

int findPeakElement(vector<int>& nums) {
    int left = 0, right = nums.size() - 1;

    while (left < right) {                         // ① 二分查找
        int mid = left + (right - left) / 2;

        if (nums[mid] < nums[mid + 1]) {           // ② 上坡 → 峰值在右
            left = mid + 1;
        } else {                                   // ③ 下坡或平 → 峰值在左
            right = mid;
        }
    }

    return left;                                   // ④ left == right 即峰值
}

double mySqrt(double x) {
    double left = 0, right = x;

    if (x < 1) right = 1;                         // ① x<1 时 sqrt(x) > x

    while (right - left > 1e-7) {                 // ② 精度控制而非整数比较
        double mid = left + (right - left) / 2;
        if (mid * mid < x) {
            left = mid;                           // ③ mid 太小，向右靠
        } else {
            right = mid;                          // ④ mid 太大，向左靠
        }
    }

    return left;                                  // ⑤ 返回近似值
}

nums = [7, 2, 5, 10, 8], k = 2

如果每段最大和 ≤ 10：能分成 2 段吗？
  [7,2] sum=9 ≤10  ✅, [5,10,8] sum=23 >10 ❌ → 不行

如果每段最大和 ≤ 15：能分成 2 段吗？
  [7,2,5] sum=14 ≤15 ✅, [10,8] sum=18 >15 ❌ → 不行

如果每段最大和 ≤ 18：
  [7,2,5] sum=14 ≤18 ✅, [10,8] sum=18 ≤18 ✅ → 可以！

bool canSplit(const vector<int>& nums, int k, int max_sum) {
    int count = 1;                                 // ① 至少一段
    int current_sum = 0;

    for (int x : nums) {                           // ② 遍历每个元素
        if (current_sum + x > max_sum) {           // ③ 超过上限，另起一段
            count++;
            current_sum = x;
            if (count > k) return false;           // ④ 段数超了 → 不可行
        } else {
            current_sum += x;                      // ⑤ 加入当前段
        }
    }

    return true;                                   // ⑥ 可以在 k 段内完成
}

int splitArray(vector<int>& nums, int k) {
    int left = *max_element(nums.begin(), nums.end());   // ① 下界：最大元素
    int right = accumulate(nums.begin(), nums.end(), 0); // ② 上界：总和

    while (left < right) {                         // ③ 二分搜索
        int mid = left + (right - left) / 2;
        if (canSplit(nums, k, mid)) {
            right = mid;                           // ④ 可行，尝试更小值
        } else {
            left = mid + 1;                        // ⑤ 不可行，增大上限
        }
    }

    return left;                                   // ⑥ 最小的最大段和
}

物品：重量 w = [2, 3, 4, 5]  价值 v = [3, 4, 5, 6]  容量 W = 8

dp[i][j]：前 i 个物品中选，总重量 ≤ j 时的最大价值

初始化 dp[0][*] = 0（没有物品可选）

状态转移：
dp[i][j] = max(dp[i-1][j],                      // 不选第 i 个
               dp[i-1][j - w[i-1]] + v[i-1])    // 选第 i 个（前提 j >= w[i-1]）

填表过程：
   j=0  1  2  3  4  5  6  7  8
i=0: 0  0  0  0  0  0  0  0  0
i=1(w=2,v=3): 0  0  3  3  3  3  3  3  3
i=2(w=3,v=4): 0  0  3  4  4  7  7  7  7
i=3(w=4,v=5): 0  0  3  4  5  7  8  9  9
i=4(w=5,v=6): 0  0  3  4  5  7  8  9  10  ← 结果 = 10

选法：物品 2(w=3,v=4) + 物品 4(w=5,v=6) = 重量 8，价值 10

int knapsack01(const vector<int>& w, const vector<int>& v, int W) {
    int n = w.size();
    vector<int> dp(W + 1, 0);                      // ① dp[j] = 容量 j 的最大价值

    for (int i = 0; i < n; i++) {                  // ② 遍历每个物品
        for (int j = W; j >= w[i]; j--) {          // ③ 倒序遍历容量
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);// ④ 不选 vs 选
        }
    }

    return dp[W];                                  // ⑤ 容量 W 的最大价值
}

dp[j] = max(dp[j], dp[j - w[i]] + v[i])

正序遍历时：dp[j - w[i]] 可能已经包含了当前第 i 个物品
  → 相当于"一个物品选多次"（完全背包）

倒序遍历时：dp[j - w[i]] 还是上一轮的状态（还没更新）
  → 保证每个物品最多选一次（0-1 背包）

int knapsackComplete(const vector<int>& w, const vector<int>& v, int W) {
    int n = w.size();
    vector<int> dp(W + 1, 0);

    for (int i = 0; i < n; i++) {                  // ① 遍历每个物品
        for (int j = w[i]; j <= W; j++) {          // ② 正序遍历容量
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);// ③ 允许重复选择
        }
    }

    return dp[W];
}

int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, 1);                          // ① dp[i]: 以 i 结尾的 LIS 长度
    int max_len = 1;

    for (int i = 0; i < n; i++) {                  // ② 遍历每个元素作为结尾
        for (int j = 0; j < i; j++) {              // ③ 找前面比它小的元素
            if (nums[j] < nums[i]) {               // ④ 可以接在后面
                dp[i] = max(dp[i], dp[j] + 1);     // ⑤ 取最大长度
            }
        }
        max_len = max(max_len, dp[i]);             // ⑥ 更新全局最大值
    }

    return max_len;
}

int lengthOfLIS(vector<int>& nums) {
    vector<int> tails;                             // ① tails[k] = 长度为 k+1 的最小末尾

    for (int x : nums) {                           // ② 遍历每个元素
        auto it = lower_bound(tails.begin(), tails.end(), x);// ③ 找第一个 >= x 的位置
        if (it == tails.end()) {
            tails.push_back(x);                    // ④ x 大于所有末尾，扩展 LIS
        } else {
            *it = x;                               // ⑤ 替换末尾为更小的值
        }
    }

    return tails.size();                           // ⑥ LIS 长度
}

nums = [3, 5, 6, 2, 5, 4, 7]

tails 的变化：
x=3: tails = [3]              (长度为 1 的 LIS 末尾最小是 3)
x=5: tails = [3, 5]            (长度为 2 的 LIS 末尾最小是 5)
x=6: tails = [3, 5, 6]         (长度为 3 的 LIS 末尾最小是 6)
x=2: tails = [2, 5, 6]         (替换 3 → 2，长度为 1 的末尾更小了)
x=5: tails = [2, 5, 6]         (5 ≥ tails[1]=5，不动)  
     // 注意 lower_bound 找第一个 >=5，是 tails[1]=5
     // 严格递增，5 不小于 5 → 不替换
x=4: tails = [2, 4, 6]         (替换 5 → 4，长度为 2 的末尾更小了)
x=7: tails = [2, 4, 6, 7]      (扩展！LIS 长度 = 4)

int longestCommonSubsequence(string text1, string text2) {
    int m = text1.size(), n = text2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));// ① 初始化 DP 表

    for (int i = 1; i <= m; i++) {                   // ② 遍历 text1
        for (int j = 1; j <= n; j++) {               // ③ 遍历 text2
            if (text1[i-1] == text2[j-1]) {          // ④ 字符匹配
                dp[i][j] = dp[i-1][j-1] + 1;         // ⑤ 长度 +1
            } else {                                 // ⑥ 不匹配
                dp[i][j] = max(dp[i-1][j],           // ⑦ 跳过 text1 的字符
                               dp[i][j-1]);           // ⑧ 跳过 text2 的字符
            }
        }
    }

    return dp[m][n];                                 // ⑨ LCS 长度
}

    ""  a  c  e
""  0  0  0  0
a   0  1  1  1   ← a 匹配
b   0  1  1  1
c   0  1  2  2   ← c 匹配
d   0  1  2  2
e   0  1  2  3   ← e 匹配 → 答案 3

石子重量 [3, 2, 4, 1]

dp[i][j]：合并第 i 堆到第 j 堆的最小代价
dp[i][i] = 0（一堆不需要合并）

转移方程：dp[i][j] = min(dp[i][k] + dp[k+1][j] + sum(i,j))
其中 k 从 i 到 j-1，sum(i,j) 是合并 i~j 的代价（即 i~j 的总重量）

int mergeStones(vector<int>& stones) {
    int n = stones.size();
    vector<int> prefix(n + 1, 0);                  // ① 前缀和
    for (int i = 0; i < n; i++) prefix[i+1] = prefix[i] + stones[i];

    auto sum = [&](int i, int j) { return prefix[j+1] - prefix[i]; };

    vector<vector<int>> dp(n, vector<int>(n, INT_MAX));
    for (int i = 0; i < n; i++) dp[i][i] = 0;      // ② 一堆不用合并

    for (int len = 2; len <= n; len++) {            // ③ 从小到大枚举区间长度
        for (int i = 0; i + len - 1 < n; i++) {    // ④ 枚举起点
            int j = i + len - 1;                    // ⑤ 计算终点
            for (int k = i; k < j; k++) {           // ⑥ 枚举分割点
                dp[i][j] = min(dp[i][j],
                               dp[i][k] + dp[k+1][j] + sum(i, j));// ⑦ 合并 i~j 的总代价
            }
        }
    }

    return dp[0][n-1];                             // ⑧ 合并全部的最小代价
}

void dfs(TreeNode* node, vector<int>& result) {
    if (!node) return;                             // ① 空节点返回

    result.push_back(node->val);                   // ② 前序位置处理当前节点

    dfs(node->left, result);                       // ③ 递归左子树
    dfs(node->right, result);                      // ④ 递归右子树
}

void dfsStack(TreeNode* root) {
    if (!root) return;
    stack<TreeNode*> stk;
    stk.push(root);                                // ① 根节点入栈

    while (!stk.empty()) {
        TreeNode* node = stk.top();
        stk.pop();                                 // ② 弹出栈顶
        // 处理 node

        if (node->right) stk.push(node->right);    // ③ 右子节点先入栈
        if (node->left)  stk.push(node->left);     // ④ 左子节点后入栈（保证左先处理）
    }
}

// BFS 通用模板
void bfs(TreeNode* root) {
    if (!root) return;
    queue<TreeNode*> q;
    q.push(root);

    while (!q.empty()) {
        int level_size = q.size();  // 当前层节点数
        for (int i = 0; i < level_size; i++) {
            TreeNode* node = q.front();
            q.pop();
            // 处理 node

            if (node->left)  q.push(node->left);
            if (node->right) q.push(node->right);
        }
    }
}

课程依赖：
  课程 1 → 课程 3（1 是 3 的先修）
  课程 2 → 课程 3
  课程 3 → 课程 4

有向图：
1 → 3 → 4
↑
2 ┘

入度表：1:0, 2:0, 3:2, 4:1

步骤：
1. 入度为 0：1, 2 → 入队
2. 弹出 1，3 入度 -1 → 3 入度 1
3. 弹出 2，3 入度 -1 → 3 入度 0 → 3 入队
4. 弹出 3，4 入度 -1 → 4 入度 0 → 4 入队
5. 弹出 4

拓扑排序结果：[1, 2, 3, 4] 或 [2, 1, 3, 4]

vector<int> topologicalSort(int n, const vector<vector<int>>& edges) {
    vector<vector<int>> graph(n);                  // ① 邻接表
    vector<int> indegree(n, 0);                    // ② 入度表

    for (auto& e : edges) {                       // ③ 建图
        int u = e[0], v = e[1];
        graph[u].push_back(v);                    // u → v
        indegree[v]++;                            // ④ v 的入度 +1
    }

    queue<int> q;
    for (int i = 0; i < n; i++) {
        if (indegree[i] == 0) q.push(i);          // ⑤ 入度为 0 的节点入队
    }

    vector<int> result;
    while (!q.empty()) {
        int u = q.front(); q.pop();               // ⑥ 弹出队首
        result.push_back(u);                      // ⑦ 加入拓扑排序结果

        for (int v : graph[u]) {                  // ⑧ 遍历所有后继
            if (--indegree[v] == 0) {             // ⑨ 入度减为 0 → 入队
                q.push(v);
            }
        }
    }

    return result;                                // ⑩ result.size() < n 则有环
}

图：
     2
  A───→B
  │    │
1 │    │ 3
  ↓    ↓
  C───→D
     1

从 A 出发：
dist: A=0, B=∞, C=∞, D=∞

1. 从 A 出发，更新邻居：
   dist[B] = min(∞, 0+2) = 2
   dist[C] = min(∞, 0+1) = 1
   dist = {A:0, B:2, C:1, D:∞}
   标记 A 已访问

2. 选未访问中最小 dist：C(1)
   dist[D] = min(∞, 1+1) = 2
   标记 C 已访问

3. 选未访问中最小：B(2) 和 D(2)，任选一个，比如 B
   dist[D] = min(2, 2+3) = 2  ← 不变
   标记 B 已访问

4. 选 D，没有未访问邻居

最终：A→C→D = 2，A→B = 2

vector<int> dijkstra(int start, const vector<vector<pair<int, int>>>& graph) {
    int n = graph.size();
    vector<int> dist(n, INT_MAX);                  // ① 距离初始化为无穷大
    vector<bool> visited(n, false);

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;// ② 小顶堆

    dist[start] = 0;                               // ③ 起点到自身距离为 0
    pq.push({0, start});                           // ④ 起点入队

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();          // ⑤ 取距离最近的未访问节点

        if (visited[u]) continue;                  // ⑥ 已处理过则跳过
        visited[u] = true;                         // ⑦ 标记已访问

        for (auto [v, w] : graph[u]) {             // ⑧ 遍历所有邻接边
            if (d + w < dist[v]) {                 // ⑨ 发现更短路径
                dist[v] = d + w;                   // ⑩ 更新距离
                pq.push({dist[v], v});             // ⑪ 新距离入队
            }
        }
    }

    return dist;                                   // ⑫ 返回所有点的最短距离
}

vector<vector<int>> floydWarshall(const vector<vector<int>>& graph) {
    int n = graph.size();
    vector<vector<int>> dist = graph;              // ① 拷贝邻接矩阵

    for (int k = 0; k < n; k++) {                  // ② 中间节点
        for (int i = 0; i < n; i++) {              // ③ 起点
            for (int j = 0; j < n; j++) {          // ④ 终点
                if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX) {
                    dist[i][j] = min(dist[i][j],   // ⑤ 尝试经过 k 的路径
                                     dist[i][k] + dist[k][j]);
                }
            }
        }
    }

    return dist;                                   // ⑥ 所有点对的最短距离
}

class UnionFind {
    vector<int> parent;                             // parent[i] = i 的父节点
    vector<int> rank;                               // rank[i] = 树的高度
    int count;                                      // 连通分量数

public:
    UnionFind(int n) : parent(n), rank(n, 0), count(n) {
        for (int i = 0; i < n; i++) parent[i] = i; // ① 每个节点自成一派
    }

    int find(int x) {
        if (parent[x] != x) {                      // ② 不是根节点
            parent[x] = find(parent[x]);           // ③ 递归找根 + 路径压缩
        }
        return parent[x];                          // ④ 返回根节点
    }

    void unite(int x, int y) {
        int rootX = find(x);                        // ⑤ 找 x 的根
        int rootY = find(y);                        // ⑥ 找 y 的根

        if (rootX == rootY) return;                // ⑦ 已经连通

        if (rank[rootX] < rank[rootY]) {            // ⑧ 矮树接到高树下
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;                  // ⑨ 高度相同，合并后高度 +1
            rank[rootX]++;
        }

        count--;                                    // ⑩ 连通分量数减 1
    }

    int getCount() const { return count; }          // ⑪ 查询连通分量数
};

初始： 0  1  2  3  4
       |  |  |  |  |
       0  1  2  3  4

unite(0,1): 0 → 1
unite(2,3): 2 → 3
unite(1,2): 找 1 的根 = 1，找 2 的根 = 3，按秩合并

树形：
    1       3
   /       / \
  0       2   4
         (unite(3,4))

接下来 find(0)：
  find(0) → find(1) → 返回 1
  路径压缩：parent[0] = 1

树形变为：
    1
   / \
  0   3
     / \
    2   4

下次 find(0) 直接 O(1)：parent[0] → 1

第四阶段（排序算法）：
    快排：原地分区，缓存友好，平均 O(N log N)，最坏退化 O(N²)
    归并：稳定，O(N log N)，外部排序首选
    堆排：原地 O(1) 空间，但缓存不友好
    实际选型：std::sort = 快排 + 堆排 + 插入排序的混合

第五阶段（二分搜索）：
    [left,right] vs [left,right) 两种写法
    lower_bound：第一个 >=target 的位置
    旋转数组：判断哪半有序来决定搜索方向
    二分答案：把最优化问题转为判定问题

第六阶段（动态规划）：
    状态定义 + 转移方程 + 初始条件 = DP 三要素
    0-1 背包：一维数组倒序
    完全背包：一维数组正序
    LIS：O(N log N) 耐心排序
    LCS：二维表格递推
    区间 DP：从小到大枚举区间长度

第七阶段（图算法）：
    DFS：递归/显式栈，找路径
    BFS：队列，找最短路径（无权图）
    拓扑排序：Kahn 算法（入度表 + 队列）
    Dijkstra：优先队列，非负权单源最短路径
    Floyd：三重循环，全源最短路径（V<500）
    并查集：路径压缩 + 按秩合并 ≈ O(1)

需要实现：
get(key)：存在返回值，不存在返回 -1。访问过的 key 变为"最近使用"。
put(key, value)：存在则更新值；不存在则插入，如果满则淘汰最久未使用的。

数据结构选择：
1. 哈希表（unordered_map）：O(1) 查找 key 是否存在。
2. 双向链表（list）：维护使用顺序。
   - 头部 = 最近使用
   - 尾部 = 最久未使用

哈希表的 value 存链表的迭代器 → 查到时直接 O(1) 移到头部。

内存布局：
链表：
[head] ⇄ [key=k1, val=v1] ⇄ [key=k2, val=v2] ⇄ ... ⇄ [tail(哨兵)]
  ↑ 最近使用                        最久未使用 ↑

哈希表：
{k1: 指向 k1 节点的迭代器}
{k2: 指向 k2 节点的迭代器}

class LRUCache {
    int cap_;
    list<pair<int, int>> items_;                     // 链表：头=最近使用，尾=最久未使用
    unordered_map<int, list<pair<int, int>>::iterator> cache_;// key → 迭代器

public:
    LRUCache(int capacity) : cap_(capacity) {}

    int get(int key) {
        auto it = cache_.find(key);                  // ① 在哈希表中查找
        if (it == cache_.end()) return -1;            // ② 不存在 → -1

        items_.splice(items_.begin(), items_, it->second);// ③ 移到链表头部
        return it->second->second;                    // ④ 返回 value
    }

    void put(int key, int value) {
        auto it = cache_.find(key);

        if (it != cache_.end()) {                     // ① key 已存在
            it->second->second = value;               // ② 更新 value
            items_.splice(items_.begin(), items_, it->second);// ③ 移到头部
            return;
        }

        if (cache_.size() >= cap_) {                  // ④ 缓存满
            auto& last = items_.back();               // ⑤ 取尾部节点（最久未使用）
            cache_.erase(last.first);                 // ⑥ 从哈希表删除
            items_.pop_back();                        // ⑦ 从链表删除
        }

        items_.emplace_front(key, value);             // ⑧ 在链表头部插入
        cache_[key] = items_.begin();                 // ⑨ 记录到哈希表
    }
};

// splice 不拷贝元素，只改 3 个指针
items_.splice(items_.begin(), items_, it->second);

// 操作本质：
// 把 it->second 这个节点的 prev/next 和 items_.begin() 之前的节点串起来
// 等价于：
// 1. 从当前位置摘下（改前驱和后继的指针）
// 2. 插入到头部（改 head 的指针）
// 一共改 6 个指针，常数时间

插入 "apple"、"app"、"apply"、"apt" 后的 Trie：

         root
        /    \
       a      ...
      /
     p
    /
   p ← 有一个 is_end 标记（"app" 到这里结束）
  / \
 l   t
 |   |
 e   ... ("apt" 的 t)
 |
 e ← is_end（"apple"）
 |
 y ← is_end（"apply"）

查找 "appl"：
  root → a → p → p → l → 没到 is_end → 不是完整单词
  但路径存在 → 是前缀

class Trie {
    struct TrieNode {
        TrieNode* children[26] = {};                // ① 26 个小写字母的子节点指针
        bool is_end = false;                         // ② 标记是否为完整单词
    };

    TrieNode* root_;

public:
    Trie() : root_(new TrieNode()) {}

    void insert(string word) {
        TrieNode* cur = root_;
        for (char c : word) {                        // ③ 遍历每个字符
            int idx = c - 'a';                       // ④ 计算子节点索引
            if (!cur->children[idx]) {               // ⑤ 子节点不存在则创建
                cur->children[idx] = new TrieNode();
            }
            cur = cur->children[idx];                // ⑥ 移动到子节点
        }
        cur->is_end = true;                          // ⑦ 标记为完整单词
    }

    bool search(string word) {
        TrieNode* cur = root_;
        for (char c : word) {                        // ① 沿路径查找
            int idx = c - 'a';
            if (!cur->children[idx]) return false;    // ② 路径中断 → 不存在
            cur = cur->children[idx];
        }
        return cur->is_end;                          // ③ 必须是完整单词
    }

    bool startsWith(string prefix) {
        TrieNode* cur = root_;
        for (char c : prefix) {
            int idx = c - 'a';
            if (!cur->children[idx]) return false;
            cur = cur->children[idx];
        }
        return true;                                 // ④ 路径存在即匹配
    }
};

初始状态（位数组长度 m=12，哈希函数 k=3）：
[0][0][0][0][0][0][0][0][0][0][0][0]

插入 "apple"：
  哈希1("apple") % 12 = 2  → 位置 2 置 1
  哈希2("apple") % 12 = 7  → 位置 7 置 1
  哈希3("apple") % 12 = 5  → 位置 5 置 1
  → [0][0][1][0][1][0][0][1][0][0][0][0]
              ↑        ↑        ↑

插入 "banana"：
  哈希1("banana") % 12 = 5  → 已经是 1
  哈希2("banana") % 12 = 9  → 位置 9 置 1
  哈希3("banana") % 12 = 1  → 位置 1 置 1
  → [0][1][1][0][1][0][0][1][0][1][0][0]
          ↑              ↑        ↑

查询 "apple"：
  哈希1→位置2=1 ✅  哈希2→位置7=1 ✅  哈希3→位置5=1 ✅
  所有位都是 1 → "可能存在"

查询 "grape"：
  哈希1("grape") % 12 = 2 → 1 ✅
  哈希2("grape") % 12 = 7 → 1 ✅
  哈希3("grape") % 12 = 4 → 0 ❌
  有一位是 0 → "一定不存在"

class BloomFilter {
    std::vector<bool> bits_;                         // 位数组
    size_t k_;                                       // 哈希函数个数

    std::pair<size_t, size_t> hash(const std::string& key, size_t i) const {
        size_t h1 = std::hash<std::string>{}(key);   // ① 主哈希
        size_t h2 = h1 >> 32;                        // ② 辅助哈希
        size_t index = (h1 + i * h2) % bits_.size(); // ③ 第 i 个哈希位置
        return {index, 0};
    }

public:
    BloomFilter(size_t bit_count, size_t hash_count)
        : bits_(bit_count, false), k_(hash_count) {}

    void insert(const std::string& key) {
        size_t h1 = std::hash<std::string>{}(key);
        size_t h2 = h1 >> 32;

        for (size_t i = 0; i < k_; i++) {            // ① k 个哈希函数
            size_t idx = (h1 + i * h2) % bits_.size();
            bits_[idx] = true;                       // ② 对应位置 1
        }
    }

    bool contains(const std::string& key) const {
        size_t h1 = std::hash<std::string>{}(key);
        size_t h2 = h1 >> 32;

        for (size_t i = 0; i < k_; i++) {
            size_t idx = (h1 + i * h2) % bits_.size();
            if (!bits_[idx]) return false;           // ③ 有一位为 0 → 一定不存在
        }
        return true;                                 // ④ 所有位为 1 → 可能存在
    }
};

假阳性率 ≈ (1 - e^(-k * n / m))^k

m = 位数组长度（bit 数）
n = 插入的元素个数
k = 哈希函数个数

经验值（让假阳性率最低）：
  k = (m / n) * ln(2)      ← 最优哈希函数个数
  m = -n * ln(p) / (ln(2)^2)  ← 给定假阳性率 p 所需的位数

例如：
  n = 1000 万，希望 p = 1%：
  m ≈ 9580 万 bit ≈ 114 MB
  k ≈ 7 个哈希函数

模式串 P = "ABABCABAB"

手动计算 next：
i=0: next[0] = -1（特殊标记，表示第一个字符就不匹配）
i=1: P[0] = "A" → 没有前后缀 → next[1] = 0
i=2: P[0..1] = "AB" → 前缀"A", 后缀"B" → 不相等 → next[2] = 0
i=3: P[0..2] = "ABA" → 前缀"A"="A"✅, "AB"≠"BA" → next[3] = 1
i=4: P[0..3] = "ABAB" → 前缀"AB"="AB"✅, "ABA"≠"BAB" → next[4] = 2
i=5: P[0..4] = "ABABC" → "AB"?="BC"→no, "A"?="C"→no → next[5]=0
i=6: P[0..5] = "ABABCA" → "A"="A"✅ → next[6]=1
i=7: P[0..6] = "ABABCAB" → "AB"="AB"✅ → next[7]=2
i=8: P[0..7] = "ABABCABA" → "ABA"="ABA"✅ → next[8]=3

最终 next = [-1, 0, 0, 1, 2, 0, 1, 2, 3]

vector<int> buildNext(const string& pattern) {
    int m = pattern.size();
    vector<int> next(m);
    next[0] = -1;                                  // ① 特殊标记
    int i = 0, j = -1;                             // ② i:当前处理位置, j:已匹配前缀长度

    while (i < m - 1) {                            // ③ 遍历模式串
        if (j == -1 || pattern[i] == pattern[j]) { // ④ 匹配成功或从头开始
            i++; j++;
            next[i] = j;                           // ⑤ 记录最长相等前后缀长度
        } else {
            j = next[j];                           // ⑥ 回溯到更短的前缀
        }
    }

    return next;
}

int kmpSearch(const string& text, const string& pattern) {
    int n = text.size(), m = pattern.size();
    if (m == 0) return 0;

    vector<int> next = buildNext(pattern);
    int i = 0, j = 0;                              // ① i:文本指针, j:模式指针

    while (i < n && j < m) {
        if (j == -1 || text[i] == pattern[j]) {    // ② 字符匹配
            i++; j++;
        } else {
            j = next[j];                           // ③ 关键：i 不回溯，只回退 j
        }
    }

    if (j == m) return i - j;                      // ④ 匹配成功，返回文本中的起始位置
    return -1;                                     // ⑤ 匹配失败
}

文本: A B A B D A B A C D A B A B C A B A B
模式: A B A B C A B A B
    匹配 D ≠ C 时：
    模式 C 的位置 j=4，next[4]=2
    → j 跳到 2（模式串的第三个字符 A）
    → 模式串的 "AB" 已经匹配好了，不需要重新比较

    A B A B D A B A C ...
          A B A B C ...（j=2 开始，跳过 A B）

// 把 "hello" 看成 26 进制数：
// h = ('h'-'a'+1) * 26^4 + ('e'-'a'+1) * 26^3 + ... + ('o'-'a'+1) * 26^0
// 这样每个字符串唯一对应一个 hash 值

// 在 "abcdefg" 中找 "cde"

// 先计算 "abc" 的哈希
// 窗口右移 → "abc" → "bcd"
// hash("bcd") = (hash("abc") - val('a') * 26^2) * 26 + val('d')
//   = 去掉最高位 + 整体左移一位 + 加入新低位

class RabinKarp {
    const long long base_ = 131;                     // ① 进制（常用质数）
    const long long mod_ = 1e9 + 7;                  // ② 取模用的大质数

    long long pow_mod(long long base, long long exp) const {
        long long res = 1;
        while (exp) {                                // ③ 快速幂
            if (exp & 1) res = (res * base) % mod_;
            base = (base * base) % mod_;
            exp >>= 1;
        }
        return res;
    }

public:
    int search(const string& text, const string& pattern) {
        int n = text.size(), m = pattern.size();
        if (m > n) return -1;

        long long pat_hash = 0;
        for (char c : pattern) {                     // ④ 计算模式串哈希
            pat_hash = (pat_hash * base_ + (c - 'a' + 1)) % mod_;
        }

        long long power = pow_mod(base_, m - 1);     // ⑤ 最高位权值

        long long text_hash = 0;
        for (int i = 0; i < m; i++) {                // ⑥ 计算首个窗口哈希
            text_hash = (text_hash * base_ + (text[i] - 'a' + 1)) % mod_;
        }

        if (text_hash == pat_hash) return 0;         // ⑦ 首个窗口匹配

        for (int i = m; i < n; i++) {                // ⑧ 滚动窗口
            text_hash = (text_hash - (text[i - m] - 'a' + 1) * power) % mod_;// ⑨ 去掉最左
            text_hash = (text_hash * base_) % mod_;   // ⑩ 左移一位
            text_hash = (text_hash + (text[i] - 'a' + 1)) % mod_;// ⑪ 加入最右

            if (text_hash < 0) text_hash += mod_;    // ⑫ 处理负数

            if (text_hash == pat_hash) return i - m + 1;// ⑬ 匹配
        }

        return -1;                                   // ⑭ 未找到
    }
};

不同字符串可能有相同的哈希值（hash collision）。
解决方案：
1. 双哈希：用两组不同的 base 和 mod，两个哈希值都相等才认为匹配。
2. 哈希值相等时，再逐字符比较确认（如果 m 很小，代价不高）。

一般用单哈希 + 少量误判可接受（比如海量去重场景）。

// 1. 消去最后一个 1
int lowbit_clear(int x) {
    return x & (x - 1);
    // x   = 10101000
    // x-1 = 10100111
    // &   = 10100000 ← 最后一个 1 被消掉
}

// 2. 取出最后一个 1
int lowbit(int x) {
    return x & -x;
    // x     = 10101000
    // -x    = 01011000（补码表示）
    // &     = 00001000 ← 只留下最后一个 1
}

// 3. 判断 2 的幂
bool isPowerOfTwo(int x) {
    return x > 0 && (x & (x - 1)) == 0;
    // 2 的幂：二进制只有一个 1
    // 8  = 00001000, 7 = 00000111, & = 00000000 ✅
    // 10 = 00001010, 9 = 00001001, & = 00001000 ≠ 0 ❌
}

// 统计 1 的个数（Brian Kernighan 算法）
int countBits(int x) {
    int count = 0;
    while (x) {
        x &= (x - 1);  // 每次消去最后一个 1
        count++;
    }
    return count;
}

// 判断第 k 位是否为 1（从 0 开始）
bool getBit(int x, int k) {
    return (x >> k) & 1;
}

// 将第 k 位置为 1
int setBit(int x, int k) {
    return x | (1 << k);
}

// 将第 k 位置为 0
int clearBit(int x, int k) {
    return x & ~(1 << k);
}

// 交换两个数（不用临时变量）
void swap(int& a, int& b) {
    a ^= b;
    b ^= a;
    a ^= b;
}

x  = 10101000
~x = 01010111
-x = ~x + 1 = 01011000
x & -x = 00001000 ✅

// 假设有 10 亿个整数（0 ~ 10^9），标记哪些出现过
// 用 bool 数组：10 亿字节 ≈ 1GB
// 用位图：10 亿 bit ≈ 125MB（节省 8 倍）

class BitMap {
    vector<uint64_t> bits_;  // 每个 uint64_t 存 64 个 bit

public:
    BitMap(size_t size) : bits_((size + 63) / 64, 0) {}

    void set(size_t pos) {
        bits_[pos / 64] |= (1ULL << (pos % 64));
    }

    bool test(size_t pos) const {
        return (bits_[pos / 64] >> (pos % 64)) & 1;
    }
};

visited = 0b00000000000000000101
           ↑                    ↑
           城市 19              城市 0 和 2 已经去过

int tsp(vector<vector<int>>& dist) {
    int n = dist.size();
    vector<vector<int>> dp(1 << n, vector<int>(n, INT_MAX / 2));// ① dp[mask][i]
    dp[1][0] = 0;                                     // ② 从城市 0 出发

    for (int mask = 1; mask < (1 << n); mask++) {      // ③ 遍历所有访问状态
        for (int i = 0; i < n; i++) {
            if (!(mask & (1 << i))) continue;          // ④ i 不在 mask 中 → 跳过
            for (int j = 0; j < n; j++) {
                if (mask & (1 << j)) continue;         // ⑤ j 已访问 → 跳过
                int next = mask | (1 << j);            // ⑥ 新状态：加入 j
                dp[next][j] = min(dp[next][j],         // ⑦ 更新最短距离
                                  dp[mask][i] + dist[i][j]);
            }
        }
    }

    int ans = INT_MAX;
    for (int i = 1; i < n; i++) {                      // ⑧ 回到城市 0
        ans = min(ans, dp[(1 << n) - 1][i] + dist[i][0]);
    }
    return ans;
}

vector<int> topK(const vector<int>& data, int k) {
    priority_queue<int, vector<int>, greater<>> pq;   // ① 小顶堆

    for (int x : data) {
        if (pq.size() < k) {                           // ② 堆未满直接入
            pq.push(x);
        } else if (x > pq.top()) {                     // ③ 比堆顶大则替换
            pq.pop();                                  // ④ 去掉当前第 K 大
            pq.push(x);                                // ⑤ 加入更大的
        }
    }

    vector<int> result;
    while (!pq.empty()) {
        result.push_back(pq.top());
        pq.pop();
    }
    reverse(result.begin(), result.end());             // ⑥ 反转为从大到小
    return result;
}

int partition(vector<int>& nums, int left, int right) {
    int pivot = nums[right];                         // ① 选最右为基准
    int i = left;
    for (int j = left; j < right; j++) {
        if (nums[j] > pivot) {                       // ② 大的放左边（区别：找前 K 大）
            swap(nums[i++], nums[j]);
        }
    }
    swap(nums[i], nums[right]);                      // ③ 归位 pivot
    return i;                                        // ④ 返回 pivot 在从大到小序列中的位置
}

int quickSelect(vector<int>& nums, int left, int right, int k) {
    if (left == right) return nums[left];

    int p = partition(nums, left, right);            // ① 分区

    if (p == k) return nums[p];                      // ② 找到第 k 大的元素
    if (p < k) return quickSelect(nums, p + 1, right, k); // ③ 第 k 大在右半
    return quickSelect(nums, left, p - 1, k);        // ④ 第 k 大在左半
}

vector<int> topKQuickSelect(vector<int>& nums, int k) {
    quickSelect(nums, 0, nums.size() - 1, k - 1);    // ① 找第 k 大（k-1 是 0-indexed）
    return vector<int>(nums.begin(), nums.begin() + k);// ② 前 k 个就是前 K 大
}

1. 分割（Split Phase）：
   读入 1GB 到内存 → 快排 → 写回磁盘为 "chunk1.sorted"
   读入 1GB 到内存 → 快排 → 写回磁盘为 "chunk2.sorted"
   ... 共 100 个有序块

2. 多路归并（Merge Phase）：
   打开 100 个文件句柄，每个读第一个元素
   用大小为 100 的小顶堆找最小的元素输出到结果文件
   从输出元素的文件读入下一个
   重复直到所有文件处理完

总 I/O：读 100GB + 写 100GB（分割），再读 100GB + 写 100GB（归并）
       = 读 200GB + 写 200GB

1. 用哈希函数把每个 URL 分配到 1000 个小文件中：
   file_id = hash(url) % 1000
   写入 file_{file_id}.txt

2. 每个小文件足够小，可以全部加载到内存：
   用 unordered_set 对每个小文件去重
   输出到独立的结果文件

3. 合并各文件结果
   （因为哈希分片后，相同的 URL 一定在同一个文件中）

class MedianFinder {
    priority_queue<int> left_;                       // ① 最大堆（存左半较小的一半）
    priority_queue<int, vector<int>, greater<>> right_;// ② 最小堆（存右半较大的一半）

public:
    void addNum(int num) {
        if (left_.empty() || num <= left_.top()) {   // ③ 小于等于左半最大值 → 左半
            left_.push(num);
        } else {
            right_.push(num);                        // ④ 否则 → 右半
        }

        if (left_.size() > right_.size() + 1) {      // ⑤ 左半太多 → 移一个到右半
            right_.push(left_.top());
            left_.pop();
        }
        if (right_.size() > left_.size()) {          // ⑥ 右半太多 → 移一个到左半
            left_.push(right_.top());
            right_.pop();
        }
    }

    double findMedian() {
        if (left_.size() > right_.size()) {          // ⑦ 奇数个 → 左半堆顶
            return left_.top();
        }
        return (left_.top() + right_.top()) / 2.0;   // ⑧ 偶数个 → 两堆顶均值
    }
};

int majorityElement(vector<int>& nums) {
    int candidate = nums[0];                         // ① 初始候选人
    int count = 1;                                   // ② 票数

    for (int i = 1; i < nums.size(); i++) {
        if (nums[i] == candidate) {                  // ③ 相同 → 加票
            count++;
        } else {                                     // ④ 不同 → 抵销
            count--;
            if (count == 0) {                        // ⑤ 票数为 0 → 换候选人
                candidate = nums[i];
                count = 1;
            }
        }
    }

    return candidate;                                // ⑥ 最终候选人即为众数
}

nums = [2, 2, 1, 1, 1, 2, 2]

2: candidate=2, count=1
2: count=2
1: 不同 → count=1
1: 不同 → count=0 → candidate=1, count=1
1: count=2
2: 不同 → count=1
2: 不同 → count=0 → candidate=2, count=1

最终 candidate=2 ✅

第八阶段（数据结构手写）：
    LRU 缓存：list + unordered_map，splice O(1) 移到头部
    Trie：26 叉树，前缀查询 O(L)，空间大
    布隆过滤器：位数组 + k 哈希，省空间但可能有误判

第九阶段（字符串算法）：
    KMP：next 数组记录最长相等前后缀，i 不回溯
    滚动哈希：O(N) 滑动窗口更新哈希值

第十阶段（位运算）：
    x & (x-1)：消去最后一个 1
    x & -x：取出最后一个 1
    位图：8 倍省空间，海量判重
    状态压缩：用 int 的 bit 表示集合，N≤20 可用

第十一阶段（海量数据）：
    TopK：小顶堆 O(N log K) 或 快速选择 O(N)
    外部排序：分割 + 多路归并
    双堆中位数：最大堆 + 最小堆
    摩尔投票：O(N) 找出现次数超过一半的元素