经典基础

Created2026-03-17Updated2026-03-20

经典基础

一、核心易错点

1. 数组与越界

循环变量和分类下标分离：不要用外层 i 直接访问固定小数组。
容器访问前先判空或判长度：

1 2	if (!v.empty()) use(v[0]); if (v.size() > 1) use(v[1]);

2. 输入输出

cin >> n 后接 getline，必须先吃掉换行符：

1 2	cin >> n; cin.ignore();

大数据 I/O 优化：

1 2	ios::sync_with_stdio(0); cin.tie(0);

固定宽度补零：printf("%05d\n", num)。
输出优先 \n，避免频繁 endl。

3. 数据结构选择

键可能重复时，不用 map 存主体数据（会覆盖），用 struct + vector + sort。
不要求有序时优先 unordered_map/unordered_set。
小范围计数（如 26 字母）优先数组。

4. 边界条件

重点检查：0、空输入、区间端点、整除（余数为 0）。
转换类题目做“正向 + 逆向”自检。

5. 算法策略

能数组模拟就别硬改指针（如链表题可先按地址收集再处理）。
位数少可枚举，位数大用 DFS + 剪枝。

二、字符串输入与分词

1. 按空白读取到 EOF

string word;
while (cin >> word) {
    words.push_back(word);
}

2. 读取整行后按空格切词

string line;
getline(cin, line);
istringstream iss(line);
string word;
while (iss >> word) {
    words.push_back(word);
}

3. `cin >> n` 与 `getline` 混用模板

输入流缓冲区陷阱：

先 cin >> 读数字，后用 getline() 读字符串，cin 残留的回车符会直接被 getline 吞掉导致读到空串。必须在两者之间加 cin.ignore(); 清理。

int n;
cin >> n;
cin.ignore();

for (int i = 0; i < n; i++) {
    string line;
    if (!getline(cin, line)) break;
    istringstream iss(line);
    string word;
    while (iss >> word) {
        cout << word << ' ';
    }
    cout << '\n';
}

三、排序与比较器

1. `sort` + Lambda

1
2
3

sort(a.begin(), a.end(), [](const Node& x, const Node& y) {
    return x.key < y.key;
});

2. 结构体内重载 `<`

struct Student {
    int num, de, cai;
    bool operator<(const Student& b) const {
        if (de + cai == b.de + b.cai) {
            if (de == b.de) return num < b.num;
            return de > b.de;
        }
        return de + cai > b.de + b.cai;
    }
};

成员版 operator< 只写一个参数（右操作数）。
建议加 const，保证比较不改对象。

四、`map<int, bool>` 常用写法

1. 插入/修改

1
2
3

mp[10] = true;
mp.insert({30, true});
mp.emplace(50, false);

2. 遍历（推荐写法）

1
2
3

for (const auto& [key, val] : mp) {
    cout << key << ' ' << boolalpha << val << '\n';
}

五、区间与迭代器

1. `begin()` 与 `end()`

begin() 指向第一个元素。
end() 指向末尾后一个位置，不可解引用。

2. `reverse` 左闭右开

reverse(first, last) 作用区间是 $[first, last)$。
示例：

1 2	reverse(v.begin(), v.begin() + 3); // 前 3 个 reverse(v.begin() + 1, v.end()); // 从第 2 个到末尾

六、格式化输出

1	cout << fixed << setprecision(n) << x << '\n';

fixed：固定小数格式。
setprecision(n)：配合 fixed 时表示小数位数。

七、`sort()` 越界保护

1. 推荐：`min` 限制右边界

1 2	int end_idx = min(i + step, (int)a.size()); sort(a.begin() + i, a.begin() + end_idx);

2. 与 `end()` 比较

1 2	auto it_end = (a.begin() + i + step > a.end()) ? a.end() : a.begin() + i + step; sort(a.begin() + i, it_end);

八、工程化小习惯

比较前先判长度，不等直接返回。
vector 返回值可直接 return {a, b};。
累加场景优先检查是否误写 =（应为 +=）。

这是一个为你整理的 C++ STL 关联容器与哈希表核心用法总结表。在刷题和面试时，你可以直接在脑海中调出这张表格，快速决定使用哪种数据结构。

九、C++ STL 核心容器对比与速查表

操作大类	具体方法 / 代码片段	适用容器	时间复杂度 (哈希表 / 红黑树)	核心说明与避坑指南
插入 / 修改	`insert(val)`	全部适用	$O(1)$ / $O(\log n)$	插入元素。如果 Key 已经存在，则不会覆盖，插入失败。
	`emplace(args...)`	全部适用	$O(1)$ / $O(\log n)$	原地构造元素，省去拷贝/移动开销，性能通常优于 `insert`。
	`container[key] = val`	仅 `map`, `unordered_map`	$O(1)$ / $O(\log n)$	最常用。Key 存在则修改 Value；Key 不存在则创建并赋默认值。
查找 / 访问	`find(key)`	全部适用	$O(1)$ / $O(\log n)$	查找 Key。找到返回对应迭代器，没找到返回 `container.end()`。
	`count(key)`	全部适用	$O(1)$ / $O(\log n)$	返回 Key 的数量。在不允许重复的容器中，只能返回 1 或 0（常用于判断存在性）。
	`at(key)`	仅 `map`, `unordered_map`	$O(1)$ / $O(\log n)$	访问对应 Key 的 Value。如果 Key 不存在，会抛出越界异常，比 `[]` 更安全。
	`lower_bound(key)`	仅 `set`, `map` (有序)	$O(\log n)$	返回指向第一个大于或等于 key 的迭代器。哈希表不支持。
	`upper_bound(key)`	仅 `set`, `map` (有序)	$O(\log n)$	返回指向第一个严格大于 key 的迭代器。哈希表不支持。
删除	`erase(key)`	全部适用	$O(1)$ / $O(\log n)$	直接根据 Key 删除元素。返回被删除元素的个数（0 或 1）。
	`erase(iterator)`	全部适用	摊还 $O(1)$	删除迭代器指向的元素（常用于遍历时按条件删除）。
	`clear()`	全部适用	$O(n)$	清空容器中的所有元素。
容量 / 状态	`empty()`	全部适用	$O(1)$	检查容器是否为空。返回 `true` 或 `false`。
	`size()`	全部适用	$O(1)$	返回当前容器中元素的个数。

核心操作速记 (适用于以上所有 STL 容器)

查找是否存在： 首选：if (container.find(key) != container.end())
- 次选（仅限 set/map）：if (container.count(key) > 0)
插入元素：
- set / unordered_set: insert(key)
- map / unordered_map: container[key] = value (最方便) 或 insert({key, value})
删除元素：
- 按值删除：erase(key)
遍历容器：
- C++11 写法：for (auto it : container)
- C++17 结构化绑定 (针对 map)：for (auto [key, value] : my_map)

十、算法题型强化（从 N 数之和开始）

这一部分按“题型框架 -> 高频坑点 -> 可复用模板思维”整理，便于刷题时快速调用。

1. N 数之和家族（3Sum / 4Sum）

题型总框架

先排序，再做枚举 + 双指针。
去重必须发生在遍历过程中，而不是预处理阶段。
4Sum 及以上场景优先考虑剪枝，否则容易超时。

四个高频坑点

不能提前去重

不要先用 set 对原数组去重。
原数组中的重复值可能是合法答案的一部分，例如 [0, 0, 0]。

去重边界要写准

外层去重：if (k > 0 && nums[k] == nums[k - 1]) continue;
内层去重：if (i > k + 1 && nums[i] == nums[i - 1]) continue;
关键点：内层必须和当前层起点比较，不能写成 i > 0。

警惕整型溢出

多个 int 累加时可能溢出。
计算和时先提升类型：(long long)nums[k] + nums[i] + ...。

剪枝时分清 break 与 continue

最小和已经大于 target：后续只会更大，直接 break。
最大和仍小于 target：当前值太小，应该 continue。

2. 回溯算法（Backtracking）

统一骨架

终止条件 -> 做选择 -> 递归 -> 撤销选择。

两种写法对比

值传递写法（易写易懂）

形式：void backtrack(int n, string path)
递归：backtrack(n, path + ch)
特点：天然不需要手动撤销，代码直观。
代价：频繁拷贝字符串，适合 $n$ 很小（如 $n \le 10$）。

引用传递写法（面试主流）

形式：void backtrack(int n, string& path)
必须严格遵循：加入字符 -> 递归 -> pop_back()。
特点：性能更好，适合规模更大的搜索。

3. 哈希表优化思路

思路一：分组哈希（降维）

典型题：四数相加 II（四个独立数组）。
做法：前两数组求和计数，后两数组查补数 0 - c - d。
复杂度从 $O(n^4)$ 降为 $O(n^2)$。

思路二：能用定长数组就别用哈希

当键空间很小且固定（如 26 个小写字母）时，优先 int hash[26] = {0};。
数组访问常数更小、内存连续、实现也更稳定。

4. 一页速记（实战决策）

N 数之和：排序 + 双指针 + 分层去重 + 剪枝。
回溯：小规模可值传递，大规模用引用传递并手动撤销。
哈希优化：先看能否分组降维，再看能否降到定长数组。

十一、二叉树与 C++ 核心机制

1. 二叉树的遍历框架（基础必须如肌肉记忆般熟练）

1. DFS 迭代法（前、中、后序）

核心数据结构：栈 (stack)。注意栈是后进先出 (LIFO)。
易错点：写前序遍历时，压栈顺序必须是先压右孩子，再压左孩子，这样出栈时才是“先左后右”。

2. BFS 层序遍历

核心数据结构：队列 (queue)。
黄金模板：每次 while 循环开头，一定要先定格 int size = q.size();，然后用 for(int i=0; i<size; i++) 处理当前层，千万别和刚加进来的下一层节点混淆。

2. 树的属性与形态判定（思维陷阱高发区）

1. 最小深度 (Min Depth) 的“单身狗”陷阱

教训：遇到空节点不能直接算作叶子返回 0。如果一个节点只有左孩子没有右孩子，你必须顺着左边往下走，不能抄右边的空指针近道。

2. 对称二叉树 (Symmetric Tree)

教训：队列不支持下标访问（q[i] 报错）。正确的迭代法是成对入队，每次弹出两个节点对比，然后按 [左的左, 右的右] 和 [左的右, 右的左] 的顺序压入。

3. 平衡二叉树 (Balanced Tree) 的 $O(N)$ 优化

教训：自顶向下的递归会导致 $O(N^2)$ 的重复计算。
神仙操作：利用自底向上，在求深度的同时判断高度差。一旦发现不平衡，直接返回 -1 作为报错信号，一路剪枝到顶。

4. 左叶子之和 (Sum of Left Leaves)

教训：当前节点无法判断自己是不是“左叶子”。必须站在父节点去判断：root->left && !root->left->left && !root->left->right。

3. 高阶算法思想的应用

1. 完全二叉树的节点数（二分搜索思想）

核心公式：满二叉树节点数 = (1 << height) - 1 （注意防溢出，必要时用 1LL）。
神级优化：一直向左走测出左右子树的高度。如果 leftH == rightH，说明左子树是满的；如果 leftH > rightH，说明右子树是满的。每次直接抛弃一半，复杂度降为 $O(\log^2 N)$。

2. 回溯算法初步（Binary Tree Paths & Path Sum）

传值 vs 传引用：传 string path (传值) 会自动拷贝，不需要你手动清理；传 vector<int>& path (传引用) 必须成对出现 push_back 和 pop_back（做选择与撤销选择）。
做减法：路径总和问题，最好带着 targetSum - root->val 往下传，到叶子节点看是否刚好归零。

4. 二叉树的重构（纯靠索引操作）

1. 从中序与后序遍历构造二叉树

教训 1：建好的子树一定要挂载到父节点上（node->left = ...）。
教训 2：切分数组时，不要用绝对下标相加！唯一可靠的指标是算出一个 leftSize（左子树长度）。
切分公式：leftSize = index - inBegin。然后顺着后序数组的开头数 leftSize 个人，硬切开左右子树。

5. C++ 语言与语法避坑指南

1. 变量遮蔽 (Variable Shadowing)

惨痛教训：在 while 循环外定义了 TreeNode* cur，如果在循环里又写了 TreeNode* cur = q.front()，外部的 cur 就废了！更新外部变量时千万别加类型。

2. STL 队列操作

C++ 的 q.pop() 返回值是 void！必须先 q.front() 拿到值，再去 q.pop() 弹出。

3. 防呆设计 (Null Pointer Check)

任何递归或循环的第一步，永远是 if (!root) return ...;，直接拦截空指针，防止 Segfault。

十三、转义字符

反斜杠必须转义：

题目要求的错误提示包含 \，在 C++ 字符串中必须写成双反斜杠 **\\**，即 cout << "Are you kidding me? @\\/@";。

死循环与段错误：

找右括号 ] 时，循环条件必须加上 j < line.size() 保护。如果输入数据残缺（只有 [ 没有 ]），不加保护直接内存越界。

十四、整除

在中文语境和数学严谨表达中，“A 可以整除 B” 的含义是：B 是被除数，A 是除数。

A 整除 B（记作 $A | B$）：意味着 $B \div A$ 的结果是一个整数。
A 被 B 整除：意味着 $A \div B$ 的结果是一个整数。

所以，题目中“正整数 N 可以整除它的 4 个不同正因数之和”对应的数学表达式是：

$$\frac{\text{因数1} + \text{因数2} + \text{因数3} + \text{因数4}}{N} = \text{整数}$$

也就是说，这 4 个因数的“和”，必须是 $N$ 的倍数。

十五、螺旋矩阵

void solve() {
    int N;
    cin >> N;
    vector<int> vec(N);
    for (int i = 0; i < N; i++) {
        cin >> vec[i];
    }

    // TODO 1: 对 vec 进行降序排序
    sort(vec.begin(),vec.end(),[](int a,int b){
        return a > b;
    });
    int m = 0, n = 0;
    // TODO 2: 计算行数 m 和列数 n 
    // 提示: 令 n = sqrt(N)，循环递减 n 直到 N % n == 0，求出 m
    for(n = sqrt(N);n >= 1;n--){
        if(N % n == 0){
            m = N / n;
            break;
        }
    }
   // cout  << m << " " << n << endl;
    // 初始化二维矩阵 (注意一定要等 m 和 n 算出来后再初始化)
    vector<vector<int>> matrix(m, vector<int>(n));

    // 定义四个边界
    int top = 0, bottom = m - 1;
    int left = 0, right = n - 1;
    int index = 0; // 记录当前填到了 vec 中的第几个数

    // TODO 3: 螺旋填充核心逻辑
    while (index < N) {
        // 1. 从左到右填充上边界，填完后上边界下移
        // 提示: for (int j = left; j <= right && index < N; j++) ...
        //00 -> 0n
        for(int j = left; j <= right && index < N;j++){
            matrix[top][j] = vec[index++];
        }
        top ++;
        // 2. 从上到下填充右边界，填完后右边界左移
        //1n -> mn
        for(int j = top;j <= bottom && index < N;j++){
            matrix[j][right] = vec[index++];
        }
        right--;
        // 3. 从右到左填充下边界，填完后下边界上移
        //mn -> m0
        for(int j = right;j >= left && index < N;j--){
            matrix[bottom][j] = vec[index++];
        }
        bottom--;
        // 4. 从下到上填充左边界，填完后左边界右移
        //m0 -> 10
        for(int j = bottom;j >= top && index < N;j--){
            matrix[j][left] = vec[index++];
        }
        left++;
    }
    
}

经典基础

一、核心易错点

1. 数组与越界

2. 输入输出

3. 数据结构选择

4. 边界条件

5. 算法策略

二、字符串输入与分词

1. 按空白读取到 EOF

2. 读取整行后按空格切词

3. cin >> n 与 getline 混用模板

三、排序与比较器

1. sort + Lambda

2. 结构体内重载 <

四、map<int, bool> 常用写法

1. 插入/修改

2. 遍历（推荐写法）

五、区间与迭代器

1. begin() 与 end()

2. reverse 左闭右开

六、格式化输出

七、sort() 越界保护

1. 推荐：min 限制右边界

2. 与 end() 比较

八、工程化小习惯

九、C++ STL 核心容器对比与速查表

核心操作速记 (适用于以上所有 STL 容器)

十、算法题型强化（从 N 数之和开始）

1. N 数之和家族（3Sum / 4Sum）

题型总框架

四个高频坑点

2. 回溯算法（Backtracking）

统一骨架

两种写法对比

3. 哈希表优化思路

思路一：分组哈希（降维）

思路二：能用定长数组就别用哈希

4. 一页速记（实战决策）

十一、二叉树与 C++ 核心机制

1. 二叉树的遍历框架（基础必须如肌肉记忆般熟练）

1. DFS 迭代法（前、中、后序）

2. BFS 层序遍历

2. 树的属性与形态判定（思维陷阱高发区）

1. 最小深度 (Min Depth) 的“单身狗”陷阱

2. 对称二叉树 (Symmetric Tree)

3. 平衡二叉树 (Balanced Tree) 的 $O(N)$ 优化

4. 左叶子之和 (Sum of Left Leaves)

3. 高阶算法思想的应用

1. 完全二叉树的节点数（二分搜索思想）

2. 回溯算法初步（Binary Tree Paths & Path Sum）

4. 二叉树的重构（纯靠索引操作）

1. 从中序与后序遍历构造二叉树

5. C++ 语言与语法避坑指南

1. 变量遮蔽 (Variable Shadowing)

2. STL 队列操作

3. 防呆设计 (Null Pointer Check)

十三、转义字符

反斜杠必须转义：

死循环与段错误：

十四、整除

十五、螺旋矩阵

3. `cin >> n` 与 `getline` 混用模板

1. `sort` + Lambda

2. 结构体内重载 `<`

四、`map<int, bool>` 常用写法

1. `begin()` 与 `end()`

2. `reverse` 左闭右开

七、`sort()` 越界保护

1. 推荐：`min` 限制右边界

2. 与 `end()` 比较