刷题catcatcatcat
哈希
当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法。
例子：给出一个元素，判断这个元素是否出现过，如果出现过，返回这个元素的下标。那么判断元素是否出现，这个元素就要作为key，所以数组中的元素作为key，有key对应的就是value，value用来存下标。
取数的个位并去掉个位，循环继续的技巧
int getSum(int n) {
int sum = 0;
while (n) {
sum += (n % 10) * (n % 10); // 取个位，平方累加
n /= 10; // 去掉个位
}
return sum;
}
容器变量初始化
- 语法规则：变量默认初始化：只写类型 + 变量名，编译器会调用无参构造函数，生成一个空容器。即创建空容器时，{} / () 可省略，直接写变量名就行。
// 等价，都是创建空哈希表
unordered_map<int, int> map;
unordered_map<int, int> map{};
vector<int> v; // 空数组，最常用
vector<int> v{}; // 也是空数组
return {a, b};是 C++11 列表初始化 + 隐式构造，若函数返回值类型是 vector，{a, b} 会自动构造出一个临时 vector。返回 vector、数组、结构体等，只要编译器能推导出类型，都可以直接 {元素1, 元素2}。
// 简写（刷题首选）
return {iter->second, i};
// 完整等价写法
return vector<int>({iter->second, i});
vector a; // 空容器，容量0，没有可用下标
vector b(k); // 直接开辟k个int空间，下标 0~k-1 可用
- 什么时候必须写 vector result(k)（指定初始大小）
当你要直接用下标 result[i] = xxx 赋值时，必须提前开好空间。
vector result; // 长度0
result[2] = 10; // 非法！内存越界，运行报错
vector result(k);// 预先创建k个元素，下标0~k-1存在
result[i] = pri_que.top().first; // 合法
只用尾部追加 push_back()，不用下标读写，可以只写 vector result; 不填大小
vector result;
result.push_back(5);
result.push_back(3);
vector 会自动扩容，不会越界。
pair<int, int>(a,b) 与 {a,b} 区别
pair<int, int>(nums[i], i)：显式调用 pair 构造函数，老式 C++ 写法，兼容所有编译器。
这里 () 是函数调用语法，传参构造 pair 对象。
{nums[i], i}：C++11 列表初始化，编译器自动识别成 pair
有返回值的函数，所有代码分支必须有 return
创建空容器
unordered_map / vector 变量名; 即可，不用加 {}/()。
返回 vector
直接 return {val1, val2};，编译器自动构造临时容器。
map 插入键值对
老式：insert(pair<K,V>(k,v))
简写：insert({k, v})
最简：mp[k] = v（优先用这个）
pair() / pair{}
都是构造键值对，新旧语法，效果一致。
return {};
返回空容器，补全语法，防止编译报错。
模拟unordered_map 的 map[key]++；
map[key]++
key 不存在：插入 key，value 初始为 0 → 再 ++，最终 value=1
key 已存在：直接 value + 1
insert
key 不存在：插入键值对
key 已存在：直接忽略，不会修改原有 value
// 先查是否存在
auto it = map.find(key);
if (it != map.end()) {
// 存在 → 次数+1
it->second++;
} else {
// 不存在 → 插入，初始次数=1
map.insert(pair<int, int>(key, 1));
}
erase
erase 作用：删除容器元素，部分容器迭代器会失效
一、unordered_map /map（键值对哈希 / 红黑树）
三种重载：删除后仅被删元素的迭代器失效，其他迭代器安全。不能通过下标删除。
1.按 key 删除（最常用）
unordered_map<int, int> mp;
mp[1] = 10;
mp[2] = 20;
int cnt = mp.erase(1);
// 返回值：int，删除成功返回1，key不存在返回0
2.按迭代器删除
auto it = mp.find(2);
if (it != mp.end()) {
mp.erase(it);
// 无返回值；当前迭代器失效，其余迭代器/引用不受影响
}
3.区间删除
mp.erase(mp.begin(), mp.end()); // 清空容器
二、unordered_set /set（集合）
用法和 map 几乎一致，只是元素是单值而非键值对。erase(值)：返回 int，成功 1、失败 0。迭代器失效规则同 map。
unordered_set<int> st{1,2,3};
// 1. 按值删除
st.erase(2);
// 2. 按迭代器删除
auto it = st.find(1);
if(it != st.end()) st.erase(it);
// 3. 区间删除
st.erase(st.begin(), st.end());
三、vector 动态数组（重点，迭代器大坑）
三种用法
vector<int> v{1,2,3,4,5};
// 1. 按迭代器删除单个元素
auto it = v.begin() + 1;
v.erase(it); // 删除 2
// 2. 区间删除
v.erase(v.begin(), v.begin() + 2);//vector 的 erase(左迭代器, 右迭代器) 是区间删除，规则：左闭右开，v.begin() 指向第 1 个元素 1
//v.begin()+2 指向第 3 个元素 3
//执行后删除 1、2，最终 v = {3,4}。
// 3. 按值删除（无直接重载，要结合 find），vector 没有直接按值删除的重载，必须先用 find 找到位置，再删
auto pos = find(v.begin(), v.end(), 3);
//find(v.begin(), v.end(), 3)：在整个 vector 里查找值为 3 的元素，返回对应迭代器；没找到就返回 v.end()。
if(pos != v.end()) v.erase(pos);
致命注意：迭代器失效
vector 连续内存，删除元素后，后面所有元素前移：
被删位置、该位置之后所有迭代器全部失效
正确遍历删除写法
vector<int> v{1,2,2,3};
auto it = v.begin();
while (it != v.end()) {
if (*it == 2) {
// erase 返回：被删元素的下一个有效迭代器
it = v.erase(it);
} else {
it++;
}
}
四、string（字符串，本质字符容器，同 vector）
string 是字符版容器，erase 用法兼容 vector，还支持下标 + 长度写法：迭代器失效规则和 vector 一致。
string s = "abcde";
// 1. 迭代器删除
s.erase(s.begin() + 1); // 删除 b
// 2. 下标 + 个数 (pos, len)
s.erase(0, 2); // 从下标0开始，删2个字符
// 3. 区间删除
s.erase(s.begin(), s.end()); // 清空
五、list 双向链表：链表内存不连续，迭代器特性最好：仅被删迭代器失效，其余迭代器、指针、引用全都有效。
遍历删除写法简单，几乎无坑。
list<int> lst{1,2,3};
// 按迭代器删除
auto it = lst.begin();
lst.erase(it);
// 按值删除
lst.remove(2); // list 专属：直接按值删除（更方便）
4 vector
int record[26] = {0};//开辟大小 26 的整型数组，对应 a~z 26 个小写字母，初始全部置 0。
record[magazine[i]-‘a’] ++; //magazine[i] - ‘a’：把字符转为 0~25 的数组下标
例：‘a’-‘a’=0、‘b’-‘a’=1、‘z’-‘a’=25
每遍历一个字符，对应位置计数 +1。
三数之和模板
while(right>left){
// 1. 先算和、移动指针（核心查找）
if(和 > 0) right--;
else if(和 < 0) left++;
else{
// 2. 只有找到 和=0 时，才执行：存答案 + 去重 + 收缩指针
result.push_back(...);
// 去重
while(...) left++;
while(...) right--;
// 指针向内走
right--;
left++;
}
}
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> res;
sort(nums.begin(), nums.end());
int n = nums.size();
// 第一层循环：固定第一个数 a = nums[i]
for (int i = 0; i < n; ++i) {
// 剪枝：升序数组，a>0 后面全更大，和必大于0，直接结束
if (nums[i] > 0) break;
// a 去重：跳过重复的第一个数
if (i > 0 && nums[i] == nums[i - 1]) continue;//一般去重都是i>0，当前使用 nums[i]，我们判断前一位是不是一样的元素，在看 {-1, -1 ,2} 这组数据，当遍历到 第一个 -1 的时候，只要前一位没有-1，那么 {-1, -1 ,2} 这组数据一样可以收录到 结果集里。
int left = i + 1;
int right = n - 1;
while (left < right) {
// 强转 long long 防止 int 溢出
long long sum = (long long)nums[i] + nums[left] + nums[right];
if (sum > 0) {
right--; // 和偏大，右指针左移
} else if (sum < 0) {
left++; // 和偏小，左指针右移
} else {
// 找到合法三元组
res.push_back({nums[i], nums[left], nums[right]});
// b 去重：跳过左侧重复
while (left < right && nums[left] == nums[left + 1]) left++;
// c 去重：跳过右侧重复
while (left < right && nums[right] == nums[right - 1]) right--;
// 双指针向内收缩
left++;
right--;
}
}
}
return res;
}
};
四数相加模板
class Solution {
public:
int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
unordered_map<int, int> umap; //key:a+b的数值，value:a+b数值出现的次数
// 遍历大A和大B数组，统计两个数组元素之和，和出现的次数，放到map中
for (int a : A) {
for (int b : B) {
umap[a + b]++;
}
}
int count = 0; // 统计a+b+c+d = 0 出现的次数
// 再遍历大C和大D数组，找到如果 0-(c+d) 在map中出现过的话，就把map中key对应的value也就是出现次数统计出来。
for (int c : C) {
for (int d : D) {
if (umap.find(0 - (c + d)) != umap.end()) {
count += umap[0 - (c + d)];
}
}
}
return count;
}
};
四数之和
long long sum = (long long)nums[i] + nums[j] + nums[left] + nums[right];
先把 nums[i] 单独强制转为 long long
再依次和后面 int 类型的 nums[j]、nums[left]、nums[right] 相加
运算时，int 会自动提升为 long long，整个求和过程都在 64 位整数里计算，不会溢出。
// ❌ 把一整串加法整体转 long long，先算 int 加法，再转类型，已经溢出了
long long sum = (long long)(nums[i] + nums[j] + nums[left] + nums[right]);
数组先排序（去重、双指针前提）
两层循环固定前两个数 i、j（相当于把四数 → 简化成两数）
双指针 left、right 找后两个数
四层去重：
外层 i 去重/
/if (k > 0 && nums[k] == nums[k - 1]) {
continue;
}
中层 j 去重
内层 left 去重
内层 right 去重
1. 整体流程（N 数之和通用）
排序：sort(nums.begin(), nums.end())
多层循环：固定前 n-2 个数
三数：固定 1 层 + 双指针
四数：固定 2 层 + 双指针
逐层去重：每层循环都要跳过重复元素，防止结果重复
双指针：left 左、right 右，根据总和与目标值大小移动
防溢出：求和时第一个元素强转 long long
2. 去重标准写法
外层循环（i）：if (i > 0 && nums[i] == nums[i-1]) continue;
中层循环（j）：if (j > i+1 && nums[j] == nums[j-1]) continue;
双指针端：找到答案后，while 跳过相邻重复值
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> res;
sort(nums.begin(), nums.end());
int n = nums.size();
// 第一层循环：固定第一个数 a = nums[i]
for (int i = 0; i < n; ++i) {
// a 去重
if (i > 0 && nums[i] == nums[i - 1]) continue;
// 第二层循环：固定第二个数 b = nums[j]
for (int j = i + 1; j < n; ++j) {
// b 去重
if (j > i + 1 && nums[j] == nums[j - 1]) continue;
int left = j + 1;
int right = n - 1;
while (left < right) {
// 防溢出
long long sum = (long long)nums[i] + nums[j] + nums[left] + nums[right];
if (sum > target) {
right--;
} else if (sum < target) {
left++;
} else {
// 找到合法四元组
res.push_back({nums[i], nums[j], nums[left], nums[right]});
// c 去重
while (left < right && nums[left] == nums[left + 1]) left++;
// d 去重
while (left < right && nums[right] == nums[right - 1]) right--;
// 指针收缩
left++;
right--;
}
}
}
}
return res;
}
};
C++ std::reverse 用法总结
reverse 是 头文件中的反转函数，反转容器 / 区间内元素顺序，
一、函数原型
// 左闭右开区间 [first, last)
void reverse(iterator first, iterator last);//只接收迭代器,范围：包含 first，不包含 last
普通数组反转:数组名可当作首迭代器
#include <algorithm>
int arr[] = {10,20,30,40};
int n = sizeof(arr)/sizeof(arr[0]);
reverse(arr, arr + n);
// 结果：40 30 20 10
手动模拟 reverse 原理（底层逻辑）
// 模拟 reverse 功能,双指针头尾交换
void myReverse(vector<int>& v) {
int l = 0, r = v.size() - 1;
while (l < r) {
swap(v[l], v[r]);
l++;
r--;
}
}
// 反转字符串s中左闭右闭的区间[start, end]
void reverse(string& s, int start, int end) {
for (int i = start, j = end; i < j; i++, j--) {
swap(s[i], s[j]);
}
}
C++ swap 用法全总结
交换两个变量 / 容器的值，原地交换，无返回值。需要头文件：#include （C++11 后多数场景可省略，建议统一加上）
交换 vector / string（整容器交换）:直接交换整个容器内容，效率极高（只交换内部指针，不拷贝元素）
vector v1 = {1,2,3};
vector v2 = {4,5};
swap(v1, v2);
// v1 = {4,5} , v2 = {1,2,3}
string s1 = “abc”, s2 = “123”;
swap(s1, s2);
// s1 = “123”
手动实现 swap
// 手写交换两个 int
void mySwap(int &x, int &y)
{
int temp = x;
x = y;
y = temp;
}
C++ 常用容器互相转换
核心原理：利用容器构造函数 + 迭代器区间 [begin, end)，绝大多数顺序 / 关联容器都能互相转。
通用语法（所有容器通用）
任意容器 A → 容器 B：
B 新容器(A.begin(), A.end());
#include <vector>
#include <set>
#include <list>
#include <deque>
#include <algorithm>
using namespace std;
一、vector ↔ set（刷题最高频）
- vector 转 set
作用：自动去重 + 升序排序（set 特性：元素唯一、默认从小到大）
语法：set s(vec.begin(), vec.end());
vector<int> vec = {3, 1, 2, 2, 3, 1};
// vector → set：去重 + 排序
set<int> st(vec.begin(), vec.end());
// 遍历结果：1 2 3
for (int x : st) cout << x << " ";
- set 转 vector
作用：把有序、去重的集合转回动态数组，方便下标访问、双指针、排序题
语法：vector vec(st.begin(), st.end());
set<int> st = {1, 2, 3};
// set → vector
vector<int> vec(st.begin(), st.end());
// 遍历结果：1 2 3
for (int x : vec) cout << x << " ";
容器转换核心特性
- 转 set /multiset 一定会发生两件事
自动升序排序
set 自动去重；multiset 保留重复
刷题场景：数组去重、有序化，一行代码搞定。 - 转回 vector/list/deque
保留原容器的顺序、重复值，仅做元素拷贝。 - 不能互相转换的容器
map / unordered_map（键值对 key-value 结构）不能直接转 vector/set（单元素）
需要单独遍历取键 / 取值再存入。
map 转 vector（键值对场景）
map<int, int> mp;
mp[1] = 10;
mp[2] = 20;
// 把 map 所有键值对存入 vector
vector<pair<int, int>> vec(mp.begin(), mp.end());//vec 里存的就是：vec[0] = pair(1,10)，vec[1] = pair(2,20)
map<int, int> 中每一个元素都是 pair<int, int>：
第一个值 = 键 (key)，用 .first 访问
第二个值 = 值 (value)，用 .second 访问
C++ 代码字面量 / 初始化写法
// 初始化 map
map<int, int> mp = {{1, 10}, {2, 20}};
整体看成：
{ {1,10}, {2,20} }
外层 {} 代表整个 map，内层每一组 {键, 值} 是一个键值对。
判断一个字符为数字还是字母
一、标准库函数
isalpha©：是大写 / 小写字母 返回 非 0，否则返回 0
char c = 'A';
if (isalpha(c)) {
cout << "是字母" << endl;
}
判断是否是数字：isdigit©：是 0~9 返回 非 0，否则返回 0
char c = '5';
if (isdigit(c)) {
cout << "是数字" << endl;
}
isupper©：是否大写字母
islower©：是否小写字母
isalnum©：是否字母 或 数字（字母数字混合判断）
利用 ASCII 码范围判断
ASCII 范围：
大写字母：A ~ Z → 65 ~ 90
小写字母：a ~ z → 97 ~ 122
数字：0 ~ 9 → 48 ~ 57
判断字母：
bool isLetter(char c) {
// 大写 或 小写
return (c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z');
}
判断数字：
bool isNumber(char c) {
return c >= '0' && c <= '9';
}
参数类型隐患
cctype 函数要求传入 unsigned char，如果字符是负数（扩展 ASCII），会报错。
刷题仅处理英文字母 + 数字，日常使用基本没问题。
返回值不是严格 bool
isalpha/isdigit 成功时返回任意非 0 整数，不是固定 1，判断只用 if(函数名©)，不要写 == true。
空格、标点、特殊字符
以上函数都会判定为「非字母、非数字」。
C++ string 扩容、拷贝
一、字符串拷贝（复制内容）
- 直接赋值 =（最常用）
string a = "hello";
string b;
b = a; // 把 a 完整拷贝给 b
- 构造函数拷贝
string a = "hello";
string b(a); // 整体拷贝
string c = a; // 等价写法
- copy() 函数（拷贝到字符数组）把 string 内容复制到 char[]，不含末尾 \0
string s = "abc";
char buf[10];
// 参数：目标地址、拷贝长度、起始下标(默认0)
s.copy(buf, 3);
buf[3] = '\0'; // 手动补结束符，否则乱码
- 拷贝部分子串
方式 1：substr 截取再赋值
语法：substr(起始下标, 长度)，长度省略则截取到末尾
string s = "abcdef";
string res = s.substr(1, 3); // 从下标1开始，取3个字符 → "bcd"
string res2 = s.substr(2); // 从下标2到末尾 → "cdef"
方式 2：assign 赋值（支持整体 / 部分拷贝）
string a = "123456";
string b;
b.assign(a); // 整体拷贝
b.assign(a, 2, 3); // 从a下标2开始，拷贝3个字符
二、字符串扩容 & 追加内容,string 是动态字符数组，不用手动管理内存，追加字符 / 字符串会自动扩容。
- 末尾追加（最常用）
① += 运算符
string s = "hi";
s += " world"; // 追加字符串 → "hi world"
s += '!'; // 追加单个字符 → "hi world!"
② append() 函数
string s = "a";
s.append("bc"); // 追加字符串 → "abc"
s.append(2, 'x'); // 追加 2 个 'x' → "abcxx"
s.append("1234", 1, 2);// 截取"1234"下标1开始2个字符追加 → "abcxx23"
③ push_back() 只追加单个字符
string s = "ab";
s.push_back('c'); // → "abc"
- 手动预分配容量（主动扩容，优化效率）
string 有两个关键属性：
size() / length()：实际字符个数
capacity()：当前已分配内存容量（能存多少字符，不含结束符）
当 size == capacity，再追加内容会自动扩容。
如果提前知道大概长度，可用 reserve() 预分配，减少多次扩容开销。
1）reserve(n)：预分配容量（只改容量，不改变字符）:适合要大量追加字符的场景，避免反复自动扩容。
string s = "abc";
cout << s.size() << endl; // 3
cout << s.capacity() << endl;// 初始容量
s.reserve(20); // 提前扩容到可存20个字符
cout << s.capacity() << endl;// 容量变为20，内容不变
2）resize(n)：改变实际字符长度（扩容 + 截断都能做）
n > 原size：扩容，多出位置补空字符 \0
n < 原size：截断字符串，丢弃后面字符
string s = "abcd";
s.resize(6); // 扩容到6位 → "abcd\0\0"
s.resize(2); // 截断到2位 → "ab"
// 扩容并指定填充字符
s.resize(5, '#'); // 长度设为5，空位用 # 填充 → "ab###"
reserve 不会缩短容量，只能扩大；resize 可长可短。
substr(起始下标, 长度)，第二个参数是字符个数，不是结束下标。
所有拷贝 / 追加都是深拷贝，多个 string 之间内存相互独立。
输入输出
空白符，屏幕上看不到实际内容，只起分隔作用：
空格：键盘空格键
回车：键盘回车键（换行 \n）
制表符：键盘 Tab 键（\t）
cin >> s 「自动忽略空白符」分两步理解
第一步：读取前 —— 跳过所有连续空白
执行 cin >> s 时，先往后扫，遇到空格 / 回车 / Tab 直接跳过，直到找到可见字符才开始读。
第二步：读取中 —— 碰到空白就停止
从可见字符开始读，一旦再次遇到空格 / 回车 / Tab，立刻终止本次读取。
cin >> s 与 getline(cin, s)
cin >> 字符串/数字 特点
不区分空格、回车、Tab，统一当「分隔符」；
只能读取连续一段无空白的内容（单个单词 / 单个数字）。
对比 getline（不忽略回车）
getline(cin, s) 以回车作为结束标记，不会跳过回车，能读取整行（包含行内空格）。
如果前面用了 cin >>，后面紧跟 getline，会读到空行。
cin >> s1;
cin.ignore(); // 丢弃缓冲区里的回车
getline(cin, s2);
C++ 没有标准库 split 分割字符串函数
常用两种手写实现：按空格分割、按指定字符分割
把一个长字符串，按分隔符切成多个子串，存入 vector。
常见分隔符：空格、逗号、逗号 + 空格、特定字符。
模板 1：按空白符 (空格 / 回车 / Tab) 分割
利用 stringstream，自动按空白拆分，连续多个空格、Tab、换行，都会当成一个分隔符，首尾空格自动忽略，适配 getline 读整行后再分割
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
using namespace std;
// 按空白分割，返回分割后的字符串数组
vector<string> split(const string& str)
{
vector<string> res;
stringstream ss(str);
string word;
// 不断读取单词，自动跳过所有空格、Tab、换行
while (ss >> word)
{
res.push_back(word);
}
return res;
}
int main()
{
string s = "hello world c++ 123";
vector<string> vec = split(s);
for (auto& t : vec)
{
cout << t << endl;
}
return 0;
}
int main()
{
string line;
// 循环读多行
while (getline(cin, line))
{
vector<string> parts = split(line);
// 遍历分割结果
for (auto& p : parts)
{
cout << p << " | ";
}
cout << endl;
}
return 0;
}
模板 2：按指定单个字符分割（如 ,、-、.）
#include <iostream>
#include <string>
#include <vector>
using namespace std;
// delimiter：分隔符
vector<string> split(const string& str, char delimiter)
{
vector<string> res;
string temp;
for (char ch : str)
{
if (ch == delimiter)
{
// 遇到分隔符，把临时串存入结果
if (!temp.empty())
{
res.push_back(temp);
temp.clear();
}
}
else
{
temp += ch;
}
}
// 把最后一段加入
if (!temp.empty())
{
res.push_back(temp);
}
return res;
}
int main()
{
string s = "apple,banana,orange,grape";
vector<string> vec = split(s, ',');
for (auto& t : vec)
cout << t << " ";
return 0;
}
stringstream 、while(getline(cin, line))
stringstream 属于 头文件，字符串流，可以把字符串当作「内存中的数据流」读写，用法和 cin/cout 几乎一致。
string str = "hello 123";
stringstream ss(str);
//用字符串 str 初始化流对象 ss；等价于：把字符串内容放进流缓冲区，之后能用 >> 从里面读数据、<< 往里写数据。
//cin：从键盘读数据；stringstream：从字符串读数据
while(getline(cin, line))
功能：从标准输入（键盘）读取一整行字符，存入字符串 line；
规则：
读到回车就停止，回车不会存入 line；
行内空格全部保留；
读取成功返回 true，循环继续；读到文件结束 / 异常返回 false，循环退出。
ss >> num 可以直接 string 转 int
ss 是字符串流，>> 运算符会自动按类型解析内容：
流里是数字格式的字符，读取到 int 变量时，自动完成 字符串 → 整型 转换。
流同样支持反向：ss << 数字，把数字转成字符串；
如果字符串不是合法数字，ss >> num 会读取失败，返回 false。
#include <sstream>
#include <string>
#include <iostream>
using namespace std;
int main()
{
string s = "100 200 300";
stringstream ss(s);
int num;
// 自动拆分、自动转 int
while (ss >> num)
{
cout << num << endl;
}
return 0;
}
C++ 流分三类：标准控制台流、文件流、字符串流
前缀标识
i = Input 输入（读数据：外部 → 程序变量）
o = Output 输出（写数据：程序变量 → 外部）
后缀标识（区分数据载体）
无特殊后缀：控制台（键盘 / 屏幕）
file：文件
string：字符串
运算符固定搭配
输入流 统一用 >>
输出流 统一用 <<
第一组：控制台流（终端交互）
头文件：#include
用于键盘输入、屏幕打印，
类型名 含义 读写属性 配套全局对象
istream 标准输入流 只读 cin（键盘读）
ostream 标准输出流 只写 cout（屏幕打印）、cerr/clog（错误输出）
iostream 控制台双向流 可读可写 一般不手动创建对象，继承自上面两个
第二组：文件流（读写本地 txt / 二进制文件）
头文件：#include
后缀 file 代表操作本地文件。
类型名 全称拆解 读写属性 用途
ifstream in + file + stream 只读 从文件读取数据
ofstream out + file + stream 只写 向文件写入数据
fstream file + stream 可读可写 文件同时读写
ifstream fin(“a.txt”); // 打开文件 读
ofstream fout(“b.txt”); // 打开文件 写
第三组：字符串流（内存中字符串当作流）
头文件：#include
后缀 string 代表操作内存字符串，用于分割字符串、字符串 / 数字互转。
类型名 全称拆解 读写属性 用途
istringstream in + string + stream 只读 从字符串中读数据
ostringstream out + string + stream 只写 向字符串中写数据
stringstream string + stream 可读可写 全能型，刷题首选
移除空格
void removeExtraSpaces(string& s) {//去除所有空格并在相邻单词之间添加空格, 快慢指针。
int slow = 0; //整体思想参考https://programmercarl.com/0027.移除元素.html
for (int i = 0; i < s.size(); ++i) { //
if (s[i] != ' ') { //遇到非空格就处理，即删除所有空格。
if (slow != 0) s[slow++] = ' '; //手动控制空格，给单词之间添加空格。slow != 0说明不是第一个单词，需要在单词前添加空格。
while (i < s.size() && s[i] != ' ') { //补上该单词，遇到空格说明单词结束。
s[slow++] = s[i++];
}
}
}
s.resize(slow); //slow的大小即为去除多余空格后的大小。
}
//快指针遍历，空格直接跳过；读到单词：，不是第一个单词 → 先补一个分隔空格；，再把整个单词复制到慢指针位置；遍历结束，用 resize 截断字符串。
//外层 for：只管发现新单词（跳过所有空格），内层 while：一次性搬运整个单词，直到再次碰到空格
在这类原地覆盖的双指针题里，通用规则：slow 永远指向 下一个待写入的位置
//待写入位置下标 = 字符串有效长度
C++ 实现 strStr()（找出字符串中第一个匹配项的下标）
给你两个字符串 haystack（原串）和 needle（模式串），在 haystack 中找出 needle 字符串出现的第一个位置，从 0 开始；如果不存在返回 -1。约定：needle 为空串时返回 0。
一、思路（暴力双指针，刷题最常用）
遍历原串 haystack，逐个位置当作匹配起点
从起点开始，逐字符对比 haystack 和 needle
全部字符匹配成功 → 返回当前起点下标
遍历完都不匹配 → 返回 -1
#include <iostream>
#include <string>
using namespace std;
int strStr(string haystack, string needle) {
// 模式串为空，直接返回 0
if (needle.empty()) {
return 0;
}
int n = haystack.size();
int m = needle.size();
// 原串遍历到 n-m 即可，后面长度不够无需判断
for (int i = 0; i <= n - m; ++i) {
int j = 0;
// 从 i 开始逐字符匹配
while (j < m && haystack[i + j] == needle[j]) {
j++;
}
// 全部匹配完成
if (j == m) {
return i;
}
}
// 没有匹配项
return -1;
}
int main() {
string a, b;
cin >> a >> b;
cout << strStr(a, b) << endl;
return 0;
}
循环上限 i <= n - m
原串剩余长度必须 ≥ 模式串长度，否则不可能匹配，减少无效循环。
例：原串长 5，模式串长 3 → i 最大取 2。
匹配逻辑
j 是模式串下标，逐个比对字符
j == m 代表模式串所有字符匹配完毕，找到答案
边界处理
needle 空串 → 返回 0（题目规定）
haystack 比 needle 短 → 直接走循环外，返回 -1
KMP
next数组就是一个前缀表（prefix table）
前缀表是用来回退的，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配。
要在文本串：aabaabaafa 中查找是否出现过一个模式串：aabaaf。
前缀表：记录下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀。
缀是指不包含最后一个字符的所有以第一个字符开头的连续子串。
后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。
前缀表要求的就是相同前后缀的长度。
字符串a的最长相等前后缀为0。 字符串aa的最长相等前后缀为1。 字符串aaa的最长相等前后缀为2。
前缀表统一减一 C++代码实现
class Solution {
public:
void getNext(int* next, const string& s) {
int j = -1;
next[0] = j;
for(int i = 1; i < s.size(); i++) { // 注意i从1开始
while (j >= 0 && s[i] != s[j + 1]) { // 前后缀不相同了
j = next[j]; // 向前回退
}
if (s[i] == s[j + 1]) { // 找到相同的前后缀
j++;
}
next[i] = j; // 将j（前缀的长度）赋给next[i]
}
}
int strStr(string haystack, string needle) {
if (needle.size() == 0) {
return 0;
}
vector<int> next(needle.size());
getNext(&next[0], needle);
int j = -1; // // 因为next数组里记录的起始位置为-1
for (int i = 0; i < haystack.size(); i++) { // 注意i就从0开始
while(j >= 0 && haystack[i] != needle[j + 1]) { // 不匹配
j = next[j]; // j 寻找之前匹配的位置
}
if (haystack[i] == needle[j + 1]) { // 匹配，j和i同时向后移动
j++; // i的增加在for循环里
}
if (j == (needle.size() - 1) ) { // 文本串s里出现了模式串t
return (i - needle.size() + 1);
}
}
return -1;
}
};
前缀表（不减一）C++实现
class Solution {
public:
void getNext(int* next, const string& s) {
int j = 0;
next[0] = 0;
for(int i = 1; i < s.size(); i++) {
while (j > 0 && s[i] != s[j]) {
j = next[j - 1];
}
if (s[i] == s[j]) {
j++;
}
next[i] = j;
}
}
int strStr(string haystack, string needle) {
if (needle.size() == 0) {
return 0;
}
vector<int> next(needle.size());
getNext(&next[0], needle);
int j = 0;
for (int i = 0; i < haystack.size(); i++) {
while(j > 0 && haystack[i] != needle[j]) {
j = next[j - 1];
}
if (haystack[i] == needle[j]) {
j++;
}
if (j == needle.size() ) {
return (i - needle.size() + 1);
}
}
return -1;
}
};
tips：C++ 标准里，普通数组的长度不能用变量，C++ 原生数组 T 数组名[长度] 要求：长度必须是编译期常量
使用 vector
int m = needle.size();
vector<int> next(m); // 动态数组，长度可以是变量
如果执意用原生数组（仅限提前定常量）
只有长度是字面量 /const 常量才合法：
vector 不能转 int*
vector 底层是连续数组，用 .data() / &next[0] 拿到首地址转指针：
// 合法：编译期常量
const int LEN = 1000;
int next[LEN];
find/erase/contains 时间复杂度
std::string（字符串）
- find () 查找子串 / 字符
查找单个字符：O(n)
查找子串：最坏 (O(n*m)（m 为子串长度，暴力匹配）
说明：顺序遍历，逐个比对，无哈希 / 红黑树优化 - erase () 删除分三种用法：
erase(pos, len) / erase(迭代器) 删除单个位置
后面元素全部向前挪动，(O(n
erase(begin, end) 删除区间
区间后元素前移，O(n)
规律：string 是连续数组，只要删中间 / 开头，必挪动元素，复杂度 O(n) - 无原生 containsC++20 才给 string 加 contains，等价于 find != npos，复杂度同 find：O(n)
二、std::vector 动态数组底层：连续线性内存 - find()std::find(迭代器范围, 目标值)
顺序遍历：O(n) - erase()
erase(迭代器) 删除单个元素
后方元素整体前移：O(n)
erase(首迭代器, 尾迭代器) 删除区间
剩余元素前移：O(n) - containsC++20 新增 vector::contains，底层还是顺序查找：O(n)
三、unordered_set /unordered_map（哈希表）底层：哈希散列表，平均效率极高平均情况
1.find() O(1)常数级 - erase()
erase(迭代器) / erase(键值)：O(1)
erase(区间)：O(k)，k 为被删除元素个数 - contains()（C++20）判断键是否存在：O(1)最坏情况（哈希大量冲突）全部退化为链表遍历：O(n)
刷题一般只记平均 O(1)
四、set /map（有序集合 / 映射）底层：平衡红黑树，有序、自动排序
1.find()树的高度 ：O(log n) - erase()
erase(迭代器) / erase(键)：O(log n)（树节点删除 + 重平衡）
erase(区间)：O(log n + k)，k 是删除元素个数 - contains()（C++20）存在性判断：{O(log n)
if (t.find(s) != std::string::npos)：判断字符串 t 中是否包含子串 s
t.find(s)
调用 string 成员查找函数：在字符串 t 里查找子串 s
返回值：匹配成功 返回首个匹配位置下标（size_t 无符号整数）
匹配失败：返回特殊值 std::string::npos
std::string::npos
是 string 类定义的静态常量
本质：size_t 类型的最大值（一个超大无符号数）
语义：表示 “未找到”
查找单个字符用法一样 char ch = ‘o’; if (t.find(ch) != string::npos)
很多数组填充类的问题，其做法都是先预先给数组扩容带填充后的大小，然后在从后向前进行操作。
反转链表
双指针：
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* temp; // 保存cur的下一个节点
ListNode* cur = head;
ListNode* pre = NULL;
while(cur) {
temp = cur->next; // 保存一下 cur的下一个节点，因为接下来要改变cur->next
cur->next = pre; // 翻转操作
// 更新pre 和 cur指针
pre = cur;
cur = temp;
}
return pre;
}
};
递归：
class Solution {
public:
ListNode* reverse(ListNode* pre,ListNode* cur){
if(cur == NULL) return pre;
ListNode* temp = cur->next;
cur->next = pre;
// 可以和双指针法的代码进行对比，如下递归的写法，其实就是做了这两步
// pre = cur;
// cur = temp;
return reverse(cur,temp);
}
ListNode* reverseList(ListNode* head) {
// 和双指针法初始化是一样的逻辑
// ListNode* cur = head;
// ListNode* pre = NULL;
return reverse(NULL, head);
}
};
函数定义：ListNode* reverse(ListNode* pre, ListNode* cur)
逻辑：
cur == nullptr：所有节点处理完毕，pre 是新链表头，直接返回
保存 temp = cur->next（先存下一个要处理的节点，防止断链）
cur->next = pre：当前节点反向指向前驱
递归调用：reverse(cur, temp)
新 pre = 旧 cur
新 cur = 旧 temp
完全对应迭代里 pre=cur; cur=temp;
递归方法2：
class Solution {
public:
ListNode* reverseList(ListNode* head) {
// 边缘条件判断
if(head == NULL) return NULL;
if (head->next == NULL) return head;
// 递归调用，翻转第二个节点开始往后的链表
ListNode *last = reverseList(head->next);
// 翻转头节点与第二个节点的指向
head->next->next = head;
// 此时的 head 节点为尾节点，next 需要指向 NULL
head->next = NULL;
return last;
}
};
last 永远是最深层递归返回的原链表尾节点（反转后的新头），每层直接向上传递，最终函数返回反转链表头部。
last 不能丢，它是反转后的头节点，不能 return head；
必须写 head->next = nullptr，否则链表会形成环；
例：如果省略这句，1 和 2 会互相指向，死循环；
终止条件 head->next == nullptr 是递归出口，拿到反转后的起点。
双指针的经典应用，如果要删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾。删掉slow所指向的节点就可以了。
// 如果 B 的长度 > A 的长度
if (lenB > lenA) {
swap (lenA, lenB); // 交换两个长度变量
swap (curA, curB); // 交换两个链表头指针
}
代码典型场景：两个链表找相交节点 / 两数相加链表
作用：保证 curA 指向更长链表，curB 指向更短链表
方便后续对齐尾部，同步向后走。
遇到fast->next->next;，要先判断fast != NULL && fast->next != NULL
while(fast != NULL && fast->next != NULL)
fast = fast->next->next;
栈
栈提供push 和 pop 等等接口，所有元素必须符合先进后出规则，所以栈不提供走访功能，也不提供迭代器(iterator)。 不像是set 或者map 提供迭代器iterator来遍历所有元素。
栈是以底层容器完成其所有的工作，对外提供统一的接口，底层容器是可插拔的（也就是说我们可以控制使用哪种容器来实现栈的功能）。
所以STL中栈往往不被归类为容器，而被归类为container adapter（容器适配器）。
可以指定vector为栈的底层实现，初始化语句如下：
std::stack<int, std::vector > third; // 使用vector为底层容器的栈
也可以指定list 为起底层实现，初始化queue的语句如下：
std::queue<int, std::list> third; // 定义以list为底层容器的队列
STL 队列也不被归类为容器，而被归类为container adapter（ 容器适配器）。
vector / list / deque 是底层容器（基础容器），自带完整存储、增删、遍历逻辑；
stack / queue / priority_queue 是容器适配器，自身不存数据，只是套一层壳，借用别的容器实现功能。
C++ queue 常用函数
头文件：#include
底层默认容器：deque，属于容器适配器，先进先出 FIFO。
一、插入元素
push(x)
队尾插入元素
q.push(10);
emplace(x)
原地构造，效率比 push 高
q.emplace(20);
二、弹出元素
pop()
删除队首元素，无返回值
q.pop();
三、访问首尾元素
front()
返回队头第一个元素的引用，可读可改
int a = q.front();
q.front() = 100;
back()
返回队尾最后一个元素的引用
int b = q.back();
原地反转字符串
class Solution {
public:
void reverseString(vector<char>& s) {
int l = 0, r = s.size() - 1;
while(l < r) {
swap(s[l], s[r]);
l++;
r--;
}
}
};
二、string 字符串反转（普通 string）
方法 1：库函数 reverse（最简单）
cpp
运行
#include <algorithm>
string str = "abc123";
reverse(str.begin(), str.end());
cout << str; // "321cba"
string 和 stack 对应关系
string 是连续字符数组
头部（头）：下标 0，第一个字符 s[0]
尾部（尾）：最后一个字符，s.back() / s[s.size()-1]
和 stack 一一对应
把 string 当作栈使用时：
string 的尾部 = 栈顶 top ()
result.back() 等价于 st.top()
result.push_back(x) 等价于 st.push(x) 往栈顶加元素
result.pop_back() 等价于 st.pop() 删掉栈顶
string 的头部 = 栈底（永远不动，不操作）
栈只能操作栈顶，所以我们只用 string 的尾部，完全不用管头部。
C++ string 与 int 互相转换
一、int → string（数字转字符串）支持：int、long、float、double。
- to_string () 最简单
#include <string>
int a = 123;
string s = to_string(a);
// s = "123"
int b = -456;
string s2 = to_string(b);
// s2 = "-456"
二、string → int（字符串转数字）
- stoi () 转 int
string s = "789";
int num = stoi(s);
// num = 789
string s2 = "-100";
int num2 = stoi(s2);
// num2 = -100
stoi：string → int
stol：string → long
stoll：string → long long
stof：string → float
stod：string → double
三、旧方法（stringstream，兼容老标准）
需要头文件 #include
int 转 string
int x = 666;
stringstream ss;
ss << x;
string str = ss.str();
string 转 int
string str = "888";
stringstream ss(str);
int x;
ss >> x;
迭代器
rend() 和 rbegin() 是一对反向迭代器，所有有序容器（set/multiset/vector/string/deque）都配套存在。
- 基础对应关系（默认从小到大升序容器）
begin()：正向第一个（最小值）
end()：正向末尾后一位（无元素）
反向迭代器：
rbegin() = 反向起点，等价于 end()-1，指向最大值
rend() = 反向终点，等价于 begin()-1，指向最小值前一位（无效位置） - 遍历示例 multiset
multiset<int> s = {1,3,5,7};
// 反向从大到小遍历
for(auto it = s.rbegin(); it != s.rend(); ++it)
{
cout << *it; // 7 5 3 1
}
- 关键特点
反向迭代器用 ++ 向后走（数值变小），不能用 --；
判断循环结束条件固定：it != rend()；
rbegin() / rend() 不支持 -> 以外的特殊操作，和解引用 *；
降序容器 multiset<int, greater> 里：
rbegin() 指向最小元素，rend() 在最大元素外侧。
窗口 multiset：{1,3,3,-1}，现在要删掉左边滑出去的一个 3
- window.erase (迭代器) 正确写法
auto it = window.find(3);
window.erase(it);
find 返回第一个 3的迭代器，erase 只删除这一个元素。
集合变为：{1,3,-1}，窗口数量维持 k 个，逻辑正常。 - window.erase (数值) 错误写法
window.erase(3);
erase 传数字时，multiset 会删除容器中所有值等于 3 的元素。
集合直接变成：{1,-1}，少了一个本该留在窗口的 3，窗口元素丢失，结果全错。
滑动窗口求最大值
使用multiset作为单调队列
多重集合(multiset) 用以有序地存储元素的容器。允许存在相等的元素。
在遍历原数组的时候，只需要把窗口的头元素加入到multiset中，然后把窗口的尾元素删除即可。因为multiset是有序的，并且提供了*rbegin()，可以直接获取窗口最大值。
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
multiset<int> st;
vector<int> ans;
for (int i = 0; i < nums.size(); i++) {
if (i >= k) st.erase(st.find(nums[i - k]));
st.insert(nums[i]);
if (i >= k - 1) ans.push_back(*st.rbegin());
}
return ans;
}
};
单调队列
class MyQueue { //单调队列（从大到小）
public:
deque<int> que; // 使用deque来实现单调队列
// 每次弹出的时候，比较当前要弹出的数值是否等于队列出口元素的数值，如果相等则弹出。
// 同时pop之前判断队列当前是否为空。
void pop(int value) {
if (!que.empty() && value == que.front()) {
que.pop_front();
}
}
// 如果push的数值大于入口元素的数值，那么就将队列后端的数值弹出，直到push的数值小于等于队列入口元素的数值为止。
// 这样就保持了队列里的数值是单调从大到小的了。
void push(int value) {
while (!que.empty() && value > que.back()) {
que.pop_back();
}
que.push_back(value);
}
// 查询当前队列里的最大值 直接返回队列前端也就是front就可以了。
int front() {
return que.front();
}
};
优先级队列
缺省情况下priority_queue利用max-heap（大顶堆）完成对元素的排序，这个大顶堆是以vector为表现形式的complete binary tree（完全二叉树）。
priority_queue（优先队列 / 堆）底层默认是大顶堆，它需要一套规则来判断两个元素谁更大、谁放堆顶，这套规则就是比较器。
堆的底层逻辑：
比较器函数 operator()(a,b) 返回 true → 在堆中 a 的优先级低于 b，b 更靠近堆顶
1）默认大顶堆（不用自己写比较器）
priority_queue q;
默认比较规则：a < b
大的数留在堆顶。
2）自定义小顶堆，必须手写比较器类
class mycomparison {
public:
bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
return lhs.second > rhs.second;
}
};
operator() 重载括号，让这个类像一个函数一样能用；operator() 是判断大小，返回布尔值，必须加 bool。
参数 lhs = 左边元素，rhs = 右边元素；
return lhs.second > rhs.second：
如果左边的频次 ＞ 右边的频次 → 返回 true，代表左边优先级更低，堆顶留频次更小的值，实现小顶堆。
priority_queue 完整模板参数
template<
class T,
class Container = vector<T>,
class Compare = less<typename Container::value_type>
> class priority_queue;
一共3 个模板参数，后两个有默认值，可省略。
参数 1：T —— 堆里存储的元素类型
示例：
priority_queue：存 int
priority_queue<pair<int,int>>：存键值对 pair
参数 2：Container —— 底层存储容器（默认 vector）
可选，默认用 vector 实现堆结构。
要求容器支持 back()、push_back()、pop_back()，只能是 vector /deque，不能用 list、map。
参数 3：Compare —— 比较器（默认 less，大顶堆）
可选，决定堆是大顶还是小顶，控制优先级规则。
核心规则
比较器 cmp(a,b) 返回 true：代表 a 的优先级比 b 低，b 放堆顶。
默认 less → a < b
大数优先级更高 → 大顶堆
greater → a > b
小数优先级更高 → 小顶堆
priority_queue 优先级规则
比较器 cmp(a,b) 返回 true：
a 优先级 < b，b 更靠近堆顶。
- 默认大顶堆 less
priority_queue q;
// 等价：priority_queue<int, vector, less> q;
less 内部逻辑：return a < b;
举例：a=3，b=5
3 < 5 → true
→ a (3) 优先级 < b (5)
→ 5 放堆顶，大数在上，大顶堆。 - 内置小顶堆 greater
priority_queue<int, vector, greater> q;
greater 逻辑：return a > b;
举例：a=5，b=3
5 > 3 → true
→ a (5) 优先级 < b (3)
→ 3 放堆顶，小数在上，小顶堆。
两种返回 true 都代表 a 优先级低，区别在哪？
区别是：什么情况下判定 a 更低
return a < b
只有【a 更小】时，a 才变垃圾、b 上位；结果：大数字掌权
return a > b
只有【a 更大】时，a 才变垃圾、b 上位；结果：小数字掌权
两组数字：3 和 7
情况 1：return a < b
a=3,b=7 → 3<7 为 true → 3 垃圾，7 堆顶（大顶堆）
a=7,b=3 →7<3 为 false → 不会交换，7 保持堆顶
情况 2：return a > b
a=7,b=3 →7>3 为 true →7 垃圾，3 堆顶（小顶堆）
a=3,b=7 →3>7 为 false →不会交换，3 保持堆顶
一句总结区分符号作用
<：小数自动降级，大的优先（大顶堆）
：大数自动降级，小的优先（小顶堆）
一、sort 自定义比较函数规则（快排 / 普通排序）
sort 的 cmp 返回 true 代表：left 应该排在 right 前面。
- return a < b
如果 a 小于 b，返回 true → a 放左边，b 放右边
结果：从小到大升序
例：a=2，b=5，2<5=true → 2 在前，5 在后 → [2,5] - return a > b
如果 a 大于 b，返回 true → a 放左边，b 放右边
结果：从大到小降序
例：a=5，b=2，5>2=true →5 在前，2 在后 → [5,2]
场景 return a < b r eturn a > b
sort 排序 升序（小在前） 降序（大在前）
priority_queue 大顶堆（大数在上） 小顶堆（小数在上）
大根堆小根堆的比较器
注意operator要是public，否则为私有成员函数，其他类无法访问，
// 小顶堆
class mycomparison {
public:
bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
return lhs.second > rhs.second;
}
};
// 定义一个小顶堆，大小为k
priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;
// 用固定大小为k的小顶堆，扫面所有频率的数值
for (unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) {
pri_que.push(*it);
if (pri_que.size() > k) { // 如果堆的大小大于了K，则队列弹出，保证堆的大小一直为k
pri_que.pop();
}
}
前K个高频元素
class Solution {
public:
// 小顶堆
class mycomparison {
public:
bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
return lhs.second > rhs.second;
}
};
vector<int> topKFrequent(vector<int>& nums, int k) {
// 要统计元素出现频率
unordered_map<int, int> map; // map<nums[i],对应出现的次数>
for (int i = 0; i < nums.size(); i++) {
map[nums[i]]++;
}
// 对频率排序
// 定义一个小顶堆，大小为k
priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;
// 用固定大小为k的小顶堆，扫面所有频率的数值
for (unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) {
pri_que.push(*it);
if (pri_que.size() > k) { // 如果堆的大小大于了K，则队列弹出，保证堆的大小一直为k
pri_que.pop();
}
}
// 找出前K个高频元素，因为小顶堆先弹出的是最小的，所以倒序来输出到数组
vector<int> result(k);
for (int i = k - 1; i >= 0; i--) {
result[i] = pri_que.top().first;
pri_que.pop();
}
return result;
}
};
C/C++的定义链表节点方式
// 单链表
struct ListNode {
int val; // 节点上存储的元素
ListNode *next; // 指向下一个节点的指针
ListNode(int x) : val(x), next(NULL) {} // 节点的构造函数
};
通过自己定义构造函数初始化节点：
ListNode* head = new ListNode(5);
使用默认构造函数初始化节点：
ListNode* head = new ListNode();
head->val = 5;
所以如果不定义构造函数使用默认构造函数的话，在初始化的时候就不能直接给变量赋值
链式存储的二叉树节点的定义方式
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
递归三要素
1确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
2确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
3确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。
二叉树的统一迭代法
方法一：就是要处理的节点放入栈之后，紧接着放入一个空指针作为标记。 这种方法可以叫做空指针标记法
中序遍历
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> st;
if (root != NULL) st.push(root);
while (!st.empty()) {
TreeNode* node = st.top();
if (node != NULL) {
st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
if (node->right) st.push(node->right); // 添加右节点（空节点不入栈）
st.push(node); // 添加中节点
st.push(NULL); // 中节点访问过，但是还没有处理，加入空节点做为标记。
if (node->left) st.push(node->left); // 添加左节点（空节点不入栈）
} else { // 只有遇到空节点的时候，才将下一个节点放进结果集
st.pop(); // 将空节点弹出
node = st.top(); // 重新取出栈中元素
st.pop();
result.push_back(node->val); // 加入到结果集
}
}
return result;
}
};
要不要存 NULL，取决于你什么时候处理节点
- 带 NULL 标记栈（必须 push (nullptr)）
适用场景：想用一套栈模板统一实现前 / 中 / 后序遍历
原理
栈里两种东西：普通节点、NULL 标记
弹出非 NULL 节点：代表还没处理，重新按「右、左、中、NULL」顺序压栈
弹出 NULL：代表它前面那个节点现在可以处理（打印、swap、算深度等）
作用：分割 “访问节点” 和 “处理节点” 两个时机
递归天然分开两步：
往下走（访问节点）
回溯回来（处理节点）
迭代没有回溯，只能靠 NULL 标记告诉程序：现在该处理了。
举例：求深度、中序遍历、后序遍历都要用这套模板，必须压 NULL。
if(node != nullptr){
st.pop();
st.push(node);
st.push(nullptr); // 标记后面要处理它
st.push(右);
st.push(左);
}else{
st.pop();
node = st.top(); st.pop();
// 真正处理逻辑写这里
}
- 不用 NULL 的迭代（普通栈 / 队列）
分两类：层序队列、简单前序栈
① BFS 队列（完全不需要 NULL）
层序遍历逻辑：拿到节点立刻处理，再把子节点入队
访问 = 处理，两步合并，不需要标记分割时机。
② 简单前序栈（不用 NULL）
前序规则：中→左→右
取出节点马上处理，再先压右、后压左，访问和处理同步完成，不需要等回溯。
比如双栈求二叉树路径、简单前序遍历。
while(!st.empty()){
auto node=st.top();st.pop();
// 直接处理
if(node->right) st.push(node->right);
if(node->left) st.push(node->left);
}
while(!que.empty()){
int size=que.size();
for(...) {
auto node=que.front();que.pop();
swap(node->left,node->right); // 取出直接处理
if(node->left) que.push(node->left);
}
}
区分规则
处理节点的操作，要等左右子树全部走完才执行（后序 / 中序 / 回溯算深度）
→ 必须用 NULL 标记分割访问、处理两步，栈里要存 nullptr
取出节点立刻执行处理，不用等子树遍历完（前序迭代、层序 BFS）
→ 不需要 NULL，直接存取正常节点即可
4. 举两个你见过的代码对照
需要 NULL：求最大深度栈迭代
要等一条路径走完再深度回溯 depth–，必须 NULL 标记判断什么时候回退一层。
不需要 NULL：翻转二叉树队列 BFS
拿出节点直接 swap 左右，当场处理，不需要等待，不用标记。
极简总结
存 NULL：为了模拟递归回溯，把「访问节点」和「处理节点」分成两个阶段；
不存 NULL：访问节点和处理节点同时发生，取出立刻操作，无需标记。
方法二：加一个 boolean 值跟随每个节点，false (默认值) 表示需要为该节点和它的左右儿子安排在栈中的位次，true 表示该节点的位次之前已经安排过了，可以收割节点了。 这种方法可以叫做boolean 标记法
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
stack<pair<TreeNode*, bool>> st;
if (root != nullptr)
st.push(make_pair(root, false)); // 多加一个参数，false 为默认值，含义见下文注释
while (!st.empty()) {
auto node = st.top().first;
auto visited = st.top().second; //多加一个 visited 参数，使“迭代统一写法”成为一件简单的事
st.pop();
if (visited) { // visited 为 True，表示该节点和两个儿子位次之前已经安排过了，现在可以收割节点了
result.push_back(node->val);
continue;
}
// visited 当前为 false, 表示初次访问本节点，此次访问的目的是“把自己和两个儿子在栈中安排好位次”。
// 中序遍历是'左中右'，右儿子最先入栈，最后出栈。
if (node->right)
st.push(make_pair(node->right, false));
// 把自己加回到栈中，位置居中。
// 同时，设置 visited 为 true，表示下次再访问本节点时，允许收割。
st.push(make_pair(node, true));
if (node->left)
st.push(make_pair(node->left, false)); // 左儿子最后入栈，最先出栈
}
return result;
}
};
make_pair(a,b) 是 C++ 标准库函数，作用：快速生成一个 pair 键值对对象
pair<T1,T2> 是一个结构体，存两个数据：
.first：第一个元素
.second：第二个元素
两种创建 pair 的写法对比
写法 1：make_pair
st.push(make_pair(root, false));
自动推导类型，不用手动写尖括号，简洁。
写法 2：直接构造 pair<>
st.push(pair<TreeNode*, bool>(root, false));
必须完整写出模板类型，写起来很长。
make_pair(root, false)
==
pair<TreeNode*, bool>(root, false)
#include <utility> // make_pair、pair都在这个头文件
#include <iostream>
using namespace std;
int main() {
// 生成 pair<int, string>
auto p = make_pair(100, "hello");
cout << p.first << endl; // 100
cout << p.second << endl; // hello
return 0;
}
C++11 以后还能用大括号简写替代 make_pair：
st.push({root, false});
效果和 make_pair(root,false) 完全一样。
deque和queue
#include <deque>
#include <iostream>
using namespace std;
int main() {
deque<int> dq;
dq.push_back(1);
dq.push_back(2);
dq.push_front(0); // [0,1,2]
cout << dq.front() << endl; // 0
cout << dq.back() << endl; // 2
cout << dq.size() << endl; // 3
dq.pop_front(); // 删0 → [1,2]
dq.pop_back(); // 删2 → [1]
cout << dq[0] << endl; //1
dq.clear();
cout << dq.empty() << endl; //1
return 0;
}
#include <queue>
#include <iostream>
using namespace std;
int main() {
queue<int> q;
q.push(10);
q.push(20);
q.push(30);
cout << q.front() << endl; //10
cout << q.back() << endl; //30
cout << q.size() << endl; //3
q.pop(); // 删除队头10
cout << q.front() << endl; //20
if (!q.empty()) {
q.pop();
}
return 0;
}
deque：两头都能增删，支持下标 []
push_back / push_front
pop_back / pop_front
queue：只能尾插、头删，两头只读，无下标
只有 push()、pop()
没有 push_back、push_front、[]、clear
变量作用域规则
大括号 {} 划定变量作用域；
在 for 的 {} 里定义的 vec，出了 for 循环就被销毁，外部无法使用。
while(!que.empty()){
int size = que.size();
for(int i = 0; i<size; i++){
vector<int> vec; // vec 只在这个{}内部生效
TreeNode* node = que.front();
que.pop();
vec.push_back(node->val);
if(node->left) que.push(node->left);
if(node->right) que.push(node->right);
} // for 循环结束，vec 生命周期结束，直接销毁
result.push_back(vec); // 这里根本找不到vec，报错
}
正确写法：vec 写在 for 外面、while 内部，每一层对应一个 vec，一层遍历完再存入 result：
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> result;
queue<TreeNode*> que;
if(root) que.push(root);
while(!que.empty()){
int size = que.size();
vector<int> vec; // 一层共用一个数组，作用域在while本轮内
for(int i = 0; i<size; i++){
TreeNode* node = que.front();
que.pop();
vec.push_back(node->val);
if(node->left) que.push(node->left);
if(node->right) que.push(node->right);
}
// 当前层所有值收集完毕，存入总结果
result.push_back(vec);
}
return result;
}
二叉树层序遍历
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
queue<TreeNode*> que;
if (root != NULL) que.push(root);
vector<vector<int>> result;
while (!que.empty()) {
int size = que.size();
vector<int> vec;
// 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的
for (int i = 0; i < size; i++) {
TreeNode* node = que.front();
que.pop();
vec.push_back(node->val);
if (node->left) que.push(node->left);
if (node->right) que.push(node->right);
}
result.push_back(vec);
}
return result;
}
};
# 递归法
class Solution {
public:
void order(TreeNode* cur, vector<vector<int>>& result, int depth)
{
if (cur == nullptr) return;
if (result.size() == depth) result.push_back(vector<int>());
result[depth].push_back(cur->val);
order(cur->left, result, depth + 1);
order(cur->right, result, depth + 1);
}
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> result;
int depth = 0;
order(root, result, depth);
return result;
}
};
两类 STL 算法
一、void 返回：原地修改，不能 return
函数直接改原容器，无返回值，必须单独一行调用
代表：sort、reverse、fill、swap、unique、erase
错误：
return sort(v.begin(), v.end());
return reverse(v.begin(), v.end());
正确写法：
sort(v.begin(), v.end());
reverse(v.begin(), v.end());
return v;
二、有返回值：查询 / 查找类，返回迭代器 / 数值
不会修改容器，只是返回一个结果，可以赋值、可以 return
返回迭代器
find、max_element、min_element、lower_bound、upper_bound
示例：
auto it = find(v.begin(), v.end(), 5);
return it;
返回数字
count、accumulate
int cnt = count(v.begin(), v.end(), 3);
求最大值
int maxValue = INT_MIN;
maxValue = node->val > maxValue ? node->val : maxValue;
二叉树的最小深度
递归：不会出现错误把深度算成 1 的问题，天然规避单侧子树为空的陷阱，所以只需要一次叶子判断。
class Solution {
public:
int getDepth(TreeNode* node) {
if (node == NULL) return 0;
int leftDepth = getDepth(node->left); // 左
int rightDepth = getDepth(node->right); // 右
// 中
// 当一个左子树为空，右不为空，这时并不是最低点
if (node->left == NULL && node->right != NULL) {
return 1 + rightDepth;
}
// 当一个右子树为空，左不为空，这时并不是最低点
if (node->left != NULL && node->right == NULL) {
return 1 + leftDepth;
}
int result = 1 + min(leftDepth, rightDepth);
return result;
}
int minDepth(TreeNode* root) {
return getDepth(root);
}
};
前序遍历：空节点统一返回 0，但 0 不代表有效路径，会让 min 出错，必须额外区分单侧为空的三种场景。
class Solution {
private:
int result;
void getdepth(TreeNode* node, int depth) {
// 函数递归终止条件
if (node == nullptr) {
return;
}
// 中，处理逻辑：判断是不是叶子结点
if (node -> left == nullptr && node->right == nullptr) {
result = min(result, depth);
}
if (node->left) { // 左
getdepth(node->left, depth + 1);
}
if (node->right) { // 右
getdepth(node->right, depth + 1);
}
return ;
}
public:
int minDepth(TreeNode* root) {
if (root == nullptr) {
return 0;
}
result = INT_MAX;
getdepth(root, 1);
return result;
}
};
平衡二叉树判定
迭代方式可以先定义一个函数，专门用来求高度。
这个函数通过栈模拟的后序遍历找每一个节点的高度（其实是通过求传入节点为根节点的最大深度来求的高度）
然后再用栈来模拟后序遍历，遍历每一个节点的时候，再去判断左右孩子的高度是否符合，
第一个函数 getDepth 里的 stack：求某一棵子树的最大深度
第二个函数 isBalanced 里的 stack：遍历整棵树每一个节点，保证每个节点都检查一遍左右子树高度差。
两层栈的调用关系
isBalanced 的栈循环取出一个节点 node
调用 getDepth(node->left)
这里会新建另一套独立的 stack，专门算左子树深度，用完销毁
调用 getDepth(node->right)
又新建一套独立 stack，算右子树深度
class Solution {
private:
int getDepth(TreeNode* cur) {
stack<TreeNode*> st;
if (cur != NULL) st.push(cur);
int depth = 0; // 记录深度
int result = 0;
while (!st.empty()) {
TreeNode* node = st.top();
if (node != NULL) {
st.pop();
st.push(node); // 中
st.push(NULL);
depth++;
if (node->right) st.push(node->right); // 右
if (node->left) st.push(node->left); // 左
} else {
st.pop();
node = st.top();
st.pop();
depth--;
}
result = result > depth ? result : depth;
}
return result;
}
public:
bool isBalanced(TreeNode* root) {
stack<TreeNode*> st;
if (root == NULL) return true;
st.push(root);
while (!st.empty()) {
TreeNode* node = st.top(); // 中
st.pop();
if (abs(getDepth(node->left) - getDepth(node->right)) > 1) {
return false;
}
if (node->right) st.push(node->right); // 右（空节点不入栈）
if (node->left) st.push(node->left); // 左（空节点不入栈）
}
return true;
}
};
给定一个二叉树，返回所有从根节点到叶子节点的路径。
// 版本一
class Solution {
private:
void traversal(TreeNode* cur, vector<int>& path, vector<string>& result) {
path.push_back(cur->val); // 中，中为什么写在这里，因为最后一个节点也要加入到path中
// 这才到了叶子节点
if (cur->left == NULL && cur->right == NULL) {
string sPath;
for (int i = 0; i < path.size() - 1; i++) {
sPath += to_string(path[i]);
sPath += "->";
}
sPath += to_string(path[path.size() - 1]);
result.push_back(sPath);
return;
}
if (cur->left) { // 左
traversal(cur->left, path, result);
path.pop_back(); // 回溯
}
if (cur->right) { // 右
traversal(cur->right, path, result);
path.pop_back(); // 回溯
}
}
public:
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> result;
vector<int> path;
if (root == NULL) return result;
traversal(root, path, result);
return result;
}
};
void traversal(TreeNode* cur, string path, vector& result)
path 没有 &，是值传递
每次递归调用 traversal(cur->left, path + “->”, result) 时，会拷贝一份全新字符串给下一层函数
每层的 path 都是独立副本，互不干扰，上层原始字符串不会被修改
不需要 pop_back：
递归左子树结束后，回到当前函数，当前层的 path 还是原来的样子，没有新增内容，直接拿去给右子树 path + “->”
//版本二
class Solution {
private:
void traversal(TreeNode* cur, string path, vector<string>& result) {
path += to_string(cur->val); // 中，中为什么写在这里，因为最后一个节点也要加入到path中
if (cur->left == NULL && cur->right == NULL) {
result.push_back(path);
return;
}
if (cur->left) {
path += "->";
traversal(cur->left, path, result); // 左
path.pop_back(); // 回溯 '>'
path.pop_back(); // 回溯 '-'
}
if (cur->right) {
path += "->";
traversal(cur->right, path, result); // 右
path.pop_back(); // 回溯'>'
path.pop_back(); // 回溯 '-'
}
}
public:
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> result;
string path;
if (root == NULL) return result;
traversal(root, path, result);
return result;
}
};
递归
递归函数什么时候需要返回值？什么时候不需要返回值？这里总结如下三点：
如果需要搜索整棵二叉树且不用处理递归返回值，递归函数就不要返回值。
如果需要搜索整棵二叉树且需要处理递归返回值，递归函数就需要返回值。
如果要搜索其中一条符合条件的路径，那么递归一定需要返回值，因为遇到符合条件的路径了就要及时返回。
if (cur->left) { // 左 （空节点不遍历）
// 遇到叶子节点返回true，则直接返回true
if (traversal(cur->left, count - cur->left->val)) return true; // 注意这里有回溯的逻辑
}
if (cur->right) { // 右 （空节点不遍历）
// 遇到叶子节点返回true，则直接返回true
if (traversal(cur->right, count - cur->right->val)) return true; // 注意这里有回溯的逻辑
}
return false;
等价于
if (cur->left) { // 左
count -= cur->left->val; // 递归，处理节点;
if (traversal(cur->left, count)) return true;
count += cur->left->val; // 回溯，撤销处理结果
}
if (cur->right) { // 右
count -= cur->right->val;
if (traversal(cur->right, count)) return true;
count += cur->right->val;
}
return false;
根据一棵树的中序遍历与后序遍历构造二叉树
第一步：如果数组大小为零的话，说明是空节点了。
第二步：如果不为空，那么取后序数组最后一个元素作为节点元素。
第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点
第四步：切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，一定是先切中序数组）
第五步：切割后序数组，切成后序左数组和后序右数组
第六步：递归处理左区间和右区间
class Solution {
private:
TreeNode* traversal (vector<int>& inorder, vector<int>& postorder) {
if (postorder.size() == 0) return NULL;
// 后序遍历数组最后一个元素，就是当前的中间节点
int rootValue = postorder[postorder.size() - 1];
TreeNode* root = new TreeNode(rootValue);
// 叶子节点
if (postorder.size() == 1) return root;
// 找到中序遍历的切割点
int delimiterIndex;
for (delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++) {
if (inorder[delimiterIndex] == rootValue) break;
}
// 切割中序数组
// 左闭右开区间：[0, delimiterIndex)
vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex);
// [delimiterIndex + 1, end)
vector<int> rightInorder(inorder.begin() + delimiterIndex + 1, inorder.end() );
// postorder 舍弃末尾元素
postorder.resize(postorder.size() - 1);
// 切割后序数组
// 依然左闭右开，注意这里使用了左中序数组大小作为切割点
// [0, leftInorder.size)
vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());
// [leftInorder.size(), end)
vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end());
root->left = traversal(leftInorder, leftPostorder);
root->right = traversal(rightInorder, rightPostorder);
return root;
}
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if (inorder.size() == 0 || postorder.size() == 0) return NULL;
return traversal(inorder, postorder);
}
};
求数组内元素两两间最小差值
int result = INT_MAX;
for (int i = 1; i < vec.size(); i++) { // 统计有序数组的最小差值
result = min(result, vec[i] - vec[i-1]);
}
return result;
使用迭代法写中序遍历，就需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素
在迭代的过程中，其实我们有两个操作：
处理：将元素放进result数组中
访问：遍历节点
前序遍历的代码，不能和中序遍历通用呢，因为前序遍历的顺序是中左右，先访问的元素是中间节点，要处理的元素也是中间节点，所以刚刚才能写出相对简洁的代码，因为要访问的元素和要处理的元素顺序是一致的，都是中间节点。
那么再看看中序遍历，中序遍历是左中右，先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理节点（也就是在把节点的数值放进result数组中），这就造成了处理顺序和访问顺序是不一致的。
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> st;
TreeNode* cur = root;
while (cur != NULL || !st.empty()) {
if (cur != NULL) { // 指针来访问节点，访问到最底层
st.push(cur); // 将访问的节点放进栈
cur = cur->left; // 左
} else {
cur = st.top(); // 从栈里弹出的数据，就是要处理的数据（放进result数组里的数据）
st.pop();
result.push_back(cur->val); // 中
cur = cur->right; // 右
}
}
return result;
}
};
模板
while(cur || !st.empty()){
if(cur){
st.push(cur); cur=cur->left;
}else{
cur=st.top(); st.pop();
// 直接在这里处理节点，天然按中序顺序
cur=cur->right;
}
}
递归返回值
递归函数有返回值就是要遍历某一条边，但有返回值也要看如何处理返回值！
如果递归函数有返回值，如何区分要搜索一条边，还是搜索整个树呢？
搜索一条边的写法：
if (递归函数(root->left)) return ;
if (递归函数(root->right)) return ;
搜索整个树写法：
left = 递归函数(root->left); // 左
right = 递归函数(root->right); // 右
left与right的逻辑处理; // 中
在递归函数有返回值的情况下：如果要搜索一条边，递归函数返回值不为空的时候，立刻返回，如果搜索整个树，直接用一个变量left、right接住返回值，这个left、right后序还有逻辑处理的需要，也就是后序遍历中处理中间节点的逻辑（也是回溯）。
求最小公共祖先，需要从底向上遍历，那么二叉树，只能通过后序遍历（即：回溯）实现从底向上的遍历方式。
在回溯的过程中，必然要遍历整棵二叉树，即使已经找到结果了，依然要把其他节点遍历完，因为要使用递归函数的返回值（也就是代码中的left和right）做逻辑判断。
要理解如果返回值left为空，right不为空为什么要返回right，为什么可以用返回right传给上一层结果。
如果递归函数有返回值，如何区分要搜索一条边，还是搜索整个树。
搜索一条边的写法：
if (递归函数(root->left)) return ;
if (递归函数(root->right)) return ;
搜索整个树写法：
left = 递归函数(root->left);
right = 递归函数(root->right);
left与right的逻辑处理;
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == q || root == p || root == NULL) return root;
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
if (left != NULL && right != NULL) return root;
if (left == NULL && right != NULL) return right;
else if (left != NULL && right == NULL) return left;
else { // (left == NULL && right == NULL)
return NULL;
}
}
};
回溯
回溯算法模板框架如下
void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}
}
string转int
int digit = digits[index] - ‘0’; // 将index指向的数字转为int
组合
需要startIndex来控制for循环的起始位置，对于组合问题，什么时候需要startIndex呢？
如果是一个集合来求组合的话，就需要startIndex，
如果是多个集合取组合，各个集合之间相互不影响，那么就不用startIndex
for(int i = 0; i < candidates.size(); i++)：每次都从头遍历全部数字 → 出现重复组合 [2,3] [3,2]，且极易无限递归栈溢出；
for(int i = start; i < candidates.size(); i++)：只能从当前下标往后选，不会回头取前面数字，保证组合不重复，
void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {
if (sum == target) {
result.push_back(path);
return;
}
// 如果 sum + candidates[i] > target 就终止遍历
for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {
sum += candidates[i];
path.push_back(candidates[i]);
backtracking(candidates, target, sum, i);
sum -= candidates[i];
path.pop_back();
}
}
数组里面重复的元素删除
一、vector 有序数组去重（LeetCode 高频，推荐）
前提：数组先排序 sort(v.begin(),v.end())
函数：unique + erase
unique 只把重复元素移到末尾，返回新尾迭代器，再 erase 删掉后面重复段
unique 相邻相同只留一个，所以必须先排序才能全局去重
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> v = {1,2,2,3,3,3,4};
sort(v.begin(), v.end()); // 必须排序
auto last = unique(v.begin(), v.end());
v.erase(last, v.end());
// v = [1,2,3,4]
return 0;
}
二、无序 vector 去重（不排序，用哈希集合）
不需要改变原数组顺序，用 unordered_set 查重：
vector<int> v = {2,1,2,3,1};
unordered_set<int> s;
vector<int> res;
for(int x : v){
if(!s.count(x)){
s.insert(x);
res.push_back(x);
}
}
// res = [2,1,3]
三、原生普通数组 int a [] 去重
- 有序数组手动原地去重（双指针）
int a[] = {1,1,2,2,3};
int n = sizeof(a)/sizeof(a[0]);
int j = 0;
for(int i=0;i<n;i++){
if(a[i] != a[j]){
j++;
a[j] = a[i];
}
}
// 前 j+1 位是去重结果：a[0]~a[j]
- 无序数组转 set 再复制
int a[] = {1,2,2,3};
int n = sizeof(a)/sizeof(a[0]);
unordered_set<int> st(a, a+n);
vector<int> res(st.begin(), st.end());
四、字符串 string 去重
string s = "aabbcc";
sort(s.begin(),s.end());
auto last = unique(s.begin(),s.end());
s.erase(last, s.end());
// s = "abc"
一、先拆开两段代码
1）组合专用：i > startIndex && nums[i]==nums[i-1]
cpp
运行
for(int i = startIndex; i < n; i++)
{
if(i > startIndex && nums[i]==nums[i-1]) continue;
backtrack(..., i+1);
}
2）排列专用：i>0 && nums[i]==nums[i-1] && used[i-1]==false
cpp
运行
for(int i = 0; i < n; i++)
{
if(used[i]) continue;
if(i>0 && nums[i]==nums[i-1] && !used[i-1]) continue;
backtrack(used);
}
int 和string转换
string 和 int 互相转换（C++ 刷题高频）
一、int → string 数字转字符串
- to_string () 最简单（推荐）
#include
using namespace std;
int num = 12345;
string s = to_string(num);
// s = “12345”
int neg = -99;
string s2 = to_string(neg);
// s2 = “-99” - stringstream 方式（兼容老标准）
#include
int x = 666;
stringstream ss;
ss << x;
string s = ss.str();
二、string → int 字符串转数字 - stoi () 转 int（C++11+）
string s = “123”;
int a = stoi(s); // a=123
string s2 = “-456”;
int b = stoi(s2); // b=-456
注意：字符串超出 int 范围会报错溢出。 - stol /stoll 大数字
stol → long
stoll → long long
string big = “1234567890123”;
long long num = stoll(big); - stringstream 通用转换
string s = “789”;
stringstream ss(s);
int x;
ss >> x; // x=789
三、常用小操作：逐字符取数字
字符串里单个数字字符转 int：
char ch = ‘5’;
int num = ch - ‘0’; // ‘5’-‘0’ = 5
反向：int 数字转单个字符
int x = 7;
char c = x + ‘0’; // ‘7’
四、易错点
stoi 只能纯数字字符串，含字母直接运行报错
to_string 支持正负整数
单个字符 ‘9’ 和字符串 “9” 转换逻辑不一样：
“9” → stoi
‘9’ → c - ‘0’
超大数字别用 stoi，用 stoll 防止溢出
string 的 push_back 用法
string.push_back(单个字符char)，只能加一个字符，不能直接塞字符串
- 正确用法：追加单个字符
string s;
s.push_back(‘a’);
s.push_back(‘5’);
s.push_back(‘-’);
// s = “a5-”
string.push_back©：参数必须是 char 单个字符
拼接整个字符串：用 s += 另一个string
vector::push_back(string) 可以直接存完整字符串，和 string 的 push_back 区分开
string的erase和insert
一、insert 插入
格式：s.insert(插入位置下标, 内容)
- 插入字符串
string s = “1234”;
s.insert(2, “abc”);
// 下标2前面插入，结果：“12abc34” - 插入单个字符（重复 n 个）
string s = “1234”;
s.insert(1, 3, ‘x’);
// 在下标1插入3个x → “1xxx234” - 插入子串
string s = “abcd”;
string t = “123”;
s.insert(0, t, 1, 2);
// 在0位置，取t从下标1开始2个字符插入
// t.substr(1,2) = “23” → “23abcd”
二、erase 删除
三种重载：
erase(pos, len)：从 pos 开始删 len 个字符
erase(pos)：从 pos 删到末尾
erase(迭代器) / erase(左,右) 删除区间
示例 1：指定起点 + 长度
string s = “0123456”;
s.erase(1,3);
// 下标1开始删3个：1、2、3删掉 → “0456”
示例 2：只给起点，删到结尾
string s = “abcdef”;
s.erase(3);
// 下标3到最后全部删除 → “abc”
示例 3：删除单个字符（迭代器）
string s = “abcd”;
s.erase(s.begin() + 1);
// 删除下标1字符 → “acd”
示例 4：删除一段区间 [左，右)
string s = “012345”;
s.erase(s.begin()+1, s.begin()+4);
// 删除下标1、2、3 → “045”
判断为0-255区间
bool isValid(const string& s, int start, int end) {
if (start > end) {
return false;
}
if (s[start] == '0' && start != end) { // 0开头的数字不合法
return false;
}
int num = 0;
for (int i = start; i <= end; i++) {
if (s[i] > '9' || s[i] < '0') { // 遇到非数字字符不合法
return false;
}
num = num * 10 + (s[i] - '0');
if (num > 255) { // 如果大于255了不合法
return false;
}
}
return true;
}
子集去重（subsetsWithDup）
每层只能从 startindex 往后选，不存在回头选取，只用 i>startindex && nums[i]==nums[i-1]，不需要 used 数组。
含重复全排列（permuteUnique）
每层从头遍历所有下标，可以回头选，必须用 used 数组判断：i>0 && nums[i]==nums[i-1] && used[i-1]==false。
vector::assign 完整用法
作用：覆盖原有全部元素，重新赋值，直接改变容器大小
- 重载 1：assign (n, val) 填充 n 个相同值
vector<int> used;
// 开辟nums.size()个空间，全部初始化为0
used.assign(nums.size(), 0);
- 重载 2：assign (迭代器左，迭代器右) 拷贝另一容器区间
vector<int> a = {1,2,3};
vector<int> b;
b.assign(a.begin(), a.end()); // b = [1,2,3]
- 重载 3：初始化列表 C++11
vector<int> v;
v.assign({2,4,6}); // v = [2,4,6]
去重
去重一定要对元素进行排序，这样我们才方便通过相邻的节点来判断是否重复使用了
一般来说：组合问题和排列问题是在树形结构的叶子节点上收集结果，而子集问题就是取树上所有节点的结果。
第一段：利用排序 + used[i-1]==false 去重（树层跳过重复）
前置条件：sort(nums) 让相同数字挨在一起
判断：
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) continue;
逻辑拆解：
nums[i]==nums[i-1]：当前数字和前一个重复；
used[i-1]==false：前一个相同数字不在当前 path 里，说明上一轮同层已经选过这个数字，会生成完全一样的排列，直接跳过。
特点：不用额外容器，纯数组判断，空间开销极小。
第二段：每层新建 unordered_set uset 去重
每层循环一开始创建局部哈希集合：
unordered_set<int> uset;
for(int i=0;...){
if(uset.find(nums[i])!=uset.end()) continue;
uset.insert(nums[i]);
}
逻辑拆解：
同一层循环里，只要这个数字在本层已经出现过，就跳过，不管下标是否相邻，不需要提前 sort 排序。
特点：靠哈希集合记录本层用过的数字，天然去重，不用依赖数组有序。
- 是否需要排序
版本 1：必须 sort (nums)，相同数字挨在一起，nums[i]==nums[i-1] 判断才生效；不排序直接失效，会出现重复排列。
版本 2：不需要排序，uset 直接记录本层出现过的值，数字分散也能去重。 - 空间消耗
版本 1：只需要一个全局 vector used，无额外临时容器，空间最优。
版本 2：每层递归都会新建一个 unordered_set，递归深度等于 nums 长度，会额外占用哈希表内存；数字越多，开销越大。
两种写法的性能分析
需要注意的是：使用set去重的版本相对于used数组的版本效率都要低很多，大家在leetcode上提交，能明显发现。
原因在回溯算法：递增子序列 (opens new window)中也分析过，主要是因为程序运行的时候对unordered_set 频繁的insert，unordered_set需要做哈希映射（也就是把key通过hash function映射为唯一的哈希值）相对费时间，而且insert的时候其底层的符号表也要做相应的扩充，也是费时的。
而使用used数组在时间复杂度上几乎没有额外负担！
使用set去重，不仅时间复杂度高了，空间复杂度也高了，在本周小结！（回溯算法系列三） (opens new window)中分析过，组合，子集，排列问题的空间复杂度都是O(n)，但如果使用set去重，空间复杂度就变成了O(n^2)，因为每一层递归都有一个set集合，系统栈空间是n，每一个空间都有set集合。
那有同学可能疑惑 用used数组也是占用O(n)的空间啊？
used数组可是全局变量，每层与每层之间公用一个used数组，所以空间复杂度是O(n + n)，最终空间复杂度还是O(n)。
std::vectorstd::string chessboard(n, std::string(n, ‘.’));
创建一个 n行n列 的棋盘，每个格子初始都是字符 .。
等价 n×n 二维字符棋盘。
内层：std::string(n, ‘.’)
构造一个长度为 n 的字符串，全部填充字符 .
例：string(3, ‘.’) → “…”
外层 vector：vector<字符串>(数量, 元素)
第一个参数 n：vector 有 n 个元素（n 行）
第二个参数 std::string(n, ‘.’)：每一行都是上面生成的 n 个点的字符串
// 先造一行
string line(n, '.');
// 造n行
vector<string> chessboard(n, line);
N皇后
N 皇后是从上到下一行一行放皇后：
先放第 0 行 → 再放第 1 行 → …… 最后放第 n-1 行。
当我们准备在 (row, col) 放皇后时：
row 这一行上面的所有行（0 ~ row-1）已经放好了皇后；
row 下面的行还全是空的，不可能有皇后，不用往下检查。
所以 isValid 只需要检查「当前位置的上方、左上对角线、右上对角线」有没有已经存在的皇后。
整体逻辑总结
同一列上面有皇后 → 不行
左上斜线上有皇后 → 不行
右上斜线上有皇后 → 不行
三个方向都没皇后 → 返回 true，可以放皇后
为什么不用检查下方、左下、右下？
因为我们是逐行从上往下填，row 下面所有格子还都是 .，根本没有皇后，检查纯纯浪费时间，这就是代码注释说的剪枝。
数独
- 检查当前整行有没有重复数字 val
for (int i = 0; i < 9; i++) {
if (board[row][i] == val) {
return false;
}
}
固定行 row，列 i 从 0~8 遍历一整行
只要这一行任意一格等于要填的数字 val → 重复，非法
2. 检查当前整列有没有重复数字 val
for (int j = 0; j < 9; j++) {
if (board[j][col] == val) {
return false;
}
}
- 找到当前格子所属 3×3 小九宫，遍历九宫检查重复
int startRow = (row / 3) * 3;
int startCol = (col / 3) * 3;
9 行 9 列分成 9 个 3×3 小方块：
行 0,1,2 → 第一大行，startRow = 0
行 3,4,5 → 第二大行，startRow = 3
行 6,7,8 → 第三大行，startRow = 6
row / 3 整数除法得到属于第几块，再 ×3 得到九宫左上角行号；列同理。
双层循环遍历这个 3×3 九宫全部格子：
for (int i = startRow; i < startRow + 3; i++) {
for (int j = startCol; j < startCol + 3; j++) {
if (board[i][j] == val ) {
return false;
}
}
}
只要小九宫内存在相同数字，冲突返回 false。
cmp
class Solution {
static bool cmp(int a, int b) {
return abs(a) > abs(b);
}
public:
int largestSumAfterKNegations(vector<int>& A, int K) {
sort(A.begin(), A.end(), cmp); // 第一步
for (int i = 0; i < A.size(); i++) { // 第二步
if (A[i] < 0 && K > 0) {
A[i] *= -1;
K--;
}
}
if (K % 2 == 1) A[A.size() - 1] *= -1; // 第三步
int result = 0;
for (int a : A) result += a; // 第四步
return result;
}
};
- cmp 作用
自定义排序规则：按数字绝对值从大到小排。
abs(a) > abs(b)：如果 a 的绝对值更大，a 放前面。 - 怎么传给 sort
sort 第三个参数就是自定义比较函数，这里直接填函数名 cmp。 - 为什么加 static？
cmp 是类内成员函数，普通成员函数隐含 this 参数，sort 无法匹配；
加 static 变成静态函数，没有隐藏 this，签名 bool(int,int) 刚好匹配 sort 需要的比较器。
1.普通成员函数暗藏隐藏参数 this
class Solution {
public:
// 普通成员函数（非static）
bool cmp(int a, int b) {
return abs(a) > abs(b);
}
};
表面写的参数是 (int a, int b)，编译器底层会偷偷补一个参数
// 编译器真实函数原型
bool cmp(Solution* this, int a, int b);
this：指向当前调用这个函数的类对象指针
只要是普通成员函数，第一个参数永远隐藏是 this
2. sort 需要的比较器格式
sort 的第三个参数要求：只接收两个 int、返回 bool 的可调用对象
标准要求签名：bool (int, int)
如果你传普通成员函数 cmp：
它真实签名是 bool(Solution*, int, int)，多出来一个 Solution* 参数，类型对不上，编译器直接报错，匹配失败。
3. static 静态成员函数的区别
static bool cmp(int a, int b) {
return abs(a) > abs(b);
}
static 修饰的函数不属于某个对象，属于整个类，不需要对象调用，没有隐藏的 this 指针。
编译器底层原型就是你写的样子：
bool cmp(int a, int b);
刚好和 sort 需要的 bool(int,int) 格式完全匹配，可以直接传给 sort。
lambda 匿名函数
- 基础语法结构
[捕获列表](参数列表) -> 返回值类型 { 函数体 };
极简拆分：
[]：捕获外部变量（可以不用、传值、传引用）
()：形参，和普通函数一样
->类型：返回值类型，能自动推导时可省略
{}：逻辑代码
原来 static cmp 写法
static bool cmp(int a, int b){
return abs(a) > abs(b);
}
sort(A.begin(), A.end(), cmp);
等价 lambda，直接写在 sort 里，不用定义类内函数
sort(A.begin(), A.end(), [](int a, int b) {
return abs(a) > abs(b);
});
[] 空括号：不需要捕获外部任何变量
(int a,int b)：两个比较参数
省略 ->bool：return 布尔值，编译器自动推导返回 bool
- [] 捕获列表四种常用写法（重点）
假设外部有变量 int x, vector nums
[] 不捕获任何外部变量（上面排序用的）
[=] 值捕获：复制所有外部变量，只读，不能改
int k = 3;
auto f = [=](int a){
return a + k; // 可读k，不能修改k
};
[&] 引用捕获：拿到变量本体，可以修改外部变量
int sum = 0;
auto add = [&](int x){
sum += x; // 直接修改外部sum
};
[变量名] / [&变量名] 单独捕获指定变量
// 只引用捕获k，其他外部变量不用
[&k](int a){ return a - k; }
带返回值显式声明 -> （需要时写）
auto func = [](int a, int b) -> int {
return a * b;
};
只有返回类型模糊、或者返回空指针 / 复杂类型才需要写，单纯 bool、int 一般省略。
vector 与 list insert 插入语法对比
核心区别前置
vector：连续数组，支持随机访问迭代器，begin() + n 合法；中间 / 头部插入会挪动大量元素，效率低。
list：双向链表，不支持 begin()+n，只能一步步移动迭代器；任意位置插入仅修改指针，O (1)。
两者 insert 函数签名一致：容器.insert(迭代器, 待插入元素)，都是插在迭代器指向元素的前面。
一、vector 插入语法
- 指定下标位置插入（最常用）
#include <vector>
vector<int> v = {1,3,4};
// 在下标1的位置插入2，begin()+1 直接偏移
v.insert(v.begin() + 1, 2);
// v = [1,2,3,4]
// 头部插入
v.insert(v.begin(), 0);
// 尾部插入（等价push_back）
v.insert(v.end(), 5);
- 批量插入多个相同值
v.insert(v.begin(), 2, 9); // 开头插2个9
- 插入另一个容器区间
vector<int> tmp = {10,20};
v.insert(v.end(), tmp.begin(), tmp.end());
vector 坑
// 插入后原有迭代器全部失效（内存移位/扩容）
auto it = v.begin()+1;
v.insert(v.begin(), 99);
// *it 非法，崩溃
二、list 插入语法
list 不能写 begin() + pos，必须先把迭代器移动到目标位置，两种移动写法：
写法 1：while 循环移动
#include <list>
list<vector<int>> que;
int pos = 1;
auto it = que.begin();
while (pos--) {
it++;
}
que.insert(it, {7,1});
写法 2：advance 标准库函数
list<int> lst = {1,3};
auto it = lst.begin();
advance(it, 1); // 向后移动1步
lst.insert(it, 2); // [1,2,3]
list 其他插入方式
list<int> l;
l.push_front(1); // 头插专用
l.push_back(2); // 尾插专用
l.insert(l.end(), 3); // 尾部插入
l.insert(l.begin(), {10,20}); // 初始化列表批量插
list 特性
插入仅当前迭代器失效，其他迭代器、指针不受影响。
vector<uint64_t> dp(amount + 1, 0)
类型 uint64_t
无符号 64 位整数，范围：0 ~ 18446744073709551615
普通 int 一般是 32 位，上限约 21 亿；硬币组合方案数很大时，累加会int 溢出，结果变成负数、乱码。
用 64 位超大容量无符号整数，容纳极大的方案总数，避免溢出。
if (dp[j] < INT_MAX - dp[j - coins[i]])
dp[j] = dp[j] + dp[j - coins[i]];
INT_MAX 是 头文件定义的 int 最大值（一般 2147483647）。
加法溢出规则：
如果 a + b > INT_MAX，int 溢出属于未定义行为，数值乱跳、答案出错。
uint64_t vs long long 对比
- 基础类型信息long long
有符号 64 位整数
头文件：内置基础类型，无需额外头文件
取值范围：
-9223372036854775808- 9223372036854775807
可存正数、负数
uint64_t
无符号 64 位整数
头文件： 必须引入，否则无法识别
取值范围：
(0 ;\sim; 18446744073709551615)
只能存 ≥0 的数字，不存在负数
string str.substr(pos, len);
第 1 参数 pos：起始下标（从 0 开始）
第 2 参数 len：截取字符的长度（不是结束下标）
s.substr(startIndex, i - startIndex + 1)长度推导区间：下标 startIndex ~ i（左右都包含）
包含字符总个数：
i - startIndex + 1
C++ 固定宽度整数类型
头文件：#include
分为 有符号 (signed)、无符号 (unsigned)
一、常用全套清单
1）8 位（1 字节）
int8_t 有符号：[-128, 127]
uint8_t 无符号：[0, 255]
2）16 位（2 字节）
int16_t
uint16_t
3）32 位（4 字节）
int32_t
uint32_t
4）64 位（8 字节）刷题重点
int64_t 有符号 等价 long long
uint64_t 无符号 等价 unsigned long long
int32_t ↔ int
uint32_t ↔ unsigned int
int64_t ↔ long long
uint64_t ↔ unsigned long long
priority_queue 自定义比较器
priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pq;
第 1 个模板参数：存的元素 pair<int,int>
第 2 个：底层容器，一般用vector<pair<int,int>>
第 3 个：比较仿函数 mycomparison
写法 1：仿函数结构体
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
// 小顶堆：pair.first 小的在堆顶
struct mycomparison
{
bool operator()(const pair<int,int>& a, const pair<int,int>& b)
{
return a.first > b.first;
}
};
int main()
{
priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pq;
pq.push({5,1});
pq.push({2,2});
pq.push({3,3});
while(!pq.empty())
{
auto top = pq.top();
pq.pop();
cout << top.first << endl; //输出 2 3 5
}
return 0;
}
写法 2：lambda（C++11 以后 priority_queue 不能直接把 lambda 写在模板参数，要构造传进去：
auto cmp = [](const pair<int,int>&a,const pair<int,int>&b){
return a.first > b.first;
};
priority_queue<pair<int,int>,vector<pair<int,int>>,decltype(cmp)> pq(cmp);
sort(v.begin(),v.end(),cmp); // return a>b 从小到大
priority_queue<…,cmp> pq; // return a>b 小顶堆
sort：返回 true 代表 a 排在 b 前面
priority_queue：返回 true 代表b 优先级比 a 高，b 放上面
AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。
更多推荐
4
0- 0
已为社区贡献3条内容
所有评论(0)