算法板子

发表于 更新于 分类于 阅读次数：

二分查找

二分查找为什么总是写错？_哔哩哔哩_bilibili

image-20260521135449487

例题：34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

注意边界问题

  1. 空数组问题：如果 nums = []，n = 0。循环不执行，binary_search_l 会检查 nums[0]，binary_search_r 会检查 nums[-1]，两者都会直接抛出 IndexError。
  2. target 大于数组中所有元素：例如 nums = [1, 2], target = 3。binary_search_l 循环结束后 right 会等于 n（即 2），此时检查 nums[right] 会抛出 IndexError。
  3. target 小于数组中所有元素：例如 nums = [1, 2], target = 0。binary_search_r 循环结束后 left 会等于 -1。在 Python 中 nums[-1] 不会报错而是取最后一个元素，这会导致逻辑错误（如果数组为空则依然会报错）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
def searchRange(nums: list[int], target: int) -> list[int]:
    n = len(nums)
    # 边界问题 1：提前处理空数组
    if n == 0:
        return [-1, -1]

    def binary_search_l(left, right, target):
        while left + 1 != right:
            mid = (left + right) // 2
            if nums[mid] < target:
                left = mid
            else:
                right = mid
        # 边界问题 2：right 可能越界到达 n，需要先判断 right != n
        if right != n and nums[right] == target:
            return right
        return -1

    def binary_search_r(left, right, target):
        while left + 1 != right:
            mid = (left + right) // 2
            if nums[mid] <= target:
                left = mid
            else:
                right = mid
        # 边界问题 3：left 可能越界到达 -1，需要先判断 left != -1
        if left != -1 and nums[left] == target:
            return left
        return -1

    # 寻找左边界
    left_idx = binary_search_l(-1, n, target)
    
    # 优化：如果左边界都找不到，说明 target 不存在，直接返回，无需再找右边界
    if left_idx == -1:
        return [-1, -1]
        
    # 寻找右边界（此时可以缩小左边界范围，从 left_idx - 1 开始找，提升微小性能）
    right_idx = binary_search_r(left_idx - 1, n, target)
    
    return [left_idx, right_idx]

流派一：暴力排除法（找具体的值）

核心思想：mid 被检查后，它绝对不是最终答案（或者它就是答案，我们已经直接 return 了）。既然不是答案，就必须把它狠狠踢出搜索范围。

  • 适用场景：在有序数组中找一个具体的数（比如 target）。
  • 更新方式：left = mid + 1 或 right = mid - 1。（一定要 +1 或 -1 跨过 mid）
  • 循环条件：left <= right。（因为当 left == right 时，区间里还有最后一个元素，你需要进循环检查它是不是答案）。
  • 初始边界：left = 0, right = n - 1。（答案只可能在数组的索引范围内）。

标准模板： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def binary_search_1(nums, target):
    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        # mid 不是答案，踢掉它
        else:
            right = mid - 1       # mid 不是答案，踢掉它
            
    return -1

流派二：温柔缩圈法（找边界 / 找位置）

核心思想：mid 被检查后，它有可能就是我们要找的那个边界！所以不能把它踢掉，只能让搜索区间慢慢向它“靠拢”。

  • 适用场景：找第一个大于/等于 target 的数，或者找最后一个小于/等于 target 的数。（比如你之前写的 searchRange 找左右边界）。
  • 更新方式：left = mid 或 right = mid。（绝对不能 +1 或 -1，否则会把正确答案踢掉）。
  • 循环条件：left < right。（当 left == right 时，区间缩成了一个点，这个点必然就是答案，不需要再进循环了）。
  • 初始边界：通常 left = 0, right = n。（答案有可能在数组外面，比如所有数都小于 target，答案就是 n）。

2.1 标准版模板（容易死循环，需小心）

1
2
3
4
5
6
7
8
9
10
11
def binary_search_2_standard(nums, target):
    left, right = 0, len(nums)
    
    while left < right:           # 注意是 <
        # 【防死循环核心】：如果后面有 left = mid，这里必须 +1 向上取整！
        mid = (left + right + 1) // 2 
        
        if check(mid):            # 假设满足条件时，答案在 mid 左边或就是 mid
            right = mid           # mid 可能是答案，保留它，缩小区间
        else:
            left = mid + 1        # mid 确定不是答案，踢掉

dfs

给新手的回溯法总结： 1）当组合中允许元素重复：则迭代的起始值就是i，每次递增 2）当组合中不允许重复：迭代的起始值是i + 1，每次递增 3）当这是排列不是组合：迭代的起始值是传进去的start（初始位），每次都从头开始遍历所有元素

组合

77. 组合 - 力扣（LeetCode）

从 n 个不同的元素中取出 k 个元素，不考虑选出的顺序，只关心“最终选到了哪些元素

image-20260726142117371 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;
    void dfs(int n, int k,int cur){
        if(path.size()+n-cur+1<k) return;
        if(path.size()==k){
            ans.push_back(path);
            return;
        }
        for(int i=cur;i<=n;i++){
            path.push_back(i);
            dfs(n,k,i+1);
            path.pop_back();
        }
    }
    vector<vector<int>> combine(int n, int k) {
        dfs(n,k,1);
        return ans;
    }
};

排列

从 n 个不同的元素中取出 k 个元素，严格考虑选出的顺序。相同的元素，只要顺序不同，就是不同的排列。

https://leetcode.cn/problems/permutations?envType=study-plan-v2&envId=top-interview-150

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;
    vector<int> visited;
    void dfs(int n,vector<int> &nums){
        if(n==nums.size()){
            ans.push_back(path);
            return;
        }
        for(int i=0;i<nums.size();i++){
            if(visited[i]) continue;
            path.push_back(nums[i]);
            visited[i]=1;
            dfs(n+1,nums);
            path.pop_back();
            visited[i]=0;
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        visited = vector<int>(nums.size(), 0);
        dfs(0,nums);
        return ans;
    }
};

动态规划

完全背包问题

【小白都能看懂的算法课】【Leetcode 322】【力扣】零钱兑换｜动态规划_哔哩哔哩_bilibili

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> ans(amount+1,amount+1);
        ans[0]=-0;
        for(int i=1;i<=amount;i++){
            for(auto &coin:coins){
               if(i>=coin) ans[i]=min(ans[i],ans[i-coin]+1);
            }
        }
        if(ans[amount]!=amount+1){
            return ans[amount];
        }
        return -1;
    }
};

最长递增子序列

【大厂程序员带你刷力扣】【小白都能听懂的算法课】【Leetcode 300】【力扣】最长递增子序列_哔哩哔哩_bilibili

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n=nums.size();
        vector<int> ans(n,1);
        int max_len = 1;
        for(int i=0;i<nums.size();i++){
            for(int j=0;j<i;j++){
                if(nums[j]<nums[i]){
                    ans[i]=max(ans[j]+1,ans[i]);
                }
            }
            max_len = max(max_len, ans[i]);
        }
        return max_len;
    }
};

Kadane 算法 最大子数组和

遍历数组时，对于每个元素 x，我们面临两个选择：

  1. 加入前面的子数组：把当前数 x 拼接到前面累计的子数组后面。
  2. 重新开始：放弃前面的子数组，以当前数 x 为起点重新建立一个子数组。

决策依据（极简口诀）：

如果前面的累加和是负数，它只会拉低当前数，果断舍弃，从当前数重新开始；

如果前面的累加和是正数，它能帮我变大，那就接着累加！

📐 状态转移方程（动态规划公式）

设 dp[i] 表示 以第 i 个元素结尾的连续子数组的最大和：

dp[i] = max (nums[i], dp[i − 1] + nums[i])

由于 dp[i] 只依赖上一个状态 dp[i-1]，我们只需要用一个变量 cur_sum 记录当前的累加和，再用一个 max_sum 记录全局遇到的最大值即可，将空间优化到 𝒪(1)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int max_sum = nums[0]; // 全局最大子数组和
        int cur_sum = nums[0]; // 以当前元素结尾的最大子数组和

        for (int i = 1; i < nums.size(); i++) {
            // 决策：是带上前面（cur_sum + nums[i]），还是自己单干（nums[i]）？
            cur_sum = max(nums[i], cur_sum + nums[i]);
            
            // 更新全局最大值
            max_sum = max(max_sum, cur_sum);
        }

        return max_sum;
    }
};

字典树

前缀树、Trie树

字典树（前缀树、Trie树）_哔哩哔哩_bilibili

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <bits/stdc++.h>
using namespace std;
struct treenode
{
    unordered_map<char,treenode*> child;
    bool isend;
    treenode(){
        isend=false;
    }
};

class Trie {
public:
    treenode *root;
    Trie() {
        root=new treenode();
    }
    
    void insert(string word) {
        treenode* cur=root;
        for(auto c:word){
            if(cur->child.count(c)==0){
                cur->child[c]=new treenode();
            }
            cur=cur->child[c];
        }
        cur->isend=true;
        return;
    }
    
bool search(string word) {
    treenode* cur = root;
    for (auto c : word) {
        if (cur->child.count(c)) { // 只需要判断路径是否存在
            cur = cur->child[c];
        } else {
            return false;
        }
    }
    return cur->isend; // 遍历完后，判断这是否是一个完整的单词
}
    
    bool startsWith(string prefix) {
        treenode* cur=root;
        for(auto c:prefix){
            if(cur->child.count(c)){
                cur=cur->child[c];
            }else{
                return false;
            }
        }
        return true;     
    }
};

前缀和

53. 最大子数组和 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int cur_sum=0;
        int minprefix=0;
        int ans=INT_MIN;
        for(auto &x:nums){
            cur_sum+=x;
            ans=max(ans,cur_sum-minprefix);
            minprefix=min(minprefix,cur_sum);
        }
        return ans;
    }
};

环形子数组的最大和:前缀和+单调队列

求连续子数组和：

  • 本质就是 当前前缀和 prefix[j] - 前面的某个前缀和 prefix[i]。

没有窗口限制时（普通最大子数组和）：

  • 想要结果最大，只要让 prefix[i] 是 历史出现的绝对最小值 就行。
  • 只需要一个普通的变量（比如 min_prefix）随时记录历史最小值，不需要任何复杂的队列。

一旦有了“最大窗口长度为 n”的限制（环形数组）：

  • prefix[i] 的 i 必须满足 j − n ≤ i ≤ j − 1。
  • 也就是说，太久以前的 prefix[i] 会 “过期”，不能再用了。
  • 此时问题变成了：在滑动窗口 [j − n, j − 1] 范围内，实时寻找 prefix[i] 的最小值。

解法落地：

  • 只要看到 “滑动窗口 + 找最值 + O(1) 时间”，数据结构里唯一且最完美的武器就是 单调队列！

子数组和(i + 1…j) = prefix[j] − prefix[i]

目标最大化：对于给定的右端点 j，我们想让 prefix[j] − prefix[i] 尽量大。

💡 关键转化：

因为 prefix[j] 在当前的循环步中是固定的，要想让 prefix[j] − prefix[i] 最大，只需要在区间 [j − n, j − 1] 内找到一个最小的 prefix[i]！

“在一个大小固定为 n 的滑动窗口内，实时寻找最小值”，这就是单调队列的拿手好戏！

🔍 单调队列维护的原则

队列里面存的是前缀和数组的下标 i，它必须满足一个特性：

队头到队尾对应的 prefix[i] 值必须是严格单调递增的！

  1. 查最小值（q.front()）：

    队头永远是当前合法窗口内 prefix 最小的那个下标，直接拿出来减，时间复杂度 O(1)！

  2. 踢出过期下标（pop_front）：

    当 q.front() < j - n 时，说明这个左端点离 j 太远了（子数组长度超过了 n），必须淘汰。

  3. 淘汰无用老员工（pop_back）：

    当要插入一个新的右端点 j 时，如果队尾下标 k 的前缀和 prefix[k] ≥ prefix[j]，说明 k 既比 j 靠左（生得早），值还比 j 大（能力差）。k 彻底失去了作为“未来最小前缀和”的价值，直接从队尾弹掉！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
#include <climits>

using namespace std;

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        int n = nums.size();

        // 1. 破环成链：构建长度为 2n + 1 的前缀和数组
        // prefix[k] 表示 extended_nums 中前 k 个元素的和
        vector<int> prefix(2 * n + 1, 0);
        for (int i = 0; i < 2 * n; i++) {
            prefix[i + 1] = prefix[i] + nums[i % n];
        }

        int max_sum = INT_MIN;
        deque<int> q; // 单调双端队列：存储前缀和的下标 i

        // 2. 初始将 prefix[0] 的下标 0 入队
        q.push_back(0);

        // 3. 遍历子数组的右端点 j（范围从 1 到 2n）
        for (int j = 1; j <= 2 * n; j++) {
            // 【步骤 A】：弹出超出长度 n 限制的“过期”左端点
            // 限制：子数组长度 j - i <= n  =>  i >= j - n
            while (!q.empty() && q.front() < j - n) {
                q.pop_front();
            }

            // 【步骤 B】：利用队头（窗口内的最小前缀和）计算当前最大子数组和
            if (!q.empty()) {
                max_sum = max(max_sum, prefix[j] - prefix[q.front()]);
            }

            // 【步骤 C】：将当前右端点 j 作为未来的左端点入队，维护队列单调递增
            while (!q.empty() && prefix[q.back()] >= prefix[j]) {
                q.pop_back();
            }
            q.push_back(j);
        }

        return max_sum;
    }
};

图

邻接表建图+bfs

399. 除法求值 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    double bfs(string src,string dst,unordered_map<string,unordered_map<string,double>> &mp){
        if(!mp.count(src))return -1;
        queue<pair<string,double>> q;
        q.push({src,1.0});
        unordered_set<string> visited;
        visited.insert(src);
        while (!q.empty())
        {
            pair<string,double> node=q.front();
            q.pop();
            string a=node.first;
            double val=node.second;
            if(a==dst){
                return val;
            }
            for(auto &[neighbour,weight]:mp[a]){
                if(!visited.count(neighbour)){
                    visited.insert(neighbour);
                    q.push({neighbour,weight*val});
                }
            }
        }
        return -1.0;
        
    }
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        unordered_map<string,unordered_map<string,double>> mp;
        int i=0;
        for(auto &equation:equations){
            string a=equation[0],b=equation[1];
            mp[a][b]=values[i];
            mp[b][a]=1.0/values[i];
            i++;
        }
        vector<double> ans;
        for(auto &query:queries){
            ans.push_back(bfs(query[0],query[1],mp));
        }
        return ans;
    }
};

拓扑排序：判断有向图是否存在环

图-拓扑排序_哔哩哔哩_bilibili

Kahn 算法（基于“入度”的 BFS 拓扑排序）

入度（In-degree）：一个节点被多少条有向边指向（即这门课需要多少门先修课）。

如果一门课的入度为 0，说明它不需要任何先修课，可以直接修读！

我们把所有入度为 0 的课放入队列。修完一门课后，把它指向的后继课程的“先修要求”去掉（后继课程的入度 -1）。

如果某门后继课程的入度减到了 0，说明它的先修课全修完了，也入队。

终局判断：最后统计修完的课程总数。如果等于 V，说明无环；否则说明图中存在互相依赖的“死锁环”。

207. 课程表 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph(numCourses);
        vector<int> inDegree(numCourses, 0);

        for(auto &pre : prerequisites){
            int a = pre[0];
            int b = pre[1];
            graph[b].push_back(a);
            inDegree[a]++;
        }

        queue<int> q;
        for(int i = 0; i < numCourses; i++){
            if(inDegree[i] == 0){
                q.push(i);
            }
        }

        int count = 0;
        while(!q.empty()){
            int cur = q.front();
            q.pop();
            count++;

            for(int neighbour : graph[cur]){
                inDegree[neighbour]--;
                if(inDegree[neighbour] == 0){
                    q.push(neighbour);
                }
            }
        }

        return count == numCourses;
    }
};

堆

环形子数组最大值：小根堆解法

当前前缀和-前面最小的前缀和，但是有最大窗口为n的限制，所以要用单调队列/优先队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<bits/stdc++.h>
using namespace std;
class Solution {
public:

    // 1. 定义仿函数结构体（写在类里面或外面都可以）
    struct cmp {
        bool operator()(const pair<int, int>& a, const pair<int, int>& b) {
            return a.first > b.first; // 小顶堆：first 越小优先级越高
        }
    };
    int maxSubarraySumCircular(vector<int>& nums) {
        int n=nums.size();
        vector<int> prefix(2*n+1);
        for(int i=1;i<=n*2;i++){
            prefix[i]=prefix[i-1]+nums[(i - 1) % n];
        }

        // 小根堆：存储 {prefix_value, index}
        using pii = pair<int, int>;
        priority_queue<pii,vector<pii>,cmp> minheap;

        minheap.push({0,0});

        int ans=INT_MIN;

        for(int j=1;j<=2*n;j++){
            while(!minheap.empty()&&minheap.top().second<j-n){
                minheap.pop();
            }
            ans=max(ans,prefix[j]-minheap.top().first);
            minheap.push({prefix[j],j});
        }
        return ans;
    }
};

排序

image-20260604103056976

快速排序

数据结构合集 - 快速排序(算法过程, 效率分析, 稳定性分析)_哔哩哔哩_bilibili

核心思想：

  1. 选择基准 (Pivot)：从数列中挑出一个元素。
  2. 分区 (Partition)：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面。
  3. 递归排序 (Recursion)：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。

如何理解排序的稳定性

  • 如果算法只进行相邻元素的比较和交换（如冒泡排序、插入排序、归并排序），它就能小心翼翼地保护相同元素的原始顺序，它是稳定的。
  • 如果算法为了追求速度，允许元素进行远距离的交换或覆盖（如快速排序、选择排序、堆排序），这种“粗暴的跨越”就不可避免地会打乱相同元素的原始顺序，它是不稳定的。

因此快排是不稳定的

复杂度分析：

最坏情况：当每次选取最大值或最小值作为pivot，时间复杂度退化为O(N^2)

最好情况：当数组随机时/每次选取pivot都可以将数组一分为二，时间复杂度位O(nlogn)

优化1：随机选 pivot

  • 作用：防止数组原本有序时退化

挖坑法：使用>=，如果出现大量相同元素，right会将相同元素再遍历一遍，此时退化成O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
from typing import List
import random
def sortArray(nums: List[int]) -> List[int]:
    def half_sort(nums,left,right):
        #优化1：在 left 和 right 之间随机生成一个索引
        index=random.randint(left, right)
        nums[left],nums[index]=nums[index],nums[left]
        pivot=nums[left]
        while left<right:
            # 1. 从右向左找，找到第一个小于 pivot 的数
            while left < right and nums[right] >= pivot:
                right -= 1
            nums[left] = nums[right]  # 把这个数填到左边的坑里，右边形成新坑

            # 2. 从左向右找，找到第一个大于 pivot 的数
            while left < right and nums[left] <= pivot:
                left += 1
            nums[right] = nums[left]  # 把这个数填到右边的坑里，左边形成新坑

        # 3. 当 left == right 时，循环结束，把 pivot 填入最后的坑中
        nums[left] = pivot
        return left
    
    def quick_sort(nums,left,right):
        if right-left<=0:
            return
        pivot_index=half_sort(nums,left,right)
        quick_sort(nums,left,pivot_index-1)
        quick_sort(nums,pivot_index+1,right)
        
    quick_sort(nums,0,len(nums)-1)
    return nums
if __name__ == '__main__':
    print(sortArray([2,2,2,2]))
    print(sortArray([5,1,1,2,0,0]))
image-20260603164311421
image-20260603164606684

Hoare 分区

i，j要先移动是防止相同元素交换后还是一样，造成死循环

保证i右边的数>=pivot，保证h左边的数<=pivot，当遇到不满足的数时进行交换

最后保证左区间所有元素 ≤ 右区间所有元素；

为什么能完美处理大量重复元素？

等于 pivot 的元素会被两个指针同时“抓住”，并通过交换被分散到左右两侧。指针持续向中间移动，最终 j 会落在接近中央的位置，左右子数组规模基本相等。即使数组中所有元素都相等，也能做到每次递归规模减半，递归深度 O(log n)，时间复杂度 O(n log n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
from typing import List
import random
def sortArray(nums: List[int]) -> List[int]:
    def half_sort(nums,left,right):
        index=random.randint(left, right)
        nums[left],nums[index]=nums[index],nums[left]
        pivot=nums[left]
        i,j=left-1,right+1
        while 1:
            i+=1#i，j要先移动是防止相同元素交换后还是一样，造成死循环
            while nums[i]<pivot:#保证i右边的数>=pivot
                i+=1
            j-=1
            while nums[j]>pivot:#保证h左边的数<=pivot
                j-=1
            if i>=j:
                return j
            nums[i],nums[j]=nums[j],nums[i]

    def quick_sort(nums,left,right):
        if right-left<=0:
            return
        pivot_index=half_sort(nums,left,right)
        quick_sort(nums,left,pivot_index)
        quick_sort(nums,pivot_index+1,right)
        
    quick_sort(nums,0,len(nums)-1)
    return nums
if __name__ == '__main__':
    print(sortArray([2,2,2,2]))
    print(sortArray([5,1,1,2,0,0]))

归并排序

数据结构合集 - 归并排序(非递归与递归算法过程, 效率分析, 稳定性分析)_哔哩哔哩_bilibili

image-20260604104858667

归并排序的核心思想就是

  1. 分 (Divide)：将数组从中间一分为二，分别对左右两个子数组进行排序。
  2. 治 (Conquer)：递归地将子数组排序。
  3. 合 (Combine)：将两个已排序的子数组合并成一个有序数组。

空间复杂度 O(n)，时间复杂度 O(n log n)，稳定。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
from typing import List
import random
def sortArray(nums: List[int]) -> List[int]:
    ans=[0]*len(nums)
    def merge_sort(nums,left,right):
        if left>=right:return
        
        mid=(left+right)//2
        merge_sort(nums,left,mid)
        merge_sort(nums,mid+1,right)
        index=left
        i,j=left,mid+1
        while i<=mid and j<=right:
            if nums[i]>nums[j]:
                ans[index]=nums[j]
                index+=1
                j+=1
            else:
                ans[index]=nums[i]
                index+=1
                i+=1
        if i<=mid:
            ans[index:right+1]=nums[i:mid+1]
        else:
            ans[index:right+1]=nums[j:right+1]
        nums[left:right+1]=ans[left:right+1]
    merge_sort(nums,0,len(nums)-1)
        
    return ans

问：代码中的 nums[i] < pivot 和 nums[i] > pivot 能否改成 nums[i] <= pivot 和 nums[i] >= pivot？

答：这个做法会在子数组所有元素相同时，划分后的 j 是子数组最后一个元素的下标，是最不均匀划分，算法会退化至 O(n**2)。

问：代码中的 i <= j 能否改成 i < j？

答：这会算错。来看一个例子 nums=[2,1,3]，pivot=2。左指针 i=1 移动到 i=2，右指针 j=2 因为不满足 i < j 的条件，无法移动。此时我们交换 2 和 nums[j]=3，得到 [3,1,2]，返回 j=2。然而 j=2 左侧有大于 pivot=2 的元素，划分失败。

如果写成 i <= j，那么最终 i=2，j=1。此时我们交换 2 和 nums[j]=1，得到 [1,2,3]，返回 j=1。这样的划分就是正确的。

链表的归并

148. 排序链表 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
using namespace std;
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if(!head)return nullptr;
        if(!head->next){
            return head;
        }
        ListNode* slow=head;
        ListNode* fast=head;
        ListNode* prev=nullptr;

        while (fast&&fast->next)
        {
            prev=slow;
            fast=fast->next->next;
            slow=slow->next;
        }
        
        prev->next=nullptr;

        ListNode* left=sortList(head);
        ListNode* right=sortList(slow);

        return merge(left,right);
    }

    ListNode* merge(ListNode* left,ListNode* right){
        ListNode* dummy=new ListNode();
        ListNode* cur=dummy;
        while (left&&right)
        {
            if(left->val<right->val){
                cur->next=left;
                left=left->next;
            }else{
                cur->next=right;
                right=right->next;
            }
            cur=cur->next;
        }
        if(left)cur->next=left;
        if(right)cur->next=right;
        return dummy->next;
        
    }
};

堆排序

数据结构合集 - 堆与堆排序(算法过程, 效率分析, 稳定性分析)_哔哩哔哩_bilibili

image-20260623120621616
image-20260623121353399

不稳定

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:

        def heap(index,nums,n):
            #维护操作，比较左右节点是否都小于根节点，然后递归
            left=index*2+1
            right=index*2+2
            maxindex=index

            # if left<n and nums[left]>nums[index]:
            #     nums[left],nums[index]=nums[index],nums[left]
            #     heap(left,nums)
            # 先找左右节点哪个最大
            if left<n and nums[left]>nums[maxindex]:
                maxindex=left
            if right<n and nums[right]>nums[maxindex]:
                maxindex=right
            if maxindex!=index:
                #说明有变化，换位置，然后递归
                nums[maxindex],nums[index]=nums[index],nums[maxindex]
                heap(maxindex,nums,n)
        def heap_sort(nums):
            n=len(nums)
            #建堆,从最后一个非叶子节点开始，往下维护大根堆
            for i in range(n//2-1,-1,-1):
                heap(i,nums,n)
            #排序，建堆后，第一个位置一定最大，移动到最后，然后再对第一个建堆维护
            for i in range(n-1,0,-1):
                nums[0],nums[i]=nums[i],nums[0]
                heap(0,nums,i)
            return nums
        
        return heap_sort(nums)

堆排序就是反复建堆的过程是吗，但是最小堆的数据结构，不需要维护数组有序，只要保证第一个元素是最小的就行，大根堆就是维护第一个元素最大

  • 堆的性质：你理解得很对，局部有序，全局无序，只保堆顶。
  • 堆排序的本质：建一次堆（O(N)） + 反复调整堆（N次 O(log N)） = 总时间复杂度 O(N log N)。

堆的方法

  • 上浮 (Sift Up) 专门用于：插入新元素 (heappush)
  • 下沉 (Sift Down) 专门用于：删除堆顶 (heappop) 和 批量建堆 (heapify)

heappush是在列表后面新加一个元素，也就是加一个叶子节点，这个叶子节点要以此查看自己的父亲节点，维护堆的性质，称之为上浮

heappop是弹出最大/最小元素，其实是弹出arr[0]，，但左右子树依旧是保持着堆的性质，那其实思路就是和最后一个叶子节点交换位置，然后利用数组的pop弹出，再进行一次下沉操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class minheap:
    def __init__(self,arr=None):
        self.heap=[]
        if arr:
            self.heapify(arr)

    def __heapdown(self,index:int,n:int):
        left=index*2+1
        right=index*2+2
        minindex=index
        if right<n and self.heap[right]<self.heap[minindex]:
            minindex=right
        if left<n and self.heap[left]<self.heap[minindex]:
            minindex=left
        if minindex!=index:
            self.heap[minindex],self.heap[index]=self.heap[index],self.heap[minindex]
            self.__heapdown(minindex,n)
    
    def heapify(self,arr:list):
        self.heap=arr[:]
        n = len(self.heap)
        # 从最后一个非叶子节点开始，逆序遍历，依次下沉
        for i in range(n // 2 - 1, -1, -1):
            self.__heapdown(i, n)

    def heappop(self):
        if not self.heap:  # ✅ 添加空堆检查
            return None
            
        if len(self.heap) == 1:  # ✅ 只有一个元素时直接弹出
            return self.heap.pop()
        #先和最后一个元素交换，然后pop，再下沉操作
        n=len(self.heap)-1
        self.heap[0],self.heap[n]=self.heap[n],self.heap[0]
        #下沉操作
        self.__heapdown(0,n)# ✅ 修正：传入 n 而不是 n-1，这个n是数量，不是下标

        #返回最大值并弹出
        return self.heap.pop()
    def heappush(self,num:int):
        self.heap.append(num)
        #进行上浮操作，以此比较父亲节点
        index=len(self.heap)-1
        while index>0:
            parent=(index-1)//2
            if self.heap[index]<self.heap[parent]:
                self.heap[index],self.heap[parent]=self.heap[parent],self.heap[index]
                index=parent
            else:
                break

二叉树

前中后序遍历

遍历方式 所属搜索类型 核心数据结构 遍历顺序特征 典型应用场景
前序遍历 DFS 栈 (Stack) / 递归 根 → 左 → 右 复制树、序列化、生成前缀表达式
中序遍历 DFS 栈 (Stack) / 递归 左 → 根 → 右 二叉搜索树(BST)的排序输出
后序遍历 DFS 栈 (Stack) / 递归 左 → 右 → 根 删除树、计算目录大小、生成后缀表达式
层序遍历 BFS 队列 (Queue) 从上到下，从左到右按层访问 求树的最小深度、Z字形打印、寻找最短路径
  • 前序（非递归）：用栈。根节点入栈 →→ 弹出并访问 →→ 右子节点入栈 →→ 左子节点入栈（保证左先出）。
  • 中序（非递归）：用栈。一路向左将节点压入栈 →→ 弹出并访问 →→ 转向右子树。
  • 后序（非递归）：用栈。通常需要记录上一个访问的节点，或者使用“根 →→ 右 →→ 左”的顺序入栈，最后将结果数组反转，得到“左 →→ 右 →→ 根”。

前序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
	#递归版
    def preorderTraversal(root: Optional[TreeNode]) -> List[int]:
        ans=[]
        def dfs(node:TreeNode):
            if not node:
                return
            ans.append(node.val)
            if node.left:dfs(node.left)
            if node.right:dfs(node.right)
        dfs(root)
        return ans
    #栈
    def preorderTraversal_stack(root: Optional[TreeNode]) -> List[int]:
        ans=[]
        stack=[]
        stack.append(root)
        while stack:
            node:TreeNode=stack.pop()
            if not node:
                continue
            ans.append(node.val)
            if node.right:stack.append(node.right)#注意和dfs的差别
            if node.left:stack.append(node.left)
        return ans

中序遍历栈的写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        TreeNode* curr = root;
        
        // 当 curr 不为空 或 栈不为空 时继续
        while (curr != nullptr || !st.empty()) {
            
            // 第1步：一路向左，全部压栈
            while (curr != nullptr) {
                st.push(curr);
                curr = curr->left;
            }
            
            // 第2步：弹出栈顶（最左节点），访问它
            curr = st.top();
            st.pop();
            result.push_back(curr->val);  // 访问节点
            
            // 第3步：转向右子树
            curr = curr->right;
        }
        
        return result;
    }
};

层序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def levelOrder(root: Optional[TreeNode]) -> List[List[int]]:
        ans=[]
        queue=deque()
        if not root:return ans
        queue.append(root)
        while queue:
            n=len(queue)
            temp=[]
            for _ in range(n):
                node:TreeNode=queue.popleft()
                if not node:continue
                temp.append(node.val)
                if node.left:queue.append(node.left)
                if node.right:queue.append(node.right)
            ans.append(temp)
        return ans

二叉树的构造(前序中序、后序中序、层序中序构造二叉树)

数据结构合集 - 二叉树的构造(前序中序、后序中序、层序中序构造二叉树)_哔哩哔哩_bilibili

image-20260605101610954
image-20260605130441466 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def buildTree(preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        if not preorder and not inorder:
            return None
        hashmap={}
        for index,val in enumerate(inorder):
            hashmap[val]=index
        n=len(preorder)
        def dfs(in_left,in_right,pre_left,pre_right):
            if in_right-in_left<0:
                return None
            pivot_index=hashmap[preorder[pre_left]]
            node=TreeNode()
            node.val=preorder[pre_left]
            size=pivot_index-in_left
            node.left=dfs(in_left,pivot_index-1,pre_left+1,pre_left+size)
            node.right=dfs(pivot_index+1,in_right,pre_left+size+1,pre_right)

            return node
        root:TreeNode=dfs(0,n-1,0,n-1)


        return root

二叉搜索树

对于树中的任意一个节点，必须同时满足以下三个条件：

  1. 左小：它左子树上的所有节点值，都严格小于它自己的值。
  2. 右大：它右子树上的所有节点值，都严格大于它自己的值。
  3. 递归：它的左子树和右子树，也必须分别是二叉搜索树。
1
2
3
4
5
6
7
    8
   / \
  3   10
 / \    \
1   6    14
   / \   /
  4   7 13

考点 1：中序遍历 = 升序数组（最重要！）

对 BST 进行中序遍历（左 -> 根 -> 右），得到的结果一定是一个从小到大排好序的数组！ * 上面那棵树的中序遍历：1, 3, 4, 6, 7, 8, 10, 13, 14。 * 应用：很多题目让你找 BST 的第 K 小元素、验证是不是 BST、找两个节点的差值最小，全部用中序遍历解决。

考点 2：查找/插入/删除不需要遍历全树

普通二叉树找东西要遍历所有节点（O(N)），但 BST 只需要顺着“左小右大”的路径走，不需要回溯，一路走下去就行（O(H)，H是树高）。

考点 3：警惕“退化成链表”

如果插入的数据本来就是有序的（比如 1, 2, 3, 4, 5），BST 会变成这样： 

1
2
3
4
5
6
7
1
 \
  2
   \
    3
     \
      4
这时候它退化成了链表，查找速度变成了 O(N)。 (为了解决这个问题，大佬们发明了“平衡二叉搜索树”，如 AVL树、红黑树。C++ 里的 set 和 map 底层就是红黑树。)

完全二叉树

类型 定义 形状 节点数公式
满二叉树 (Full/Perfect) 每一层都填满了，最后一层也是满的。 完美的三角形 2h − 1
完全二叉树 (Complete) 上面都满了，最后一层可以不满，但必须靠左。 缺了右下角的三角形 无固定公式，但在 2h − 1 到 2h − 1 之间

C++ 里的 priority_queue（优先队列），底层就是用完全二叉树实现的，而且它通常不用指针（TreeNode*）来存，而是用数组（vector）来存！

数组下标的魔法公式（假设根节点下标为 i）：

  • 左孩子的下标是：2 * i + 1
  • 右孩子的下标是：2 * i + 2
  • 父节点的下标是：(i - 1) / 2
image-20260627113832645

模式匹配

kmp

最浅显易懂的 KMP 算法讲解_哔哩哔哩_bilibili

帮你把KMP算法学个通透！（理论篇）_哔哩哔哩_bilibili

nextval 数组是 KMP 算法的究极优化体。它通过在预处理时加入一步判断，消除了模式串中连续重复字符导致的无意义回溯。当字符发生错配时，nextval 能让指针一步跳跃到真正有效的下一个截然不同的待匹配字符，将最坏情况下的回溯开销降到了极致。”

28. 找出字符串中第一个匹配项的下标 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<int> next;
    void getnext(string s){
        int j=0;//前缀指针
        for(int i=1;i<s.size();i++){
            //找匹配的前缀
            while (j>0&&s[j]!=s[i])
            {
                j=next[j-1];//看0到j-1已经匹配的
            }
            if(s[i]==s[j]){
                j++;
            }
            next[i]=j;

            
        }
    }
    int strStr(string haystack, string needle) {
        next=vector(needle.size(),0);
        getnext(needle);
        int i=0,j=0;
        while (i<haystack.size()&&j<needle.size())
        {
            if(haystack[i]==needle[j]){
// 分支 1：匹配成功，i 和 j 一起愉快地右移
                i++;
                j++;
            } else if (j > 0) {
                // 分支 2：匹配失败，但 j 还能回退 -> i 保持不变！j 查表跳转
                j = next[j - 1];
            } else {
                // 分支 3：匹配失败，且 j 已经在起点 0 了 -> i 只能无奈右移
                i++;
            }
        }
        

        if(j==needle.size()){
            return i-needle.size();
        }
        return -1;
    }
};

python

字符串

split()

将字符串按照指定的分隔符“切割”，并返回一个列表（List）

1
str.split(sep=None, maxsplit=-1)
  • sep：分隔符（字符串）。如果不传，默认按空白字符（空格、换行符 \n、制表符 \t 等）分割。
  • maxsplit：最大分割次数。如果不传，默认 -1（表示不限制次数，有多少切多少）。

join()

是把列表（或任何可迭代对象）“拼”成字符串

1
2
3
4
chars = ['H', 'e', 'l', 'l', 'o']
word = "".join(chars)
print(word)  
# 输出: Hello

isdigit()

判断一个字符串是否“完全由数字字符组成”。 如果是，返回 True；只要包含一个非数字字符（或者字符串为空），就返回 False。

栈，队列

deque

deque 是 double-ended queue（双端队列）的缩写

deque 专门为两端的高效操作进行了优化，在头部和尾部添加、删除元素的速度都非常快，都是 O(1) 的时间复杂度。

1
from collections import deque
  • append(x)：从右边（尾部） 添加元素。
  • appendleft(x)：从左边（头部） 添加元素。
  • pop()：从右边（尾部） 移除并返回元素。
  • popleft()：从左边（头部） 移除并返回元素。

random 模块

random.randint(a, b)：生成一个 [a, b] 范围内的随机整数（包含 a 和 b）。

堆

heapq 是 Python 的内置标准库模块，用于实现堆（Heap）*数据结构，特别适合做*优先队列。

  1. 默认是最小堆（Min Heap）：堆顶永远是最小元素
  2. 基于列表实现：直接在普通 list 上操作
  3. 时间复杂度：插入和删除都是 O(log n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
import heapq
# 方法1：空列表 + heappush
heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 4)
print(heap)  # 输出: [1, 3, 4]  堆顶是最小值 1

# 方法2：heapify 快速建堆
nums = [3, 1, 4, 1, 5, 9, 2, 6]
heapq.heapify(nums)  # 原地转换，O(n)

# 弹出最小值 O(log n)
min_val = heapq.heappop(heap)
函数 说明 时间复杂度
heappush(heap, item) 插入元素 O(log n)
heappop(heap) 弹出最小值 O(log n)

cpp

排序

1
2
3
4
5
6
7
8
vector<int> nums = {5, 2, 8, 1, 9};

// 1. 默认升序（从小到大）
sort(nums.begin(), nums.end()); 
// 结果: [1, 2, 5, 8, 9]

// 2. 降序（从大到小）：传入内置的 greater<int>()
sort(nums.begin(), nums.end(), greater<int>());

结构体 (Struct / Class) 的排序

1
2
3
4
5
6
7
8
9
10
11
12
13
struct Student {
    string name;
    int score;

    // 重载 < 运算符
    bool operator<(const Student& other) const {
        return score > other.score; // 按分数降序（分数高的排前面）
    }
};

// 使用时，直接调用 sort 即可自动生效
vector<Student> students = {{"Alice", 85}, {"Bob", 92}};
sort(students.begin(), students.end());

自定义函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 1. 定义比较函数
// 规则：当 a 应该排在 b 前面时返回 true
bool compareIntervals(const vector<int>& a, const vector<int>& b) {
    if (a[0] != b[0]) {
        return a[0] < b[0]; // 第一维升序
    }
    return a[1] > b[1];     // 第二维降序
}

int main() {
    vector<vector<int>> intervals = {{1, 3}, {2, 6}, {1, 5}, {8, 10}};

    // 2. 调用 sort，直接传入函数名 compareIntervals（注意：不加括号）
    sort(intervals.begin(), intervals.end(), compareIntervals);

    return 0;
}

堆

在 C++ 中，建立最小堆（Min-Heap）最常用的工具是标准库 <queue> 中的 priority_queue（优先队列）。

默认情况下，priority_queue 是最大堆（大的元素在顶端）。要变成最小堆，你需要修改它的模板参数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <queue>
#include <vector>
#include <functional> // 包含 greater

// 语法：priority_queue<数据类型, 容器类型, 比较方式>
priority_queue<int, vector<int>, greater<int>> minHeap;

// 1. 定义一个比较结构体
struct cmp {
    // 注意：这里的参数类型要和堆里存的一样，是 ListNode*
    // 返回 true 表示 a 的优先级比 b 低（a 应该沉下去，b 浮上来）
    bool operator()(ListNode* a, ListNode* b) {
        return a->val > b->val; 
    }
};

// 2. 声明最小堆
// 参数1: 存的数据类型 (ListNode*)
// 参数2: 底层容器 (vector<ListNode*>)
// 参数3: 刚才写的比较规则 (cmp)
priority_queue<ListNode*, vector<ListNode*>, cmp> minHeap;

struct cmp {
        bool operator()(const pair<int, int>& a, const pair<int, int>& b) {
            return a.first > b.first; // 小顶堆：first 越小优先级越高
        }
    };

万能头文件

1
#include <bits/stdc++.h>

结构体

1
2
3
4
5
6
7
struct node
        {
            int val;
            int index1;
            int index2;
            node(int v,int i1,int i2):val(v),index1(i1),index2(i2){}
        };

{}的用法：初始化对象 / 容器；函数传参（上下文推导）

1
2
3
4
5
6
7
8
9
10
// 1. 容器
vector<int> v = {1, 2, 3};          // 列表初始化
map<string, int> m = {{"A", 1}};    // 嵌套花括号初始化键值对

// 2. 结构体 / 聚合类（所有成员 public）
struct Point { int x; int y; };
Point p = {10, 20};                 // ✅ 完美匹配

// 3. std::pair / std::tuple
pair<int, string> p = {1, "hello"}; // ✅ 合法，编译器自动转成 pair
1
2
3
4
5
6
7
8
9
10
queue<pair<TreeNode*, int>> q;

// ❌ 错误：不能直接 auto 接收
auto temp = {root, root->val}; 

// ✅ 正确：push 函数要求 pair，编译器看到目标类型，自动把 {} 转换成 pair
q.push({root, root->val}); 

// ✅ 正确：make_pair 明确要求返回 pair
auto temp = make_pair(root, root->val);

auto用法

拯救冗长的 STL 类型

1
2
3
4
5
6
7
priority_queue<pair<int, pair<int, int>>, vector<...>, cmp> pq;

// 不用 auto（折磨）：
pair<int, pair<int, int>> top_element = pq.top(); 

// 用 auto（清爽）：
auto top_element = pq.top(); // 编译器自动推导

遍历容器

1
2
3
4
5
6
vector<string> names = {"Alice", "Bob"};

// 爽！直接遍历
for (auto name : names) {
    cout << name << endl;
}

结构化绑定

1
2
3
4
5
queue<pair<TreeNode*, int>> q;
q.push({root, root->val});

// 爽！直接解包（注意这里是方括号 []，不是花括号 {}）
auto [node, current_sum] = q.front();

哈希表

unordered_map（键值对哈希表）

相当于 Python 的 dict。用来存 Key -> Value 的映射。

1
2
3
4
5
6
7
#include <unordered_map>
using namespace std;

// 语法：unordered_map<键的类型, 值的类型> 变量名;
unordered_map<int, string> myMap;       // 键是 int，值是 string
unordered_map<string, int> wordCount;   // 键是 string，值是 int
unordered_map<char, vector<int>> charMap; // 键是 char，值是 vector

增 & 改（最常用）

使用 [] 运算符是最简单直接的方式。 

1
2
3
4
5
unordered_map<int, int> map;

map[1] = 100;  // 新增：键为 1，值为 100
map[2] = 200;  // 新增：键为 2，值为 200
map[1] = 999;  // 修改：键 1 已存在，值被覆盖为 999

查（判断键是否存在）

这是刷题时最高频的操作，主要有两种写法：

写法 A：使用 count()（最推荐，简单直观） count(key) 会返回 1（存在）或 0（不存在）。 

1
2
3
4
5
if (map.count(1)) {
    cout << "键 1 存在！" << endl;
} else {
    cout << "键 1 不存在！" << endl;
}

写法 B：使用 find()（返回迭代器） find(key) 会返回一个迭代器。如果找不到，它会返回 map.end()。

1
2
3
if (map.find(1) != map.end()) {
    cout << "键 1 存在！" << endl;
}

删

1
2
3
// 删除指定 key
size_t count = mp.erase("apple"); 
// 返回值 count：删除了 1 个元素；如果 key 不存在则返回 0

遍历操作

在 C++ 中，遍历 unordered_map 通常使用范围 for 循环（配合 auto）。 遍历时，每一个元素都是一个 pair（键值对），可以通过 .first 获取键，.second 获取值。

1
2
3
4
5
6
unordered_map<string, int> scores = {{"Alice", 90}, {"Bob", 85}, {"Charlie", 95}};

// 推荐写法：使用 const auto& 避免拷贝，提高效率
for (const auto& pair : scores) {
    cout << "姓名: " << pair.first << ", 分数: " << pair.second << endl;
}

(注意：unordered_map 是无序的，遍历出来的顺序不一定是你插入的顺序！)

vector

insert()

1
vec.insert(插入位置的迭代器, 插入的数量, 要插入的值);

初始化

1
2
3
4
vector<类型> 变量名(元素个数, 初始值);
vector<int> v(10, 0); 

vector<int> v = {1, 2, 3, 4, 5};

单调队列

核心特性只有八个字：队内元素，单调有序。

  • 单调递增队列：队头到队尾的元素依次变大（队头始终是当前窗口的最小值）。
  • 单调递减队列：队头到队尾的元素依次变小（队头始终是当前窗口的最大值）。

为什么需要单调队列？

假设给你一个大小为 N 的数组，让你求所有长度为 K 的滑动窗口里的最小值：

  • 暴力做法：每移动一步，遍历窗口里的 K 个元素找最小值，时间复杂度为 𝒪(N × K)。
  • 优先队列（大/小顶堆）：可以 O(log K) 拿到最值，但堆不支持任意删除过期元素，时间复杂度 𝒪(Nlog K)。
  • 单调队列：能以 𝒪(1) 均摊时间 实时维护并获取窗口的最值！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
deque<int> q;
// 1. 【过期校验】队头元素太老了，踢出窗口外
while (!q.empty() && 队头超出了窗口范围) {
    q.pop_front();
}

// 2. 【维护单调性】队尾元素比新元素劣质，全部从队尾淘汰
while (!q.empty() && 队尾元素 >= 新元素) {
    q.pop_back();
}

// 3. 【新元素入队】
q.push_back(新元素);

// 此时：q.front() 必定是当前窗口内的最佳最值！