灵神：如何科学刷题？ https://leetcode.cn/discuss/post/3141566/ru-he-ke-xue-shua-ti-by-endlesscheng-q3yd/
新动计划： https://leetcode.cn/studyplan/primers-list/

结果 含义 核心排查方向 出错记录
PE 格式错误 空格 / 换行 / 大小写 / 输出顺序 / 字符宽度（如 %5d）/ 标点 打印时多了一个空格
WA 答案错误 逻辑漏洞、边界条件、数据类型溢出、特殊用例未处理（如 0 / 负数 / 极值） 边界0没处理
RE 运行时错误 数组越界、除 0、空指针、栈溢出、递归爆栈、scanf 参数漏 &
TLE 超时 算法复杂度太高、死循环、不必要的重复计算
MLE 内存超限 数组开太大、内存泄漏、重复申请内存
CE 编译错误 语法错误（少分号 / 括号）、头文件缺失、变量未定义、数据类型写错

平衡二叉树要求所有节点的左右子树高度差≤1

C++

1
2
3
4
5
6
7
#include<bits/stdc++.h> 
using namespace std;
int main( )
{

    return 0;
}

输入输出溢出

INT_MAX 表示int类型能表示的最大整数。
INT_MIN 表示int类型能表示的最小整数。

原封不动地打印：cout << R"(...内容...)" << endl;
P1000 超级玛丽游戏 - 洛谷

打印：

类型 格式符 备注
int %d
float、double %f
long long %lld
char %c
string %s string s; cin >> s; C++里用string替代char数组，无需固定长度，更安全

特殊格式控制：

说明 格式符 备注
占 5 个字符宽度（右对齐） %5d L1-008 求整数段和 - 团体程序设计天梯赛-练习集
占 5 个字符宽度（左对齐） %-5d
保留 2 位小数（四舍五入） %.2f
保留 0 位小数（取整） %.0f
补前导 0 到 5 位 %05d

cout 有一个自动优化功能！当小数部分是 0 的时候，它会自动不显示小数点和 0！

1
cout << 32.0 << endl; // 输出：32

在 C/C++ 的转义字符规则中：

  • 需要转义的字符：只有 \"（双引号）、\\（反斜杠）、\n（换行）、\t（制表符）等少数字符（因为这些字符有特殊含义）；
  • 不需要转义的字符：!、'（单引号）、,、.、- 等普通符号，直接写即可。

sqrt() 返回double。如果需要int类型，要强制转int。例如：int k = (int)sqrt((n + 1) / 2)
L1-002 打印沙漏 - 团体程序设计天梯赛-练习集
pow() 返回double。

◆优化方案
尽量避免循环遍历，最好直接下标访问。
结构体->直接数组下标访问：L1-005 考试座位号 - 团体程序设计天梯赛-练习集

当输入的值很大（比如 1e5）时，cin会比scanf慢很多，导致程序超时。必须加以下代码：

1
2
3
4
5
int main(){ 
	ios::sync_with_stdio(false); // 关闭cin和C输入流的同步 
	cin.tie(0); // 解绑cin和cout，避免cin等cout刷新 
	// 核心逻辑... 
}

循环优化（这里有点有点类似JavaScript的）

1
2
3
4
5
6
7
8
for(int i=0;i<s.size();i++){
	int a = s[i];
	// 逻辑
}
// 简化为：
for(int a : s){
	//逻辑
}

L1-011 A-B - 团体程序设计天梯赛-练习集

关于溢出

1
2
3
while(nums[right] > (long long)k * nums[left]){
// k * nums[left]两个int相乘，结果太大，超出int范围 → 直接炸掉！
}

关于数组

1
2
3
int d[1001]; // 只声明，不初始化。数组里的数是随机垃圾值，不是0！

int d[1001]{}; // 声明+全部初始化为0！数组里所有数字自动变成0，干干净净。

◆vector
vector 是 C++ 标准库提供的动态数组容器。

动态 = 你可以手动增加、删除元素，它会自动扩容。

vector<int> count(10, 0) 这一行已经完成了数组声明 + 初始化，和 C 语言的 int count[10] = {0} 等价。

写法 含义 备注
vector<int> v; 空的 int 型 vector（长度 0）
vector<int> v(10); 长度 10 的 int 型 vector，初始值为随机值
vector<int> v(10, 0); 长度 10 的 int 型 vector，初始值全 0 L1-003 个位数统计 - 团体程序设计天梯赛-练习集
vector<int> v = {1,2,3}; 长度 3 的 vector，元素为 1、2、3

访问下标为0的元素值： v[0]
获得数组长度： v.size()

1
2
3
4
5
vector<int> v; // 空的 {}
v.push_back(10); // 在最后添加元素，长度+1 {10}

vector<bool> arr(256, false); 
arr[5] = true; // 设置下标为5的元素值为true
  • nums.begin()：指向数组第一个元素
  • nums.end()：指向数组最后一个元素的后面（不指向任何元素）
  • nums.push_back()：在最后添加元素 （有参数）
  • nums.pop_back()：在最后删除元素 （无参数）
  • nums.empty()：如果空，返回true
  • *max_element(nums.begin(), nums.end()):找到数组中的最大数
  • nums.back()：数组最后一个值
  • ans.erase(ans.begin() + i)：删除下标i对应的数值
  • reverse(nums.begin(), nums.end()): 数组逆序

普通数组 < vector < string，后面的完全继承前面的功能，函数名、用法几乎全通用！

易错点：

  • C++ 不允许直接返回 vector<char> 当成 string。可以写成string(v.begin(), v.end())。
  • C++里用string可以替代char数组，无需固定长度，更安全。
1
2
3
4
5
6
7
8
9
10
// 已知该函数必须返回string类型
// 正确
string ans; 
... 
return ans;

// 错误
vector<char> ans;
...
return ans; // 但可以可改为 return string(ans.begin(), ans.end());
  • vector 是容器类型模板，不是具体类型。
1
2
3
4
5
6
7
8
9
10
vector<pair<char, int>> v;
// 错误：
for(vector p : v){
}
// 正确：
for(pair<char, int> p : v){
}
//可以直接：
for(auto& p: v){
}

◆二维数组

1
2
// 正确创建二维数组：行 = matrix[0].size()，列 = matrix.size() 
vector<vector<int>> res(matrix[0].size(), vector<int>(matrix.size()));

867. 转置矩阵 - 力扣（LeetCode）

◆数组+栈 stack
定义

1
2
3
stack<int> stk; // 定义一个栈，存 int 类型

stack<char> stk[26]; // 定义26个栈

内置函数

  • stk.push(10)：往栈顶放元素。
  • stk.pop()：删除栈顶元素。
  • stk.empty()：判断栈是不是空的。
  • stk.size()：看栈里有多少元素。
  • stk.top()：看栈顶元素

清空栈：while (!st.empty()) st.pop();

关于字符串

◆字符串
把字符数字‘1’转成数字1：str[i] - '0'
判断是否是数字：isdigit()
L1-016 查验身份证 - 团体程序设计天梯赛-练习集
(unsigned char)c把 char类型的通用字符（256个），转换成 0~255 的正整数下标，并且刚好是ASCLL值。例如(unsigned char)'a'=97 。

(unsigned char)'A' = 65
(unsigned char)'Z' = 90
(unsigned char)'a' = 97

L1-011 A-B - 团体程序设计天梯赛-练习集
709. 转换成小写字母 - 力扣（LeetCode）

统计每个字母出现的次数

1
2
3
4
5
int cnt[26] = {0}; // 26个字母计数器 下标为0-25
// 统计每个字母出现多少次 
for (char ch : s) { 
	cnt[ch - 'a']++;  // 如果ch = 'a',那么ch - 'a' = 0
	}

当要读取带空格的字符串时，注意cin >> a 遇到空格就停了，读不完整，必须用：

1
2
3
4
string a;
getline(cin, a); //读入第一行（带空格）

str.back(); //

L1-011 A-B - 团体程序设计天梯赛-练习集

字符与字符串的区别：

  • 'a' 是字符
  • "a" 是字符串

string(count, ch) 快速生成 count 个相同字符。
reverse(str.begin(), str.end()) 把字符串变为逆序。

关于指针

◆指针

哈希表

◆哈希表（字典）

key value 
1
2
3
4
5
6
7
8
unordered_map<int, int> cnt;
// 此时cnt是空的 里面什么都没有 

// 键值对 通过[]访问
if(cnt[num] == 0) unique++;  // 这里条件成立！
cnt[num]++;

cnt.erase(num); // 把num这个键在哈希表里面彻底删除

如果你用 cnt[num] 访问一个从来没出现过的数字，C++ 会自动创建这个 key，并把值初始化为 0！

unordered_map 是自动扩容的动态容器！它和 vector 不一样：

哈希表最牛的地方：查找超快。

  • 数组要找一个数，要从头遍历：O(n)

  • 哈希表找一个数，几乎瞬间找到：O (1)
    它内部用了一种叫 哈希函数 的东西，把 key 直接 “映射” 到一个位置，不用一个个找。

  • mp.find(key)：在哈希表查找有没有这个key，如果有，返回指向它的迭代器（指针），如果没有，返回 idx.end()。

  • mp.count(key)：判断是否存在

1
2
3
auto it = cnt.find(5);
//it->first           → key（你存的数字） 
//it->second          → value（你存的下标）

函数

匿名函数

1
2
3
auto f = [](string s) { ... }; // 末尾有; 用auto接收 有返回值
// 等价于
int f(string s) { ... }

功能完全一样！
只是上面那种写法更短，能直接写在别的函数里面。
1170. 比较字符串最小字母出现频次 - 力扣（LeetCode）

[&] = 引用捕获外部所有变量

  • & = 引用（不是复制，直接用外面原来的变量）
  • 所有在 check 外面定义的变量，都能直接用
1
2
3
auto check = [&](int m) -> bool { 
	// 代码 
	};

数学

基础

闰年的判别条件是：该年年份能被4整除但不能被100整除，或者能被400整除。闰年的2月有29天。

素数（质数）的定义：大于 1 的自然数，除了 1 和它本身，不能被其他自然数整除。

1
2
3
4
5
6
7
8
9
10
// 判断n是否为质数
bool is_prime(long long n) { 
	if (n < 2) return false; 
	
	// 枚举到√n即可，用long long避免i*i溢出（因为i可能会很大） 
	for (long long i = 2; i * i <= n; ++i) {
		if (n % i == 0) return false; 
	} 
	return true; 
}

L1-006 连续因子 - 团体程序设计天梯赛-练习集

因数的对称性—— 若 N 有一个因子i，则必然有一个因子N/i，且其中一个≤√N、另一个≥√N。所以只需枚举到√N即可覆盖所有可能的因子，时间复杂度从 O (N) 降到 O (√N)，这是所有因数 / 质数题的 “提速关键”。

求最大公因数 (数学 + 递归)

1
2
3
4
5
6
7
8
9
10
typedef long long ll; 

ll gcd(ll a, ll b) { 
	return b == 0 ? a : gcd(b, a % b); 
}
// a   b    t
// 6 % 12 = 6
// 12 % 6 = 0
// 6    0
// 最大公因数为6。

L1-009 N个数求和 - 团体程序设计天梯赛-练习集
263. 丑数 - 力扣（LeetCode）

向上取整：

  • 12/5 = 2.4 → 向上取整 = 3；
  • 10/5 = 2.0 → 向上取整 = 2；
  • 7/3 = 2.333 → 向上取整 = 3；
  • 0/5 = 0 → 向上取整 = 0。
    (a + b - 1) / b 实现向上取整。
取整需求 公式（整数除法） 例题
向上取整 (a + b - 1) / b 码蹄集OJ-小码哥的魔法实战1
向下取整 a / b
四舍五入 (a + b/2) / b

圆周长：C=2πr；面积：S=πr2；直径：d=2r
球体表面积：S=4*π*r^2；体积：V=3/4​*π*r^3

排序
sort()默认从小到大

1
2
3
4
5
int a[5] = {3,1,4,2,5}; 
sort(a, a + 5); // [起始地址, 结束地址后一位] // 结果：1 2 3 4 5

vector<int> v = {2,4,6,2,1,1}
sort(v.begin(), v,end());

从大到小

1
2
vector<int> v = {3,1,4}; 
sort(v.begin(), v.end(), greater<int>()); // 结果：4 3 1

L1-010 比较大小 - 团体程序设计天梯赛-练习集

二分查找 O (log n)
852. 山脉数组的峰顶索引 - 力扣（LeetCode）

逆向思维
1423. 可获得的最大点数 - 力扣（LeetCode）

余数取正
t = (x % k + k) % k

字典序：从左往右，一位一位比，谁先出现更小的字母，谁整体就更小。
aab 和 aba 的字典序比较：
第 1 位，aab → a，aba → a，一样，继续比下一位。
第 2 位，aab → a，aba → b，a < b，后面全部不用看了。
aab < aba

二进制与位运算

两大类：逻辑位运算符、位移运算符

位与& 二进制 同1异0
位或| 都为0才是0 其他全为1
异或^ 同0异1
按位取反 ~ 转化为二进制再取反

左移x<<y x转化为二进制，左移y位，末尾补0
右移x>>y x非负数，高位补0；x负数，高位补1。

C 语言中运算符的优先级： ==（相等判断） > &（按位与） > &&（逻辑与）

异或 （同0异1）

滑动窗口

【算法题单】滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）力扣（LeetCode）

定长窗口

定长滑动窗口就是一个固定长度的小框框，在字符串上从左往右滑。
每滑一步，去掉左边出去的字符，加上右边进来的字符。

关键字：长度为k的子数组

例题：643. 子数组最大平均数 I - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) {
        double sum = 0;
        for(int i=0;i<k;i++){ // 先算第一个窗口
            sum += nums[i];
        }
        double max_sum = sum;

        for(int i=k;i<nums.size();i++){  // 开始滑动窗口
            sum = sum + nums[i] - nums[i-k];  // 关键步骤！
            max_sum = max(max_sum, sum);
        }
        return max_sum / k;
    }
};

不定长窗口

不定长窗口：长度会变

  • 满足条件 → 扩大右边界（拉长窗口）
  • 不满足条件 → 移动左边界（缩小窗口）
    最终找：满足条件的最长窗口长度

关键词：求最长子数组，求最短子数组，求子数组个数。

例题1(求最大窗口)：3. 无重复字符的最长子串 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<int, int> mp;
        int length = 0;
        int max_length = 0;
        int left = 0;
        for(int right=0;right<s.size();right++){
            mp[s[right]]++;
            length++;
            while(mp[s[right]] > 1){ // 核心：不满足条件就左移
                mp[s[left]]--;
                left++;
                length--;
            }
            max_length = max(length, max_length); // 注意这一行的位置
        }
        return max_length;
    }
};

思维转换：给你一个二进制数组 nums ，你需要从中删掉一个元素。
请你在删掉元素的结果数组中，返回最长的且只包含 1 的非空子数组的长度。
如果不存在这样的子数组，请返回 0 。

输入：nums =[0,1,1,1,0,1,1,0,1]
输出：5
解释: 删掉位置 4 的数字后，[0,1,1,1,1,1,0,1] 的最长全 1 子数组为[1,1,1,1,1] 。

思路: 窗口里面最多1个0, 返回长度-1.

例题2(求最短窗口)：209. 长度最小的子数组 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int sum = 0;
        int left = 0;
        int min_length = INT_MAX;
        // 特殊情况
        for(int i=0;i<nums.size();i++){
            sum += nums[i];
        }
        if(sum < target) return 0;
        
        sum = 0;
        for(int right=0;right<nums.size();right++){
            sum += nums[right];
            while(sum >= target){ // 核心：满足条件左移，缩到不满足条件前更新
                min_length = min(min_length, right - left + 1); // 注意这行的位置
                sum -= nums[left];
                left++;
            }
        }
        return min_length;
    }
};

二分查找

分享丨【算法题单】二分算法（二分答案/最小化最大值/最大化最小值/第K小） - 讨论 - 力扣（LeetCode）

二分查找时间复杂度：O(logn)
普通逐个遍历：O(n)，二分查找吊打线性查找。在有序区间上，每次排除一半不可能的答案，。

基础查找

核心算法（闭区间写法）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int lowerBound(vector<int>& nums, int target){
        int left = 0;
        int right = nums.size() - 1; // 最右边数的下标
        while(left <= right){
            int mid = left + (right - left) / 2; // 注意写法 防止直接相加带来的溢出！

            if(nums[mid] >= target){
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        return left; // 返回第一个>=target的数的下标
    }
    // ------最终效果--------
    //  right      left
    // <target    >=target

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

1
2
3
4
5
6
7
vector<int> searchRange(vector<int>& nums, int target) {
        int left = lowerBound(nums, target);
        // 注意 要先判断left大小 再判断nums[left] 否则程序会崩溃！！！
        if(left >= nums.size() || nums[left] != target) return {-1, -1}; // 如果所有数都小于target，那么此时left=nums.size() 
        int right = lowerBound(nums, target+1) - 1;
        return {left, right};
    }

使用lower_bound内置函数：

1
2
3
lower_bound(arr2.begin(), arr2.end(), target);
lower_bound(arr2, target);
// 返回vector类型
1
2
3
4
5
6
7
8
9
10
11
vector<int> searchRange(vector<int>& nums, int target) {
		//使用内置函数
        auto left = lower_bound(nums.begin(), nums.end(), target);
        // left是vector类型 是指针 是地址
        if(left == nums.end() || *left != target) return {-1, -1};
        auto right = lower_bound(nums.begin(), nums.end(), target+1) - 1;
        return {
             (int)(left - nums.begin()),
             (int)(right - nums.begin())
        };
    }

部分题目需要先排序，然后在有序数组上二分查找。

二分答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    // 计算满足 check(x) == true 的最小整数 x
    int binarySearchMin(vector<int>& nums) {
        // 二分猜答案：判断 mid 是否满足题目要求
        auto check = [&](int mid) -> bool {
            
        };

        int left = ; // 循环不变量：check(left) 恒为 false
        int right = ; // 循环不变量：check(right) 恒为 true
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if(check(mid)){
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        return left;
    }
};

例题：1283. 使结果不超过阈值的最小除数 - 力扣（LeetCode）

数据结构

枚举

枚举右，维护左：对于双变量问题，例如两数之和a+b=target，可以枚举右边的数 ，转换成单变量问题，也就是在左边查找是否有a=target-b，这可以用哈希表维护。

枚举+哈希表

例题：1. 两数之和 - 力扣（LeetCode）
思路：遍历数组，用哈希表存已经看过的数字，每到一个新数字nums[i]，就去哈希表里查有没有数字等于target - nums[i]，有 → 直接返回答案！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 哈希表 枚举
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> mp;
        for(int i=0;;i++){
            auto it = mp.find(target - nums[i]); //.find()返回迭代器，所以用auto
            if(it != mp.end()){ // 找到了
                return {it->second,i};
            }
            mp[nums[i]] = i;
        }
    }
};
// 我们要查的是：数字是否存在
// 找到后要拿：数字对应的下标
// 所以这里必须：key = 数字，value = 下标

买卖股票

最佳时机: 买卖股票的最佳时机是由之前买或不买的状态决定的，而之前买或不买又由更早的状态决定的…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 枚举 
// 贪心：一边遍历，一边记录历史极值，一边算当前最优
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int minprice = int(1e9); // 历史最低价格 起初设大
        int maxprofit = 0;       // 历史最大利润 起初设小一点
        for (auto price : prices){
	        //-------------------------------------------
	        // 当前最大利润 = 当前价格 - 历史最低价
            maxprofit = max(maxprofit, price - minprice);
            // 更新历史最低价
            minprice = min(minprice, price);
            //-------------------------------------------
        }
        return maxprofit;
    }
};

遍历每一天：
假设今天卖出，用前面所有天里最便宜的价格买入。
更新最大利润。
再把今天价格纳入，作为以后可以买入的最低价。
必须先算利润，再更新最低价！

前缀和

通过前缀和，我们可以把子数组的元素和转化成两个前缀和的差。

1
2
3
4
5
nums[1,0,2,5,0,2,1]
s[0,1,1,3,8,8,10,11]

nums数组下标4到6的数字之和 = s[7] - s[4]
即 s[right+1] - s[left]

前缀和+哈希表

例题：560. 和为 K 的子数组 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> s(n+1); //前缀和数组 s[0]=0
        for(int i=0;i<n;i++){
            s[i+1] = s[i] + nums[i];
        } 
          
        unordered_map<int, int> mp;
        int ans = 0;
        
        //遍历前缀和数组
        for(int i=0;i<n+1;i++){ 
            auto it = mp.find(s[i] - k);
            if(it != mp.end()){ //找到啦
                ans += it->second;
            }
            mp[s[i]]++;
        }
        return ans;
    }
};

二维前缀和

1
2
3
图形理解：sum[i+1][j+1] = 左边矩形和 + 上边矩形和 - 重叠部分 + 当前格子的值

代码：sum[i+1][j+1] = sum[i+1][j] + sum[i][j+1] - sum[i][j] + matrix[i][j];

例题：304. 二维区域和检索 - 矩阵不可变 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class NumMatrix {
    vector<vector<int>> sum;  // 前缀和数组
public:
    NumMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size();    // 行数
        int n = matrix[0].size(); // 列数
        
        // 开一个(m+1) × (n+1)的数组，全部初始化为0
        sum.resize(m + 1, vector<int>(n + 1));
        
        // 遍历二维数组 计算前缀和数组
        for (int i=0;i<m;i++){
            for (int j=0;j<n;j++){
                sum[i+1][j+1]=sum[i+1][j]+sum[i][j+1]-sum[i][j]+matrix[i][j];
            }
        }
    }

差分

一维差分

原数组 arr = [1,3,3,5,8]

差分数组 d = [1,2,0,2,3]
前缀和 s = [1,3,3,5,8] = arr

把连续子数组arr[1],arr[2],arr[3]都加上10 brr = [1,13,13,15,8]
此时的差分数组[1, 12(+10), 0, 2, -7(-10)]
此时连续子数组的操作就转变成对差分数组d中两个数的操作。

对原数组 a 做「区间 [i, j] 全部 +1」的操作，等价于在差分数组 d 里只改两个位置：
d[i] += 1
d[j+1] -= 1

例题：1094. 拼车 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        int d[1001]{}; // 差分数组

        for(auto&t : trips){ // 更新差分
            int num = t[0];
            int from = t[1];
            int to = t[2];

            d[from] += num;
            d[to] -=num;
        }
        // 前缀和计算 获得每一刻的人数
        int s = 0;
        for(int a: d){
            s += a;
            if(s > capacity) return false;
        }
        return true;
    }
};

二维差分

栈

基础

vector：
进：push_back ()
出：pop_back ()
查非空：!ans.empty ()
拿最后一个值：back()

stack:
进：push ()
出：pop()
查非空：!stk.empty ()
拿最后一个值：top()

例题1：2390. 从字符串中移除星号 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    string removeStars(string s) {
        string ans; // 新建答案数组 也可以用stack<char> ans;
        for(int i =0;i<s.size();i++){
            if(s[i] == '*'){
                if(!ans.empty()){ // 一定要先检查是否空
                    ans.pop_back(); // 出栈
                }
            }else{
                ans.push_back(s[i]); // 入栈
            }
        }
        return ans; 
        // return string(ans.begin(), ans.end());
    }
};

更简洁：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    string removeStars(string s) {
        string st;
        for (char c : s) {
            if (c == '*') {
                if (!st.empty()) {  
					st.pop_back();
				}
            } else {
                st += c; // 这样写也可以，入栈
            }
        }
        return st;
    }
};

邻项消除

◆两个字符匹配消除的思路：新建一个栈，遍历原数组，把栈顶元素与当前的遍历值作比较，如果匹配，Pop栈顶元素。

2696. 删除子串后的字符串最小长度 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int minLength(string s) {
        stack<char> stk;
        for(char t: s){
            if(!stk.empty() && ((stk.top() == 'A' && t == 'B') || (stk.top() == 'C' && t == 'D'))){
                stk.pop(); // 出栈
            }
            else{
                stk.push(t); // 入栈
            }
        }
        return stk.size();
    }
};

◆两个字符匹配合并的思路：先匹配，匹配成功后Pop栈顶元素。在这之前更新当前的遍历值为合并的和，进入循环，不断合并，最后入栈。

例题：3834. 合并相邻且相等的元素 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<long long> mergeAdjacent(vector<int>& nums) {
        vector<long long> ans;
        for(long long a: nums){
            while(!ans.empty() && a == ans.back()){
                a = a + ans.back(); // 和
                ans.pop_back(); // 出栈
            }
            ans.push_back(a); // 入栈：合并后的和 / nums
        }
        return ans;
    }
};

◆k个相同字符匹配消除
为方便知道能否消除，栈中不能只存字符，还要存字符连续出现的次数。
string(count, ch)：快速生成 count 个相同字符。

例题1：1209. 删除字符串中的所有相邻重复项 II - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    string removeDuplicates(string s, int k) {
        stack<pair<char, int>> stk; // 栈里面存一对数据[字符，出现次数]
        for(char a: s){
            if(!stk.empty() && stk.top().first == a){
                auto[ch, count] = stk.top();
                stk.pop(); // 出栈
                count++;
                if(count == k) continue;
                stk.push({ch, count}); // 入栈
            }else{
                stk.push({a, 1}); // 入栈 新字符
            }
        }
        // stk所有的ch转成string
        string ans;
        while(!stk.empty()){
            auto[ch, count] = stk.top();
            stk.pop(); // 出栈
            ans += string(count, ch);
        }
        reverse(ans.begin(), ans.end()); // 栈是倒序
        return ans;
    }
};

例题2：3703. 移除K-平衡子字符串 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    string removeSubstring(string s, int k) {
        vector<pair<char, int>> v;
        for(int a: s){
            if(!v.empty() && a == v.back().first){
                // auto[ch, count] = v.back();
                // count++; // [a, count]
                v.back().second++;
            }else{
                v.push_back({a, 1}); // 入栈（新符号）
            }
            if(a == ')' && v.size() >= 2 && v.back().second == k && v[v.size()-2].second >= k){
                v.pop_back(); // 出栈 [')', k]
                v.back().second -= k; // 修改 ['(', count-k]
                if(v.back().second == 0){
                    v.pop_back(); // 出栈 ['(', k]
                }
            }
        }
        string ans;
        for(auto& p: v){ // ✅遍历容器一律写 auto&
            ans += string(p.second, p.first);
        }
        return ans;
    }

};

思考：

  1. 什么时候用 vector 当栈？
    stack<>只能访问栈顶 v.top()。
    vector<>可以通过下标访问任意位置（栈顶、倒数第二个、倒数第三个…）。

  2. auto [ch, count] = v.back()什么意思?
    把栈里的数据拷贝一份给 ch 和 count。所以上面注释里面的count++是改的临时数据，而不是栈里面存放的数据。
    v.back() 是栈里的真实数据。

  3. auto [ch, count] 到底是什么？
    这叫结构化绑定，快速拆开 pair。不加 & → 拷贝，加 & → 引用（改原值）

1
2
3
4
5
pair<char, int> p = {'a', 5}; 
auto [ch, count] = p; 
// 等价于： 
char ch = p.first; 
int count = p.second;
  1. 为什么入栈写 push_back({a, 1})，不是 []？
    因为 {} 代表一个pair！
1
2
3
v.push_back( {a, 1} ); 
// 等价于： 
v.push_back( pair<char, int>(a, 1) );
  1. 为什么用 .first .second？能不能写成 p[0] p[1]？
    pair是一个固定结构，不是数组。
    pair、map、unordered_map都可以用first、second。

RBS

RBS-合法括号字符串

例题1：1021. 删除最外层的括号 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    string removeOuterParentheses(string s) {
        string ans;
        int count = 0;
        for(char ch: s){
            if(ch == '('){
                if(count != 0) ans += ch;
                count++;
            }else{
                count--;
                if(count != 0) ans += ch;
            }
        }
        return ans;
    }
};

这个思路相当于把同级的括号记录成相同的数字！

队列