【刷题专栏】牛客网算法刷题记录帖（1）
本文记录刷题时候的查漏补缺，知识点比较小就简单记录，多一点的就会把题目和代码放上来结合做知识笔记，欢迎大家关注，共同探讨，专栏持续更新中……
目录
本文记录刷题时候的查漏补缺，知识点比较小就简单记录，多一点的就会把题目和代码放上来结合做知识笔记，欢迎大家关注，共同探讨，专栏持续更新中……
1.用string模拟栈
（1）size() / length()
功能：返回字符串的有效字符个数（不含末尾隐藏的'\0'）。
说明：两者功能完全一致，size()是 STL 容器通用接口，更推荐在工程中使用。
示例：string s = "hello"; s.size(); // 返回5
（2）empty()
功能：判断字符串是否为空（有效字符数为 0），返回bool值（true为空，false非空）。
说明：比size() == 0更高效，优先使用。
示例：string s; s.empty(); // 返回true
（3）clear()
功能：清空字符串的所有有效字符，清空后size()变为 0，但内存容量（capacity()）不变（不释放内存）。
示例：string s = "hello"; s.clear(); // s变为空字符串，s.size()=0
（4）front()
功能：返回字符串的第一个字符（等价于s[0]，C++11 及以上支持）。
示例：s.front(); // 返回'h'
（5）back()
功能：返回字符串的最后一个字符（等价于s[s.size()-1]，C++11 及以上支持）。
示例：s.back(); // 返回'o'
（6）push_back(char c)
功能：在字符串末尾追加一个单个字符。
示例：s.push_back('!'); // s变为"hello!"
（7）pop_back()
功能：删除字符串末尾的最后一个单个字符
说明：只能删除末尾一个字符，无法删除其他位置的字符，对应追加单个字符的push_back()。
示例：s.pop_back(); // "hello!"变回"hello。
（8）find(str/char, pos=0)
功能：从字符串的pos下标（默认从 0，即开头）开始，查找指定子串或字符，返回找到的第一个有效下标。
说明：找不到时返回string::npos（std::string的静态常量，表示无效下标，可理解为-1）。
示例：string s = "hello world"; s.find("world"); // 返回6（'w'的下标）；s.find('x'); // 返回string::npos
（9）rfind(str/char)
功能：从字符串末尾开始反向查找指定子串或字符，返回找到的最后一个有效下标，找不到返回string::npos。
示例：s.rfind('l'); // 返回9（最后一个'l'的下标）
（10）replace(pos, len, new_str)
功能：从下标pos开始，删除len个字符，然后在该位置插入new_str，完成字符串替换。
示例：s.replace(6, 5, "cpp"); // 从下标6开始删5个字符（"world"），替换为"cpp"，s变为"hello cpp"
2.ceil向上取整
3.堆
速记：priority_queue<int>ming，大根堆，ming.top(),ming.pop（），ming.push(X)
（1）核心基础：priority_queue 默认是大根堆
首先要明确，C++ STL 中的 priority_queue（优先队列）底层默认实现是大根堆（最大堆），即堆顶元素始终是整个堆中的最大值。
1. 基本定义
priority_queue<int> big_heap; // 定义一个存储int类型的大根堆，无需额外配置2. 最常用核心操作
这是堆操作中使用频率最高的5个方法
操作方法 | 功能说明 |
| 将元素 |
| 获取堆顶元素（大根堆就是最大值），仅读取不删除（时间复杂度O(1)） |
| 删除堆顶元素，删除后会自动调整堆结构，无返回值（不能直接获取被删除的元素，时间复杂度O(logn)） |
| 判空：判断堆是否为空，返回 |
| 获取堆中元素的个数，返回 |
注意：使用top()和pop()前，最好用empty()判断堆是否非空，否则堆为空时调用会触发未定义行为（程序崩溃）。
3. 大根堆完整使用示例
#include <iostream> #include <queue> // 使用 priority_queue 必须包含该头文件 using namespace std; int main() { // 1. 定义大根堆 priority_queue<int> big_heap; // 2. 插入元素（push） big_heap.push(3); big_heap.push(1); big_heap.push(5); big_heap.push(2); // 3. 查看堆大小（size） cout << "堆中元素个数：" << big_heap.size() << endl; // 输出：4 // 4. 访问堆顶元素（top）：大根堆顶是最大值5 while (!big_heap.empty()) { // 判空（empty），避免报错 cout << "当前堆顶元素：" << big_heap.top() << endl; // 5. 删除堆顶元素（pop） big_heap.pop(); } return 0; }运行结果：
堆中元素个数：4 当前堆顶元素：5 当前堆顶元素：3 当前堆顶元素：2 当前堆顶元素：1（2）常用的小根堆实现
实际开发中，小根堆（最小堆，堆顶是最小值）也非常常用，priority_queue 没有默认小根堆，需要显式配置，有两种简单方式：
方式1：指定比较函数 greater<int>（推荐，直观）
// 格式：priority_queue<元素类型, 底层容器, 比较函数> priority_queue<int, vector<int>, greater<int>> small_heap;- 底层容器默认是
vector<int>，小根堆必须显式指定，不能省略 greater<int>表示“优先弹出更小的元素”，最终形成小根堆
方式2：元素取反，用大根堆模拟小根堆（适合不想记复杂模板）
priority_queue<int> big_heap; // 插入时取反 big_heap.push(-3); big_heap.push(-1); big_heap.push(-5); // 取出时再取反，得到最小值 int min_val = -big_heap.top(); // min_val = 1小根堆使用示例
#include <iostream> #include <queue> #include <vector> using namespace std; int main() { priority_queue<int, vector<int>, greater<int>> small_heap; small_heap.push(3); small_heap.push(1); small_heap.push(5); small_heap.push(2); while (!small_heap.empty()) { cout << "当前堆顶元素：" << small_heap.top() << endl; // 依次输出1、2、3、5 small_heap.pop(); } return 0; }（3）自定义小根堆
实现自定义小根堆有两种常用方式，其中仿函数（比较器）方式灵活性更高、更推荐，先从这种方式讲起。
前提准备：定义自定义类型
首先我们先定义一个常见的自定义结构体作为示例（比如存储学生的成绩信息，要按「成绩」实现小根堆，即成绩最低的学生在堆顶）：
#include <iostream> #include <queue> #include <vector> #include <string> using namespace std; // 定义自定义类型：学生（包含学号、姓名、成绩） struct Student { int id; // 学号 string name; // 姓名 int score; // 成绩 // 构造函数：方便快速创建学生对象 Student(int i, string n, int s) : id(i), name(n), score(s) {} };方式1：自定义仿函数（比较器）【推荐，灵活无坑】
这是实现自定义堆的首选方式，核心是定义一个重载了 () 运算符的结构体/类（即仿函数），明确两个自定义对象的比较逻辑。
核心思路：
小根堆的核心是「让优先级更低（此处即成绩更小）的对象留在堆顶」，priority_queue 的比较规则是：返回 true 时，前一个对象会被放到堆的下层（优先级更低）。
因此，要实现「按成绩小根堆」，仿函数的逻辑应该是：如果 a 的成绩 > b 的成绩，返回 true（这样 a 会被放到下层，b 留在上层，最终成绩最小的在堆顶）。
完整实现代码
#include <iostream> #include <queue> #include <vector> #include <string> using namespace std; // 1. 定义自定义类型：学生 struct Student { int id; string name; int score; Student(int i, string n, int s) : id(i), name(n), score(s) {} }; // 2. 定义仿函数（比较器）：用于判断两个Student的优先级（按成绩小根堆） struct StudentScoreCmp { // 重载()运算符，参数是两个const引用（避免拷贝，提高效率） bool operator()(const Student& a, const Student& b) { // 关键逻辑：a.score > b.score 对应「成绩小根堆」 // 若要改成大根堆，只需改为 a.score < b.score return a.score > b.score; } }; int main() { // 3. 定义自定义类型的小根堆 // 模板参数：<自定义类型, 底层容器, 仿函数类型> priority_queue<Student, vector<Student>, StudentScoreCmp> student_min_heap; // 4. 插入自定义对象（push） student_min_heap.push(Student(101, "张三", 85)); student_min_heap.push(Student(102, "李四", 72)); // 成绩最低 student_min_heap.push(Student(103, "王五", 90)); student_min_heap.push(Student(104, "赵六", 78)); // 5. 遍历堆（取顶+弹出） cout << "按成绩小根堆遍历（堆顶是成绩最低的学生）：" << endl; while (!student_min_heap.empty()) { // 获取堆顶元素 const Student& top_stu = student_min_heap.top(); cout << "学号：" << top_stu.id << "，姓名：" << top_stu.name << "，成绩：" << top_stu.score << endl; // 删除堆顶元素 student_min_heap.pop(); } return 0; }运行结果（成绩从低到高输出，符合小根堆特性）
按成绩小根堆遍历（堆顶是成绩最低的学生）： 学号：102，姓名：李四，成绩：72 学号：104，姓名：赵六，成绩：78 学号：101，姓名：张三，成绩：85 学号：103，姓名：王五，成绩：90方式2：重载自定义类型的 < 运算符【有坑，需注意】
priority_queue 默认使用 less<> 仿函数，而 less<> 底层会调用对象的 < 运算符来判断优先级，因此我们可以通过重载自定义类型的 < 运算符来实现堆的排序规则。
核心思路与坑点：
priority_queue默认是大根堆，依赖a < b的判断：若a < b为true，则b优先级更高（留在堆顶）。- 要实现小根堆，需要反转
<运算符的逻辑：即当a的成绩 <b的成绩时，返回false；当a的成绩 >b的成绩时，返回true（本质和仿函数逻辑一致）。 - 注意：只能重载
<运算符，不能重载>运算符，因为priority_queue不支持默认调用>。
完整实现代码
#include <iostream> #include <queue> #include <vector> #include <string> using namespace std; // 1. 定义自定义类型：学生，并重载 < 运算符 struct Student { int id; string name; int score; Student(int i, string n, int s) : id(i), name(n), score(s) {} // 2. 重载 < 运算符，实现按成绩小根堆的逻辑 bool operator<(const Student& other) const { // 关键：反转逻辑！ // 原本 a < b 是 "a成绩 < b成绩"，现在改为 "a成绩 > b成绩" // 这样默认的 less<> 会认为「成绩小的对象优先级更高」，形成小根堆 return this->score > other.score; } }; int main() { // 3. 定义自定义类型的小根堆（无需指定仿函数，默认 less<> 即可） priority_queue<Student> student_min_heap; // 4. 插入自定义对象 student_min_heap.push(Student(101, "张三", 85)); student_min_heap.push(Student(102, "李四", 72)); student_min_heap.push(Student(103, "王五", 90)); student_min_heap.push(Student(104, "赵六", 78)); // 5. 遍历堆 cout << "按成绩小根堆遍历（重载<运算符实现）：" << endl; while (!student_min_heap.empty()) { const Student& top_stu = student_min_heap.top(); cout << "学号：" << top_stu.id << "，姓名：" << top_stu.name << "，成绩：" << top_stu.score << endl; student_min_heap.pop(); } return 0; }运行结果
和方式1完全一致，此处不再重复。
关键补充说明
- 仿函数 vs 重载
<运算符：
- 仿函数：灵活性高，支持多种排序规则（比如可以同时定义「按成绩小根堆」「按学号大根堆」两个仿函数，按需选择），不修改自定义类型本身，推荐在实际开发中使用。
- 重载
<运算符：灵活性低，一个自定义类型只能有一个<运算符重载逻辑，适合仅需一种排序规则的场景。
- 自定义类型的成员访问：如果自定义类型的成员变量是
private，需要将仿函数或priority_queue声明为友元，否则无法访问成员变量（新手可先将成员变量设为public简化操作）。 - 底层容器不可省略：自定义类型的堆（无论哪种方式），如果需要指定仿函数，底层容器（默认
vector<自定义类型>）必须显式写出，不能省略。
总结
- 自定义小根堆的核心是提供明确的比较规则，让编译器能判断两个自定义对象的优先级。
- 自定义小根堆推荐使用**仿函数（比较器）**实现，逻辑直观、灵活性高，小根堆的仿函数核心逻辑是「前一个对象的目标字段 > 后一个对象的目标字段」。
- 重载
<运算符也可实现，但需反转逻辑（目标字段this->x > other.x），且仅支持单一排序规则。 - 无论哪种实现，使用
top()和pop()前都需用empty()判空，避免程序崩溃。 - C++
priority_queue默认是大根堆，核心操作是push(X)（插入）、top()（取堆顶）、pop()（删堆顶）。 - 实用辅助操作：
empty()（判空）、size()（获取元素个数），使用top()/pop()前建议先判空。 - 小根堆两种实现：
priority_queue<int, vector<int>, greater<int>>或 元素取反+大根堆。
4.多源BFS+最短路径
我们来通过一道例题详细解释
（1）题目回顾
描述
给定一个 n × m 的网格，每个单元格包含 0（空）、1（完好苹果）、2（腐烂苹果）三种值。
腐烂的苹果每分钟会向上下左右四个方向扩散，感染相邻的完好苹果。
请计算：
- 经过多少分钟后，网格中不存在完好苹果 → 返回该时间
- 如果有苹果永远不会腐烂 → 返回
-1
示例
输入：[[2,1,1],[1,0,1],[1,1,1]]
输出：4（第4分钟所有苹果腐烂）
输入：[[2,1,0],[1,0,1],[0,0,0]]
输出：-1（右下角的苹果永远无法被感染）
（2）核心思路：多源 BFS
1. 多源 BFS 与普通 BFS 的区别
- 普通 BFS：从单个源点出发，逐层扩散，适合单一起点的最短路径问题。
- 多源 BFS：从多个源点同时出发，逐层扩散，适合多个起点同时扩散的场景（如本题中多个腐烂苹果同时感染）。
2. 本题的多源 BFS 逻辑
- 初始队列：将所有初始腐烂的苹果（值为
2的格子）加入队列，作为 BFS 的第 0 层（对应时间0）。 - 逐层扩散：每处理队列中的一层节点（当前分钟的烂苹果），时间加 1；然后将这些烂苹果的邻居（完好苹果）感染并加入队列，作为下一层节点。
- 结果判断：BFS 结束后，检查是否还有未被感染的完好苹果。若有则返回
-1，否则返回扩散的时间（层数 - 1，因为初始层是时间0）。
（3）代码逐行注释（结合多源 BFS 逻辑）
class Solution { public: // 成员变量：网格的行数、列数，四个方向的偏移量，访问标记数组 int m; // 网格的行数 int n; // 网格的列数 // 四个方向的偏移量：右、左、下、上 int dx[4] = {0, 0, 1, -1}; int dy[4] = {1, -1, 0, 0}; // 访问标记数组：标记该位置的苹果是否被感染（避免重复入队） int visited[1010][1010] = {0}; // 主函数：输入网格，返回所有苹果腐烂的时间，或-1 int rotApple(vector<vector<int>>& grid) { // 1. 初始化网格的行数和列数 m = grid.size(); n = grid[0].size(); // 2. 初始化队列：将所有初始腐烂的苹果（值为2的格子）加入队列 queue<pair<int, int>> q; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == 2) { q.push({i, j}); visited[i][j] = true; // 初始烂苹果标记为已访问（优化：原代码未写，需补充） } } } // 3. 多源BFS的层数（时间）计数 int ret = 0; // 初始时间为0（对应队列中的初始烂苹果） // 4. 开始BFS循环：处理每一层的腐烂苹果 while (!q.empty()) { int sz = q.size(); // 当前层的节点数（当前分钟要处理的烂苹果数量） ret++; // 进入下一层，时间加1（对应分钟数递增） // 处理当前层的所有节点 while (sz--) { auto [a, b] = q.front(); // 取出队首的烂苹果位置 q.pop(); // 遍历四个方向，扩散感染 for (int i = 0; i < 4; i++) { int x = a + dx[i]; // 新的x坐标 int y = b + dy[i]; // 新的y坐标 // 检查新坐标是否合法：在网格内、是完好苹果、未被感染 if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 && !visited[x][y]) { visited[x][y] = true; // 标记为已感染 q.push({x, y}); // 加入队列，作为下一层的节点（下一分钟扩散它的邻居） } } } } // 5. 检查是否还有未被感染的完好苹果 for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == 1 && !visited[i][j]) { // 存在完好苹果且未被感染，返回-1 return -1; } } } // 6. 返回时间：初始层是时间0，所以最终时间为层数-1；若没有扩散（ret=0），返回0 return ret == 0 ? 0 : ret - 1; } };（4）复杂度分析
- 时间复杂度：
O(mn)
每个格子最多入队一次、出队一次，处理每个格子的时间为 O(1)。
- 空间复杂度：
O(mn)
队列的最大长度为 mn（当所有格子都是烂苹果时），visited 数组的大小为 mn。
（5）易错点与优化
易错点
- 初始无烂苹果的情况：
若初始队列空（无烂苹果），且存在完好苹果 → 返回 -1；若无完好苹果 → 返回 0。
原代码中 ret=0 时返回 ret-1=-1，需优化为 return ret == 0 ? 0 : ret - 1。
visited数组的冗余：
可以直接修改原网格（将感染的苹果从 1 改为 2），无需额外 visited 数组，节省空间。
- 时间计算的偏移：
初始层（所有烂苹果）对应时间 0，处理完第一层后时间加 1，因此最终返回 ret-1。
优化后的代码（去掉 visited 数组）
class Solution { public: int dx[4] = {0, 0, 1, -1}; int dy[4] = {1, -1, 0, 0}; int rotApple(vector<vector<int>>& grid) { int m = grid.size(); int n = grid[0].size(); queue<pair<int, int>> q; // 初始化队列：加入所有初始烂苹果 for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == 2) { q.push({i, j}); } } } int ret = 0; while (!q.empty()) { int sz = q.size(); ret++; while (sz--) { auto [a, b] = q.front(); q.pop(); for (int i = 0; i < 4; i++) { int x = a + dx[i]; int y = b + dy[i]; // 直接修改grid标记感染，无需visited if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1) { grid[x][y] = 2; // 标记为腐烂 q.push({x, y}); } } } } // 检查是否有剩余完好苹果 for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == 1) { return -1; } } } return ret == 0 ? 0 : ret - 1; } };（6）总结
多源 BFS 是解决多个起点扩散问题的高效方法，核心是将所有源点初始加入队列，然后逐层处理。
本题中通过多源 BFS 可以准确计算所有苹果腐烂的时间，时间复杂度和空间复杂度均为 O(mn)，适合处理大规模网格（如本题中 n,m ≤ 1000）。
5.经典的约瑟夫环的问题
解法一:模拟
解法二：递推|递归|动态规划
我们来讲一下动态规划方法
dp[i]含义是当有i个小孩时候获胜的编号。这道题本质是一个简单的下表映射问题
6.链表问题
有段时间没有写过链表问题了，今天复习一下
（1） 题目回顾
这是一道正序链表模拟高精度加法的经典题，核心特征：
- 输入：两个链表，每个节点值为
0-9，整体代表一个整数（如9->3->7代表937） - 输出：两个整数相加后的结果链表（如
937+63=1000→1->0->0->0） - 约束：链表长度可达
1e6，不能转成普通整数直接计算，必须用链表模拟加法
（2） 核心解题思路
正序链表的低位在链表尾部，直接相加无法从低位开始计算，因此我们需要做反转：
- 反转输入链表：让低位（原链表的尾部）变为头部，模拟加法时可以从左到右处理
- 模拟高精度加法：逐位相加并处理进位，构建低位在前的结果链表
- 反转结果链表：将低位在前的结果恢复为正序，得到最终输出
（3）关键知识点
1. 链表反转（迭代法）
这是本题的基础操作，必须熟练掌握迭代式反转（递归法对长链表易栈溢出，不适合 1e6 长度场景），虚拟头结点很方便
用「虚拟头节点」作为锚点，遍历原链表时，逐个将节点插入到虚拟头的下一个位置，最终虚拟头的 next 就是反转后的头节点。
ListNode* re(ListNode* head){ ListNode* newhead=new ListNode(0); // 虚拟头节点，简化指针操作 ListNode* cur=head; while(cur){ ListNode* next=cur->next; // 保存当前节点的下一个节点（避免断链） cur->next=newhead->next; // 当前节点指向虚拟头的下一个节点 newhead->next=cur; // 虚拟头的下一个节点更新为当前节点 cur=next; // 移动到下一个节点 } cur=newhead->next; // 反转后的头节点 delete newhead; // 释放虚拟头节点（工程中避免内存泄漏） return cur; }2. 高精度加法模拟
因为链表长度可达 1e6，无法用普通整数存储，必须逐位相加并处理进位。
- 用
t记录进位，初始为0 - 循环条件：
cur1 || cur2 || t（只要还有节点未处理，或还有进位，就继续循环） - 逐位相加：当前位和为
t + cur1->val（如果cur1存在） + cur2->val（如果cur2存在） - 构建结果节点：当前位值为
t % 10，新的进位为t / 10 - 用「虚拟头节点」构建结果链表，避免头节点为空的判断
3. 结果链表的反转
相加后的结果链表是「低位在前」的（如 1000 相加后得到 0->0->0->1），因此需要再次反转，恢复为正序的 1->0->0->0。
（4）完整代码逐行复盘
易错点与避坑指南：
- 进位的循环条件：必须包含
t，否则最后一位的进位会丢失（如999+1=1000，最后进位1需要额外加一个节点）。 - 链表反转的指针操作：保存
cur->next避免断链，否则会丢失后续节点。 - 虚拟头节点的使用：结果链表用虚拟头可以避免头节点为空的判断，简化代码。
- 内存管理：
re函数中的虚拟头节点用完要delete，避免内存泄漏（工程场景必备，刷题平台可忽略）。 - 空链表处理：当其中一个输入链表为空时，代码仍能正常处理（
cur1或cur2为空时，仅加另一个节点的值）。
复盘收获
- 问题转化思维：正序相加困难 → 反转成逆序相加 → 再反转恢复，这种「转化」是解决链表问题的常用技巧。
- 链表反转的必要性：对于正序存储的链表操作，反转往往能简化问题（如相加、回文判断等）。
- 高精度加法的通用性：逐位相加+进位处理的逻辑，不仅适用于链表，也适用于数组模拟的大数加法。
- 虚拟头节点的价值：简化链表构建，避免头节点为空的边界判断。
