信创考试知识点

<!DOCTYPE html>

信创考试知识点 ← 返回首页

C++ STL 速记 & 编程考题模板

一、C++ STL 核心容器速记

1. vector<T> — 动态数组

操作代码说明
初始化vector<int> v;
vector<int> v{1,2,3};		空 / 列表初始化
尾部增删v.push_back(x);O(1) 均摊
随机访问v[i];下标访问
大小v.size();
v.empty();
删除v.erase(pos);O(n)
清空v.clear();
排序sort(v.begin(), v.end());升序
二分查找auto it = lower_bound(v.begin(), v.end(), x);需有序，返回 ≥x 的首个位置
// vector 遍历
for (int x : v) { /* ... */ }
for (int i = 0; i < v.size(); ++i) { v[i]; }
for (auto it = v.begin(); it != v.end(); ++it) { *it; }

// 自定义排序
sort(v.begin(), v.end(), [](int a, int b) { return a > b; });

// 去重（需先排序）
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());

2. string — 字符串

操作代码说明
子串s.substr(pos, len);O(len)，不写len取到末尾
查找s.find(t);返回下标或 string::npos
替换s.replace(pos, len, t);
删除s.erase(pos, len);
数值转换stoi(s);
to_string(x);		string ↔ 数值
C串s.c_str();返回 const char*
连接s += t;
比较s == t;按字典序
// 常用：按分隔符拆分字符串
vector<string> split(const string& s, char delim) {
    vector<string> res;
    stringstream ss(s);
    string token;
    while (getline(ss, token, delim)) res.push_back(token);
    return res;
}

// 常用：翻转字符串
reverse(s.begin(), s.end());

// 常用：判断字符类型
isalpha(c); isdigit(c); isalnum(c); isspace(c);
toupper(c); tolower(c);

// string → int（十六进制）
int x = stoi("1A", nullptr, 16);  // x = 26

3. map<K,V> — 有序映射（红黑树）

操作代码说明
插入/更新m[k] = v;不存在则插入默认值
删除m.erase(k);
查找m.find(k);
m.count(k);		find返回迭代器 / count返回0或1
二分m.lower_bound(k);仅 map 支持
遍历for (auto& [k,v] : m) { }按键升序遍历
陷阱：m[k] 若 k 不存在会自动插入默认值。仅判断存在用 m.find(k) != m.end() 或 m.count(k)。
// 自定义键排序（降序）
map<int, string, greater<int>> m;

// 按 value 排序 → 转 vector
vector<pair<int,string>> v(m.begin(), m.end());
sort(v.begin(), v.end(), [](auto& a, auto& b) {
    return a.second < b.second;
});

4. unordered_map<K,V> — 哈希映射

操作代码说明
基本操作同 map：[] insert erase find count均摊 O(1)
不支持lower_bound / upper_bound哈希表无序
遍历for (auto& [k,v] : um) { }无序
选择：不需要有序时优先用 unordered_map，O(1) vs O(log n)。需要按序遍历或二分时用 map。
// 统计频率
unordered_map<string, int> freq;
for (auto& w : words) freq[w]++;

// 自定义哈希（pair为例）
struct pair_hash {
    template<class T1, class T2>
    size_t operator()(const pair<T1,T2>& p) const {
        return hash<T1>{}(p.first) ^ (hash<T2>{}(p.second) << 1);
    }
};
unordered_map<pair<int,int>, int, pair_hash> um;

5. priority_queue<T> — 优先队列（堆）

操作代码说明
压入pq.push(x);O(log n)
弹出pq.pop();O(log n)，无返回值
堆顶pq.top();O(1)
大小pq.size();
// 默认：最大堆（大顶堆）
priority_queue<int> pq;           // top() 返回最大值
priority_queue<int, vector<int>, less<int>> pq;  // 等价

// 最小堆
priority_queue<int, vector<int>, greater<int>> min_pq;

// 自定义比较器（用 decltype + lambda，C++20前需传lambda给构造函数）
auto cmp = [](int a, int b) { return a > b; };
priority_queue<int, vector<int>, decltype(cmp)> pq(cmp);

// 存储 pair，按 second 排序（最小堆）
using P = pair<string, int>;
auto cmp = [](P& a, P& b) { return a.second > b.second; };
priority_queue<P, vector<P>, decltype(cmp)> pq(cmp);

// 手写结构体比较器
struct Node { int val, idx; };
struct Cmp {
    bool operator()(Node& a, Node& b) { return a.val < b.val; } // 大顶堆
};
priority_queue<Node, vector<Node>, Cmp> pq;
记忆口诀：默认 less → 大顶堆（大的在顶）。greater → 小顶堆（小的在顶）。自定义 cmp 返回 true 表示"a 优先级低于 b"。

6. 其他常用 STL 速查

// set / unordered_set — 集合
set<int> s;                    // 有序，O(log n)
unordered_set<int> us;        // 哈希，O(1)
s.insert(x); s.erase(x);
s.count(x);                   // 是否存在
s.lower_bound(x);             // 仅 set

// stack — 栈
stack<int> st;
st.push(x); st.pop(); st.top(); st.empty();

// queue — 队列
queue<int> q;
q.push(x); q.pop(); q.front(); q.back(); q.empty();

// deque — 双端队列
deque<int> dq;
dq.push_back(x); dq.push_front(x);
dq.pop_back(); dq.pop_front();
dq.front(); dq.back();

// pair
pair<int,string> p{1, "hello"};
p.first; p.second;
auto [a, b] = p;              // 结构化绑定 (C++17)

// algorithm 常用
sort(b, e);                   // 排序
sort(b, e, cmp);              // 自定义排序
reverse(b, e);                // 翻转
max_element(b, e);            // 返回最大元素迭代器
min_element(b, e);
accumulate(b, e, 0);          // 求和 <numeric>
next_permutation(b, e);       // 全排列
binary_search(b, e, x);       // 二分判断存在
lower_bound(b, e, x);         // 首个 ≥x
upper_bound(b, e, x);         // 首个 >x
nth_element(b, nth, e);       // 第n小的放到正确位置

二、编程考题模板

2.1 十六进制 / 数值双向转换

// ====== 数值 → 十六进制字符串 ======
// 方法1：stringstream
#include <sstream>
#include <iomanip>
string to_hex(int num) {
    stringstream ss;
    ss << hex << num;
    return ss.str();                      // 255 → "ff"
}
string to_hex_upper(int num) {
    stringstream ss;
    ss << hex << uppercase << num;
    return ss.str();                      // 255 → "FF"
}

// 方法2：snprintf
char buf[32];
snprintf(buf, sizeof(buf), "%x", num);    // "ff"
snprintf(buf, sizeof(buf), "%X", num);    // "FF"
snprintf(buf, sizeof(buf), "%08x", num);  // 定宽补零 "000000ff"

// 方法3：C++17 to_chars (高性能)
char buf[32];
to_chars(buf, buf + 32, num, 16);

// ====== 十六进制字符串 → 数值 ======
// 方法1：stoi / stoll
int x = stoi("ff", nullptr, 16);          // 255
int x = stoi("1A", nullptr, 16);          // 26
long long y = stoll("7FFFFFFF", nullptr, 16);

// 方法2：stringstream
stringstream ss("1A");
int x; ss >> hex >> x;                    // 26

// 方法3：strtol
long x = strtol("ff", nullptr, 16);        // 255

// ====== 任意进制转换 ======
// 数值 → K进制字符串
string to_base(int num, int base) {
    if (num == 0) return "0";
    string s;
    const string digits = "0123456789ABCDEF";
    while (num > 0) {
        s = digits[num % base] + s;
        num /= base;
    }
    return s;
}

// K进制字符串 → 数值
int from_base(const string& s, int base) {
    int num = 0;
    for (char c : s) {
        num = num * base + (isdigit(c) ? c-'0' : toupper(c)-'A'+10);
    }
    return num;
}

// ====== 十六进制字符串 ↔ 字节数组 ======
// hex → bytes: "0A1F" → {0x0A, 0x1F}
vector<uint8_t> hex_to_bytes(const string& hex) {
    vector<uint8_t> bytes;
    for (size_t i = 0; i + 1 < hex.length(); i += 2)
        bytes.push_back((uint8_t)stoi(hex.substr(i, 2), nullptr, 16));
    return bytes;
}

// bytes → hex: {0x0A, 0x1F} → "0a1f"
string bytes_to_hex(const vector<uint8_t>& bytes) {
    stringstream ss;
    for (uint8_t b : bytes)
        ss << hex << setw(2) << setfill('0') << (int)b;
    return ss.str();
}

2.2 滑动窗口 / 时间窗口阈值检测

// ====== 基础：定长滑动窗口 ======
// 求长度为k的窗口最大和
int max_window_sum(vector<int>& nums, int k) {
    int sum = 0, ans = 0;
    for (int i = 0; i < nums.size(); ++i) {
        sum += nums[i];
        if (i >= k) sum -= nums[i - k];
        if (i >= k - 1) ans = max(ans, sum);
    }
    return ans;
}

// ====== 不定长滑动窗口（双指针） ======
// 最长无重复子串
int length_of_longest_substring(string s) {
    int ans = 0, l = 0;
    unordered_map<char, int> pos;
    for (int r = 0; r < s.size(); ++r) {
        if (pos.count(s[r])) l = max(l, pos[s[r]] + 1);
        pos[s[r]] = r;
        ans = max(ans, r - l + 1);
    }
    return ans;
}

// 和 ≥ target 的最短子数组长度
int min_subarray_len(int target, vector<int>& nums) {
    int ans = INT_MAX, sum = 0, l = 0;
    for (int r = 0; r < nums.size(); ++r) {
        sum += nums[r];
        while (sum >= target) {
            ans = min(ans, r - l + 1);
            sum -= nums[l++];
        }
    }
    return ans == INT_MAX ? 0 : ans;
}

// ====== 时间窗口阈值检测 ======
// 给定时间戳数组和窗口大小w，检测窗口内事件数是否≥阈值
bool check_threshold(vector<int>& timestamps, int window_ms, int threshold) {
    int l = 0;
    for (int r = 0; r < timestamps.size(); ++r) {
        while (timestamps[r] - timestamps[l] > window_ms) l++;
        if (r - l + 1 >= threshold) return true;  // 触发
    }
    return false;
}

// 日志限流：每秒最多允许maxReq条
bool ratelimit(vector<int>& requests, int max_req_per_sec) {
    deque<int> window;
    for (int t : requests) {
        while (!window.empty() && t - window.front() >= 1000)
            window.pop_front();
        window.push_back(t);
        if (window.size() > max_req_per_sec) return false;
    }
    return true;
}

// ====== 滑动窗口统计频次 ======
// 统计每个长度为k的窗口中不同字符数 / 某字符出现次数
vector<int> window_freq_count(const string& s, int k) {
    int cnt[26] = {};
    vector<int> ans;
    for (int i = 0; i < s.size(); ++i) {
        cnt[s[i] - 'a']++;
        if (i >= k) cnt[s[i - k] - 'a']--;
        if (i >= k - 1) {
            int uniq = 0;
            for (int c : cnt) if (c > 0) uniq++;
            ans.push_back(uniq);
        }
    }
    return ans;
}

// 用 unordered_map 统计任意字符（非小写字母）
vector<int> window_freq_generic(const string& s, int k) {
    unordered_map<char, int> cnt;
    vector<int> ans;
    for (int i = 0; i < s.size(); ++i) {
        cnt[s[i]]++;
        if (i >= k && --cnt[s[i - k]] == 0)
            cnt.erase(s[i - k]);
        if (i >= k - 1) ans.push_back(cnt.size());
    }
    return ans;
}

// 定宽窗口中统计频次是否满足某条件（如窗口内某字符频次≥T）
bool window_freq_over_T(const string& s, int k, char target, int T) {
    int cnt = 0;
    for (int i = 0; i < s.size(); ++i) {
        if (s[i] == target) cnt++;
        if (i >= k && s[i - k] == target) cnt--;
        if (i >= k - 1 && cnt >= T) return true;
    }
    return false;
}

2.3 Top K 高频词统计

priority_queue TopK 思路： 1. 先用 unordered_map 统计每个元素的频次
2. 维护一个大小为 k 的小顶堆（堆顶是第k大，堆内是当前top k）
3. 遍历频次表：前 k 个直接入堆；之后若当前频次 > 堆顶频次，则 pop 堆顶再 push 当前
4. 最后堆中 k 个元素即答案（出堆顺序是升序，需反转）
—— 复杂度 O(n log k)，适合 k 远小于 n 的场景
// ====== 方法1：unordered_map + 最小堆（O(n log k)） ======
vector<string> top_k_frequent(vector<string>& words, int k) {
    unordered_map<string, int> freq;
    for (auto& w : words) freq[w]++;

    auto cmp = [](auto& a, auto& b) {
        // 频次低的优先（小顶堆），频次相同则字典序大的优先
        return a.second > b.second ||
               (a.second == b.second && a.first < b.first);
    };
    priority_queue<pair<string,int>, vector<pair<string,int>>, decltype(cmp)> pq(cmp);

    for (auto& [w, c] : freq) {
        pq.push({w, c});
        if (pq.size() > k) pq.pop();
    }

    vector<string> ans;
    while (!pq.empty()) {
        ans.push_back(pq.top().first);
        pq.pop();
    }
    reverse(ans.begin(), ans.end());  // 从高到低
    return ans;
}

// ====== 方法2：nth_element（O(n)，无需完全排序） ======
vector<string> top_k_by_nth(vector<string>& words, int k) {
    unordered_map<string, int> freq;
    for (auto& w : words) freq[w]++;

    vector<pair<string,int>> entry(freq.begin(), freq.end());
    if (k < entry.size())
        nth_element(entry.begin(), entry.begin()+k, entry.end(),
            [](auto& a, auto& b) { return a.second > b.second; });
    sort(entry.begin(), entry.begin()+k,
        [](auto& a, auto& b) { return a.second > b.second; });

    vector<string> ans;
    for (int i = 0; i < k && i < entry.size(); ++i)
        ans.push_back(entry[i].first);
    return ans;
}

// ====== 大数据量：桶排序（频次为下标） ======
vector<string> top_k_bucket(vector<string>& words, int k) {
    unordered_map<string, int> freq;
    for (auto& w : words) freq[w]++;

    int n = words.size();
    vector<vector<string>> buckets(n + 1);
    for (auto& [w, c] : freq) buckets[c].push_back(w);

    vector<string> ans;
    for (int i = n; i > 0 && ans.size() < k; --i)
        for (auto& w : buckets[i])
            if (ans.size() < k) ans.push_back(w);
    return ans;
}

2.4 字符串去重、合并与拆分

// ====== 字符串按分隔符拆分 ======
vector<string> split(const string& s, char delim) {
    vector<string> res;
    stringstream ss(s);
    string token;
    while (getline(ss, token, delim)) res.push_back(token);
    return res;
}

vector<string> split(const string& s, const string& delim) {
    vector<string> res;
    size_t l = 0, r;
    while ((r = s.find(delim, l)) != string::npos) {
        if (r > l) res.push_back(s.substr(l, r - l));
        l = r + delim.length();
    }
    if (l < s.size()) res.push_back(s.substr(l));
    return res;
}

// ====== 字符串合并 ======
string join(vector<string>& parts, const string& delim) {
    if (parts.empty()) return "";
    string res = parts[0];
    for (int i = 1; i < parts.size(); ++i)
        res += delim + parts[i];
    return res;
}

// ====== 字符串去重（保留首次出现） ======
string dedup_chars(const string& s) {
    bool seen[256] = {};
    string res;
    for (char c : s)
        if (!seen[(unsigned char)c]) {
            seen[(unsigned char)c] = true;
            res += c;
        }
    return res;
}

// 数组中去重（字符串）
vector<string> dedup(vector<string>& v) {
    unordered_set<string> seen;
    vector<string> res;
    for (auto& s : v)
        if (seen.insert(s).second) res.push_back(s);
    return res;
}

// ====== 去除首尾空格 ======
string trim(const string& s) {
    auto l = s.find_first_not_of(" \t\n\r");
    if (l == string::npos) return "";
    auto r = s.find_last_not_of(" \t\n\r");
    return s.substr(l, r - l + 1);
}

// ====== 统计字符频次 ======
int cnt[26] = {};
for (char c : s) cnt[c - 'a']++;

// ====== 判断回文 ======
bool is_palindrome(const string& s) {
    int l = 0, r = s.size() - 1;
    while (l < r) if (s[l++] != s[r--]) return false;
    return true;
}

2.5 区间重叠判断

// ====== 判断两个区间是否重叠 ======
// 区间 [a,b] 和 [c,d] 重叠 ⟺ a≤d && c≤b
bool is_overlap(int a, int b, int c, int d) {
    return a <= d && c <= b;
}

// ====== 合并所有重叠区间 ======
vector<pair<int,int>> merge_intervals(vector<pair<int,int>>& intervals) {
    if (intervals.empty()) return {};
    sort(intervals.begin(), intervals.end());  // 按start排序
    vector<pair<int,int>> res;
    auto [cur_l, cur_r] = intervals[0];
    for (int i = 1; i < intervals.size(); ++i) {
        auto [l, r] = intervals[i];
        if (l <= cur_r)  // 重叠
            cur_r = max(cur_r, r);
        else {
            res.emplace_back(cur_l, cur_r);
            cur_l = l; cur_r = r;
        }
    }
    res.emplace_back(cur_l, cur_r);
    return res;
}

// ====== 插入新区间后合并 ======
vector<pair<int,int>> insert_and_merge(
    vector<pair<int,int>> intervals, pair<int,int> new_iv) {
    vector<pair<int,int>> res;
    int i = 0, n = intervals.size();
    // 左侧不重叠
    while (i < n && intervals[i].second < new_iv.first)
        res.push_back(intervals[i++]);
    // 重叠区合并
    while (i < n && intervals[i].first <= new_iv.second) {
        new_iv.first  = min(new_iv.first,  intervals[i].first);
        new_iv.second = max(new_iv.second, intervals[i].second);
        i++;
    }
    res.push_back(new_iv);
    // 右侧不重叠
    while (i < n) res.push_back(intervals[i++]);
    return res;
}

// ====== 判断区间集合是否有重叠 ======
bool has_overlap(vector<pair<int,int>>& intervals) {
    if (intervals.size() <= 1) return false;
    sort(intervals.begin(), intervals.end());
    for (int i = 1; i < intervals.size(); ++i)
        if (intervals[i].first <= intervals[i-1].second)
            return true;
    return false;
}

// ====== 求最多重叠数（扫描线） ======
int max_overlap_count(vector<pair<int,int>>& intervals) {
    vector<pair<int,int>> events;  // {time, delta}
    for (auto& [l, r] : intervals) {
        events.emplace_back(l,  1);  // 开始
        events.emplace_back(r, -1);  // 结束（若端点不重叠则 r+1）
    }
    sort(events.begin(), events.end());
    int cur = 0, ans = 0;
    for (auto& [t, d] : events) {
        cur += d;
        ans = max(ans, cur);
    }
    return ans;
}

2.6 二分查找模板

// ====== 标准二分：查找 target ======
int binary_search(vector<int>& nums, int target) {
    int l = 0, r = nums.size() - 1;
    while (l <= r) {
        int mid = l + (r - l) / 2;  // 防溢出
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) l = mid + 1;
        else r = mid - 1;
    }
    return -1;
}

// ====== 第一个 ≥ target（lower_bound） ======
int first_ge(vector<int>& nums, int target) {
    int l = 0, r = nums.size();
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (nums[mid] >= target) r = mid;
        else l = mid + 1;
    }
    return l;  // l == nums.size() 表示不存在
}

// ====== 最后一个 ≤ target ======
int last_le(vector<int>& nums, int target) {
    int l = 0, r = nums.size() - 1, ans = -1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (nums[mid] <= target) { ans = mid; l = mid + 1; }
        else r = mid - 1;
    }
    return ans;
}

// ====== 最大值最小 / 最小值最大（答案二分） ======
// 例：分成m组使最大组和最小
bool can_split(vector<int>& nums, int max_sum, int m) {
    int cnt = 1, sum = 0;
    for (int x : nums) {
        if (sum + x > max_sum) { cnt++; sum = x; }
        else sum += x;
    }
    return cnt <= m;
}
int split_array(vector<int>& nums, int m) {
    int l = *max_element(nums.begin(), nums.end());
    int r = accumulate(nums.begin(), nums.end(), 0);
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (can_split(nums, mid, m)) r = mid;
        else l = mid + 1;
    }
    return l;
}

2.7 DFS / BFS 模板

// ====== DFS（递归） ======
void dfs(int u, vector<vector<int>>& g, vector<bool>& vis) {
    vis[u] = true;
    for (int v : g[u])
        if (!vis[v]) dfs(v, g, vis);
}

// ====== DFS（栈，迭代） ======
void dfs_iter(int start, vector<vector<int>>& g) {
    vector<bool> vis(g.size());
    stack<int> st;
    st.push(start);
    while (!st.empty()) {
        int u = st.top(); st.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (int v : g[u])
            if (!vis[v]) st.push(v);
    }
}

// ====== BFS（最短路径/层序遍历） ======
vector<int> bfs(int start, vector<vector<int>>& g) {
    int n = g.size();
    vector<int> dist(n, -1);
    queue<int> q;
    q.push(start);
    dist[start] = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : g[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
    return dist;
}

// ====== 二维网格DFS ======
int dirs[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
void dfs_grid(int x, int y, vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    if (x < 0 || x >= m || y < 0 || y >= n) return;
    if (grid[x][y] == 0) return;        // 已访问或障碍
    grid[x][y] = 0;                     // 标记已访问
    for (auto& d : dirs) dfs_grid(x+d[0], y+d[1], grid);
}

2.8 并查集 (Union-Find)

class UnionFind {
    vector<int> parent, rank;
public:
    UnionFind(int n) : parent(n), rank(n, 0) {
        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 rx = find(x), ry = find(y);
        if (rx == ry) return;
        // 按秩合并
        if (rank[rx] < rank[ry]) parent[rx] = ry;
        else if (rank[rx] > rank[ry]) parent[ry] = rx;
        else { parent[ry] = rx; rank[rx]++; }
    }

    bool same(int x, int y) { return find(x) == find(y); }

    int count_sets() {
        int cnt = 0;
        for (int i = 0; i < parent.size(); ++i)
            if (parent[i] == i) cnt++;
        return cnt;
    }
};

2.9 单调栈

// ====== 下一个更大元素（单调递减栈） ======
vector<int> next_greater(vector<int>& nums) {
    int n = nums.size();
    vector<int> ans(n, -1);
    stack<int> st;  // 存下标，栈内值单调递减
    for (int i = 0; i < n; ++i) {
        while (!st.empty() && nums[st.top()] < nums[i]) {
            ans[st.top()] = nums[i];
            st.pop();
        }
        st.push(i);
    }
    return ans;
}

// ====== 每日温度（求间隔天数） ======
vector<int> daily_temperatures(vector<int>& T) {
    int n = T.size();
    vector<int> ans(n, 0);
    stack<int> st;
    for (int i = 0; i < n; ++i) {
        while (!st.empty() && T[st.top()] < T[i]) {
            ans[st.top()] = i - st.top();
            st.pop();
        }
        st.push(i);
    }
    return ans;
}

// ====== 柱状图最大矩形（单调递增栈） ======
int largest_rectangle(vector<int>& heights) {
    heights.push_back(0);  // 哨兵
    stack<int> st;
    int ans = 0;
    for (int i = 0; i < heights.size(); ++i) {
        while (!st.empty() && heights[st.top()] > heights[i]) {
            int h = heights[st.top()]; st.pop();
            int w = st.empty() ? i : i - st.top() - 1;
            ans = max(ans, h * w);
        }
        st.push(i);
    }
    heights.pop_back();
    return ans;
}

2.10 前缀和 & 差分

// ====== 一维前缀和 ======
vector<int> prefix(n + 1, 0);
for (int i = 0; i < n; ++i)
    prefix[i + 1] = prefix[i] + nums[i];
// 区间和 [l, r]：prefix[r+1] - prefix[l]

// ====== 二维前缀和 ======
vector<vector<int>> pre(m+1, vector<int>(n+1, 0));
for (int i = 0; i < m; ++i)
    for (int j = 0; j < n; ++j)
        pre[i+1][j+1] = pre[i+1][j] + pre[i][j+1] - pre[i][j] + mat[i][j];
// 子矩阵和 [r1,c1]→[r2,c2]：pre[r2+1][c2+1]-pre[r1][c2+1]-pre[r2+1][c1]+pre[r1][c1]

// ====== 差分数组（区间增减） ======
vector<int> diff(n + 1, 0);
// [l, r] 加 val：
diff[l] += val; diff[r + 1] -= val;
// 还原：
for (int i = 1; i < n; ++i) diff[i] += diff[i-1];

2.11 回溯模板（排列 / 组合 / 子集）

// ====== 通用回溯框架 ======
vector<vector<int>> ans;
vector<int> path;

void backtrack(/* 参数 */) {
    if (/* 终止条件 */) {
        ans.push_back(path);
        return;
    }
    for (/* 每个选择 */) {
        if (/* 剪枝 */) continue;
        path.push_back(choice);       // 做选择
        backtrack(/* 更新参数 */);     // 递归
        path.pop_back();              // 撤销选择
    }
}

// ====== 全排列（无重复） ======
void permute(vector<int>& nums, vector<bool>& used) {
    if (path.size() == nums.size()) { ans.push_back(path); return; }
    for (int i = 0; i < nums.size(); ++i) {
        if (used[i]) continue;
        // 去重：if (i>0 && nums[i]==nums[i-1] && !used[i-1]) continue;
        used[i] = true;
        path.push_back(nums[i]);
        permute(nums, used);
        path.pop_back();
        used[i] = false;
    }
}

// ====== 组合 C(n, k) ======
void combine(int start, int n, int k) {
    if (path.size() == k) { ans.push_back(path); return; }
    for (int i = start; i <= n; ++i) {
        path.push_back(i);
        combine(i + 1, n, k);  // 组合 i+1；排列从0开始
        path.pop_back();
    }
}

// ====== 子集 ======
void subsets(vector<int>& nums, int start) {
    ans.push_back(path);           // 每个节点都是答案
    for (int i = start; i < nums.size(); ++i) {
        path.push_back(nums[i]);
        subsets(nums, i + 1);
        path.pop_back();
    }
}

2.12 位运算常用技巧

// ====== 基础位运算 ======
x & (1 << k)           // 判断第k位是否为1
x |= (1 << k)           // 第k位置1
x &= ~(1 << k)          // 第k位置0
x ^= (1 << k)           // 第k位取反
x & (x - 1)             // 消去最低位的1（Brian Kernighan）
x & -x                  // 取出最低位的1（lowbit）
x ^ x = 0               // 自反性

// ====== 统计1的个数 ======
int popcount(int x) {
    int cnt = 0;
    while (x) { x &= (x - 1); cnt++; }
    return cnt;
}
// 或使用 __builtin_popcount(x) (GCC/Clang)

// ====== 判断奇偶 ======
x & 1                    // 1→奇数，0→偶数

// ====== 乘除2的幂 ======
x << k                  // x * 2^k
x >> k                  // x / 2^k

// ====== 只出现一次的数字 ======
// 数组中有且仅有一个数出现一次，其余都出现两次 → 全异或
int ans = 0;
for (int x : nums) ans ^= x;

// ====== 枚举子集掩码 ======
// 枚举 mask 的所有子集
for (int sub = mask; sub; sub = (sub - 1) & mask) {
    // sub 是 mask 的一个子集
}

2.13 动态规划速记

// ====== 0-1 背包 ======
// dp[i][w] = max(dp[i-1][w], dp[i-1][w-wt[i]] + val[i])
// 一维优化（逆序）：
for (int i = 0; i < n; ++i)
    for (int w = W; w >= wt[i]; --w)
        dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);

// ====== 完全背包（每种无限个） ======
// 一维（正序）：
for (int i = 0; i < n; ++i)
    for (int w = wt[i]; w <= W; ++w)
        dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);

// ====== 最长公共子序列 LCS ======
// dp[i][j] = dp[i-1][j-1]+1            (a[i]==b[j])
//          = max(dp[i-1][j], dp[i][j-1])  (a[i]!=b[j])

// ====== 最长递增子序列 LIS ======
// 方法1：DP O(n²)
// 方法2：贪心+二分 O(n log n)
vector<int> tails;
for (int x : nums) {
    auto it = lower_bound(tails.begin(), tails.end(), x);
    if (it == tails.end()) tails.push_back(x);
    else *it = x;
}
// tails.size() 即 LIS 长度

// ====== 编辑距离 ======
// dp[i][j] = dp[i-1][j-1]              (a[i]==b[j])
//          = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

2.14 链表常用操作

// ====== 反转链表 ======
ListNode* reverse(ListNode* head) {
    ListNode *prev = nullptr, *cur = head;
    while (cur) {
        ListNode* next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}

// ====== 快慢指针找中点 ======
ListNode* middle(ListNode* head) {
    auto *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

// ====== 判断环 ======
bool has_cycle(ListNode* head) {
    auto *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}

// ====== 删除倒数第N个 ======
ListNode* remove_nth_from_end(ListNode* head, int n) {
    ListNode dummy{0, head};
    auto *fast = &dummy, *slow = &dummy;
    for (int i = 0; i <= n; ++i) fast = fast->next;
    while (fast) { fast = fast->next; slow = slow->next; }
    slow->next = slow->next->next;
    return dummy.next;
}

2.15 排序算法速写

// ====== 快速排序（分区） ======
int partition(vector<int>& v, int l, int r) {
    int pivot = v[r], i = l;
    for (int j = l; j < r; ++j)
        if (v[j] < pivot) swap(v[i++], v[j]);
    swap(v[i], v[r]);
    return i;
}
void quicksort(vector<int>& v, int l, int r) {
    if (l >= r) return;
    int p = partition(v, l, r);
    quicksort(v, l, p - 1);
    quicksort(v, p + 1, r);
}

// ====== 归并排序 ======
void mergesort(vector<int>& v, int l, int r, vector<int>& tmp) {
    if (l >= r) return;
    int mid = l + (r - l) / 2;
    mergesort(v, l, mid, tmp);
    mergesort(v, mid + 1, r, tmp);
    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r)
        tmp[k++] = v[i] < v[j] ? v[i++] : v[j++];
    while (i <= mid) tmp[k++] = v[i++];
    while (j <= r)   tmp[k++] = v[j++];
    for (i = l; i <= r; ++i) v[i] = tmp[i];
}

// ====== 堆排序 ======
void heapsort(vector<int>& v) {
    make_heap(v.begin(), v.end());        // 建堆
    sort_heap(v.begin(), v.end());        // 堆排序
}

2.16 表达式解析（中缀求值）

// ====== 中缀表达式求值（+ - * /，含括号） ======
int calculate(const string& s) {
    stack<int> nums;
    stack<char> ops;
    unordered_map<char, int> prio{{'+',1},{'-',1},{'*',2},{'/',2}};

    auto apply = [&]() {
        int b = nums.top(); nums.pop();
        int a = nums.top(); nums.pop();
        char op = ops.top(); ops.pop();
        if (op == '+') nums.push(a + b);
        else if (op == '-') nums.push(a - b);
        else if (op == '*') nums.push(a * b);
        else nums.push(a / b);           // 向零取整
    };

    for (int i = 0; i < s.size(); ++i) {
        if (isspace(s[i])) continue;
        if (isdigit(s[i])) {
            int num = 0;
            while (i < s.size() && isdigit(s[i]))
                num = num * 10 + (s[i++] - '0');
            nums.push(num);
            --i;
        } else if (s[i] == '(') {
            ops.push('(');
        } else if (s[i] == ')') {
            while (ops.top() != '(') apply();
            ops.pop();                   // 弹出 '('
        } else {
            while (!ops.empty() && ops.top() != '('
                   && prio[ops.top()] >= prio[s[i]])
                apply();
            ops.push(s[i]);
        }
    }
    while (!ops.empty()) apply();
    return nums.top();
}

// ====== 中缀表达式 → 逆波兰（后缀） ======
vector<string> infix_to_rpn(const string& s) {
    vector<string> out;
    stack<char> ops;
    unordered_map<char, int> prio{{'+',1},{'-',1},{'*',2},{'/',2}};

    for (int i = 0; i < s.size(); ++i) {
        if (isspace(s[i])) continue;
        if (isdigit(s[i])) {
            string num;
            while (i < s.size() && isdigit(s[i])) num += s[i++];
            out.push_back(num);
            --i;
        } else if (s[i] == '(') {
            ops.push('(');
        } else if (s[i] == ')') {
            while (ops.top() != '(') {
                out.push_back(string(1, ops.top()));
                ops.pop();
            }
            ops.pop();
        } else {
            while (!ops.empty() && ops.top() != '('
                   && prio[ops.top()] >= prio[s[i]]) {
                out.push_back(string(1, ops.top()));
                ops.pop();
            }
            ops.push(s[i]);
        }
    }
    while (!ops.empty()) {
        out.push_back(string(1, ops.top()));
        ops.pop();
    }
    return out;
}

// ====== 逆波兰求值 ======
int eval_rpn(const vector<string>& tokens) {
    stack<int> st;
    for (auto& t : tokens) {
        if (isdigit(t[0]) || (t.size() > 1 && t[0] == '-'))
            st.push(stoi(t));
        else {
            int b = st.top(); st.pop();
            int a = st.top(); st.pop();
            if (t == "+") st.push(a + b);
            else if (t == "-") st.push(a - b);
            else if (t == "*") st.push(a * b);
            else st.push(a / b);
        }
    }
    return st.top();
}

2.17 各种括号匹配

// ====== 基础：多种括号匹配校验 ======
bool is_valid_brackets(const string& s) {
    unordered_map<char, char> pair{
        {')','('}, {']','['}, {'}','{'}
    };
    stack<char> st;
    for (char c : s) {
        if (pair.count(c)) {                     // 是右括号
            if (st.empty() || st.top() != pair[c])
                return false;
            st.pop();
        } else {                                 // 是左括号
            st.push(c);
        }
    }
    return st.empty();
}

// ====== 最长有效括号子串（仅小括号） ======
int longest_valid_parentheses(const string& s) {
    stack<int> st;
    st.push(-1);  // 哨兵下标
    int ans = 0;
    for (int i = 0; i < s.size(); ++i) {
        if (s[i] == '(') {
            st.push(i);
        } else {
            st.pop();
            if (st.empty())
                st.push(i);  // 新的「最后一个未匹配右括号」
            else
                ans = max(ans, i - st.top());
        }
    }
    return ans;
}

// ====== 最少插入次数使括号平衡 ======
int min_insertions_to_balance(const string& s) {
    int need = 0;   // 还需多少右括号
    int ans = 0;
    for (char c : s) {
        if (c == '(') {
            need += 2;                   // 每个 '(' 需要 2 个 ')'
            if (need % 2 == 1) {         // 奇数 → 补一个右括号
                ans++;
                need--;
            }
        } else {
            need--;
            if (need < 0) {             // 右括号多了
                ans++;                   // 补一个左括号
                need = 1;                // 还需一个右括号
            }
        }
    }
    return ans + need;
}

// ====== 生成所有合法括号组合 ======
vector<string> generate_parentheses(int n) {
    vector<string> ans;
    string path;

    function<void(int,int)> dfs = [&](int l, int r) {
        if (l == n && r == n) { ans.push_back(path); return; }
        if (l < n) { path.push_back('('); dfs(l + 1, r); path.pop_back(); }
        if (r < l) { path.push_back(')'); dfs(l, r + 1); path.pop_back(); }
    };

    dfs(0, 0);
    return ans;
}

// ====== 括号嵌套深度 ======
int max_depth(const string& s) {
    int d = 0, ans = 0;
    for (char c : s) {
        if (c == '(') ans = max(ans, ++d);
        else if (c == ')') d--;
    }
    return ans;
}

2.18 字符串压缩（游程编码 RLE）

// ====== 基础游程编码：aabbbcc → a2b3c2 ======
string rle_encode(const string& s) {
    string res;
    for (int i = 0; i < s.size(); ) {
        int j = i;
        while (j < s.size() && s[j] == s[i]) ++j;
        res += s[i];
        res += to_string(j - i);
        i = j;
    }
    return res;
}

// ====== 压缩后长度更短才返回，否则返回原串 ======
string compress_if_shorter(const string& s) {
    string res;
    for (int i = 0; i < s.size(); ) {
        int j = i;
        while (j < s.size() && s[j] == s[i]) ++j;
        res += s[i];
        res += to_string(j - i);
        i = j;
    }
    return res.size() < s.size() ? res : s;
}

// ====== 游程解码：a2b3c2 → aabbbcc ======
string rle_decode(const string& s) {
    string res;
    for (int i = 0; i < s.size(); ) {
        char ch = s[i++];
        int cnt = 0;
        while (i < s.size() && isdigit(s[i]))
            cnt = cnt * 10 + (s[i++] - '0');
        res.append(cnt, ch);
    }
    return res;
}

// ====== 统计连续重复段数 ======
int count_consecutive_groups(const string& s) {
    if (s.empty()) return 0;
    int groups = 1;
    for (int i = 1; i < s.size(); ++i)
        if (s[i] != s[i - 1]) groups++;
    return groups;
}
// 或利用 unique：
// int groups = unique(s.begin(), s.end()) - s.begin();

2.19 数组中差值为1的最大索引距离

// ====== |arr[i] - arr[j]| == 1，求 |i - j| 的最大值 ======
int max_dist_diff_one(const vector<int>& arr) {
    unordered_map<int, int> first;  // value → 首次出现的索引
    int ans = -1;                    // 不存在返回 -1
    for (int i = 0; i < arr.size(); ++i) {
        // 只记录首次出现（最小下标），用当前i作为最大下标求距离
        if (!first.count(arr[i]))
            first[arr[i]] = i;

        if (first.count(arr[i] + 1))
            ans = max(ans, i - first[arr[i] + 1]);
        if (first.count(arr[i] - 1))
            ans = max(ans, i - first[arr[i] - 1]);
    }
    return ans;
}

// ====== 双指针（定差滑动）：找和为target的两数最大索引距离 ======
int max_dist_two_sum(const vector<int>& arr, int target) {
    unordered_map<int, int> first;
    int ans = -1;
    for (int i = 0; i < arr.size(); ++i) {
        if (!first.count(arr[i]))
            first[arr[i]] = i;
        if (first.count(target - arr[i]))
            ans = max(ans, i - first[target - arr[i]]);
    }
    return ans;
}

// ====== 数组中有两个数差值为1的最大索引距离（遍历所有对） ======
// 更通用的写法：记录每个值的最左和最右位置
int max_dist_diff_one_v2(const vector<int>& arr) {
    unordered_map<int, int> left, right;
    for (int i = 0; i < arr.size(); ++i) {
        if (!left.count(arr[i])) left[arr[i]] = i;
        right[arr[i]] = i;
    }
    int ans = -1;
    for (auto& [val, l] : left) {
        if (right.count(val + 1))
            ans = max(ans, abs(l - right[val + 1]));
        // 也检查 right[val+1] 在 l 之前的情况：
        if (right.count(val + 1))
            ans = max(ans, abs(right[val] - left[val + 1]));
    }
    return ans;
}

2.20 IP地址表达式展开

// ====== 含 * 和 范围 的IP表达式展开为具体IP列表 ======
// 支持：192.168.*.*  192.168.1-3.*  10.0.0.1-5
vector<string> expand_ip(const string& pattern) {
    vector<string> parts = split(pattern, '.');

    vector<string> cur{""};
    for (auto& part : parts) {
        vector<string> next;
        // '*' → 0~255
        if (part == "*") {
            for (auto& pre : cur)
                for (int i = 0; i <= 255; ++i)
                    next.push_back(
                        pre + (pre.empty() ? "" : ".") + to_string(i));
        }
        // 'lo-hi' → 范围
        else if (part.find('-') != string::npos) {
            int dash = part.find('-');
            int lo = stoi(part.substr(0, dash));
            int hi = stoi(part.substr(dash + 1));
            for (auto& pre : cur)
                for (int i = lo; i <= hi; ++i)
                    next.push_back(
                        pre + (pre.empty() ? "" : ".") + to_string(i));
        }
        // 固定值
        else {
            for (auto& pre : cur)
                next.push_back(
                    pre + (pre.empty() ? "" : ".") + part);
        }
        cur.swap(next);
    }
    return cur;
}

// ====== IP地址与整数的相互转换 ======
uint32_t ip_to_int(const string& ip) {
    vector<string> parts = split(ip, '.');
    uint32_t res = 0;
    for (auto& p : parts)
        res = (res << 8) | stoi(p);
    return res;
}

string int_to_ip(uint32_t n) {
    return to_string((n >> 24) & 0xFF) + "." +
           to_string((n >> 16) & 0xFF) + "." +
           to_string((n >> 8)  & 0xFF) + "." +
           to_string(n & 0xFF);
}

// CIDR 展开：192.168.1.0/24 → 所有IP
vector<string> expand_cidr(const string& cidr) {
    int slash = cidr.find('/');
    string ip = cidr.substr(0, slash);
    int bits = stoi(cidr.substr(slash + 1));
    uint32_t base = ip_to_int(ip);
    uint32_t mask = (bits == 0) ? 0 : (~0u << (32 - bits));
    uint32_t start = base & mask;
    uint32_t count = 1u << (32 - bits);
    vector<string> ans;
    for (uint32_t i = 0; i < count; ++i)
        ans.push_back(int_to_ip(start + i));
    return ans;
}

C++ STL 速记 & 编程考题模板 — 持续更新中