一、队列queueFIFO先进先出。只能从一端进从另一端出不能随机访问。queue默认底层是dequeue#include queue queueint q; q.push(1); // 入队 q.pop(); // 出队不返回值 q.front(); // 队头 q.back(); // 队尾deque即double-ended queue双端队列dequeint dq; dq.push_back(1); dq.push_front(2); dq.pop_back(); dq.pop_front(); dq[0]; // 可以随机访问两端都能进出支持[]随机访问灵活程度高优先级队列本质是堆priority_queueint pq; pq.push(3); pq.push(1); pq.push(5); pq.top(); // 5最大自动排序默认大顶堆取出来的值是最值不是FIFO单调队列本质用 deque 手动维护“单调性”eg:滑动窗口最大值队列不用维护窗口里所有元素只维护可能成为最大值的元素并保持从大到小。dequeint dq; for (int i 0; i nums.size(); i) { // 1. 删除队头过期元素 if (!dq.empty() dq.front() i - k) dq.pop_front(); // 2. 保持单调递减 while (!dq.empty() nums[dq.back()] nums[i]) dq.pop_back(); // 3. 入队 dq.push_back(i); // 4. 记录答案 if (i k - 1) res.push_back(nums[dq.front()]); }单调队列和优先级队列区别对比点单调队列优先级队列本质deque 手动维护堆时间复杂度O(n)O(n log n)是否有序局部有序全局有序删除任意元素O(1)滑窗❌ 很难适合场景滑动窗口动态最大最小二、堆完全二叉树排序大顶堆每个父节点 子节点小顶堆priority_queueint, vectorint, greaterint pq;三部分分别为priority_queue类型, 底层容器, 比较函数egstruct cmp { //重载括号运算符让结构体可以像函数一样被调用 bool operator()(const pairint, int lhs, const pairint, int rhs) { //返回true说明左边的优先级更低 return lhs.second rhs.second; } }; priority_queuepairint, int, vectorpairint, int, cmp pq;三、循环不变量循环不变量可以理解为在循环开始前成立每一次循环更新后仍然成立循环结束时可以用它推出答案。放到二分查找中循环不变量通常就是答案一定在我当前维护的区间里。比如你定义[left, right]表示答案一定在闭区间[left, right]里面。那么在整个二分过程中你每次缩小区间时都必须保证答案仍然在 [left, right] 中这就是不变量。[left, right] 二分法框架int binarySearch(vectorint nums, int target) { int left 0; int right nums.size() - 1; // 闭区间 [left, right] while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { return mid; } else if (nums[mid] target) { left mid 1; } else { right mid - 1; } } return -1; }四、 常见数据类型的极值与表示方法1. 整型 (Integer Types)数据类型C 风格宏定义 (climits)C 风格 (limits)近似取值范围 / 具体值32位有符号整型 (int)最小值:INT_MIN最大值:INT_MAXstd::numeric_limitsint::min()std::numeric_limitsint::max()Min:-2,147,483,648 (-2^{31})Max:2,147,483,647 (2^{31}-1)64位有符号整型 (long long)最小值:LLONG_MIN最大值:LLONG_MAXstd::numeric_limitslong long::min()std::numeric_limitslong long::max()Min:-9,223,372,036,854,775,808 (-2^{63})Max:9,223,372,036,854,775,807 (2^{63}-1)32位无符号整型 (unsigned int)最小值:0最大值:UINT_MAXstd::numeric_limitsunsigned int::min()std::numeric_limitsunsigned int::max()Min:0Max:4,294,967,295 (2^{32}-1)2. 浮点型 (Floating-point Types)数据类型C 风格 (cfloat)C 风格 (limits)真实含义与数值单精度 (float)最大值FLT_MAXstd::numeric_limitsfloat::max()最大的正浮点数约 $3.4 \times 10^{38}$单精度 (float)最小正数FLT_MINstd::numeric_limitsfloat::min()注意这是最接近0的正数约 $1.17 \times 10^{-38}$不是负数单精度 (float)最低负数-FLT_MAXstd::numeric_limitsfloat::lowest()真正的负数最小值约 $-3.4 \times 10^{38}$双精度 (double)最大/最低DBL_MAX-DBL_MAXstd::numeric_limitsdouble::max()std::numeric_limitsdouble::lowest()约 $1.79 \times 10^{308}$约 $-1.79 \times 10^{308}$3. 极值用法讲解用法 1作为寻找最大/最小值的初始“垫底值”这是最常见的用法。当你要在数组或树中寻找最大值时你需要一个初始变量这个变量必须足够小这样任何实际存在的值都能把它替换掉。找最大值初始化为极小值。找最小值初始化为极大值。#include iostream #include vector #include climits int findMax(const std::vectorint nums) { int max_val INT_MIN; // 初始化为系统的最小 int确保能被数组里的真实值更新 for (int num : nums) { if (num max_val) { max_val num; } } return max_val; }用法 2图论算法中的“无穷大” (Infinity)在求最短路径如 Dijkstra 算法或最小生成树如 Prim 算法时通常需要将尚未访问的节点的距离初始化为“无穷大”。 大家通常用INT_MAX来表示无穷大。五、迭代和递归举个通俗例子迭代是“循环往复”自己在原地一圈一圈地跑直到跑完目标圈数。递归是“委托与汇报”你把任务交给下一个人下一个人再交给下下一个人直到最后一个人做完最简单的一步然后一层层把结果汇报回来。一区别1. 执行机制迭代利用特定的代码结构如for、while循环在满足条件的情况下重复执行同一块代码。递归函数自己调用自己。它包含两个阶段递推不断调用自身问题规模缩小和回归达到结束条件后带着结果一层层返回。2. 状态保存迭代变量在循环体内就地更新。你只需要维护当前的几个状态变量即可。递归每次函数调用时系统都会把当前函数的局部变量、参数和执行状态打包成一个“栈帧”压入内存的调用栈中。3. 性能与内存迭代运行速度快内存开销小因为它只在固定的内存空间内更新变量。递归运行速度相对较慢有频繁的函数调用开销内存开销大。如果递归层数过深可能会导致栈溢出Stack Overflow。4. 代码结构与可读性迭代代码相对冗长但对于线性的、简单的重复任务更直观。递归代码通常非常简洁优雅极其适合处理树形结构、图遍历或分治算法如快速排序、归并排序。二举例以二叉树的前序遍历中左右为例子1.递归遍历1确定递归函数的参数和返回值因为要打印出前序遍历节点的数值所以参数里需要传入vector来放节点的数值除了这一点就不需要再处理什么数据了也不需要有返回值所以递归函数返回类型就是void代码如下void traversal(TreeNode* cur, vectorint vec)2确定终止条件在递归的过程中如何算是递归结束了呢当然是当前遍历的节点是空了那么本层递归就要结束了所以如果当前遍历的这个节点是空就直接return代码如下if (cur NULL) return;3确定单层递归的逻辑前序遍历是中左右的顺序所以在单层递归的逻辑是要先取中节点的数值即当前节点的数值代码如下vec.push_back(cur-val); // 中 traversal(cur-left, vec); // 左 traversal(cur-right, vec); // 右整体代码如下class Solution { public: void traversal(TreeNode* cur, vectorint vec) { if (cur NULL) return; vec.push_back(cur-val); // 中 traversal(cur-left, vec); // 左 traversal(cur-right, vec); // 右 } vectorint preorderTraversal(TreeNode* root) { vectorint result; traversal(root, result); return result; } };2. 迭代遍历class Solution { public: vectorint preorderTraversal(TreeNode* root) { stackTreeNode* st; vectorint result; if (root NULL) return result; st.push(root); while (!st.empty()) { TreeNode* node st.top(); // 中 st.pop(); result.push_back(node-val); if (node-right) st.push(node-right); // 右空节点不入栈 if (node-left) st.push(node-left); // 左空节点不入栈 } return result; } };六、static 关键字1. 函数内部的 static 局部变量普通局部变量每次函数调用都会重新创建函数结束就销毁。void func() { int x 0; x; cout x endl; }调用三次func(); // 1 func(); // 1 func(); // 1因为每次调用func()x都重新变成 0。如果加上staticvoid func() { static int x 0; x; cout x endl; }调用三次func(); // 1 func(); // 2 func(); // 3原因是static int x 0;这个变量只初始化一次函数结束后不会销毁下次调用时保留上一次的值。什么时候使用函数内部 static场景 1记录函数被调用次数void printCount() { static int count 0; count; cout 函数被调用了 count 次 endl; }场景 2生成唯一编号int getId() { static int id 1000; return id; }使用cout getId() endl; // 1000 cout getId() endl; // 1001 cout getId() endl; // 10022. 全局变量前面的 static普通全局变量可以被其他.cpp文件通过extern访问。例如// a.cpp int globalValue 10;另一个文件可以这样访问// b.cpp extern int globalValue;但如果加上static// a.cpp static int globalValue 10;那么这个变量只在当前.cpp文件内部可见其他文件不能访问。什么时候使用全局 static 变量当你只希望某个变量在当前文件内部使用不想暴露给其他文件时。// database.cpp static int connectionCount 0; void connect() { connectionCount; }这样可以避免其他文件误用或修改connectionCount。不过在现代 C 中文件内部私有变量更推荐用匿名命名空间namespace { int connectionCount 0; }3. 普通函数前面的 static在.cpp文件中普通函数默认也可以被其他文件链接访问。void helper() { cout helper endl; }如果加上staticstatic void helper() { cout helper endl; }那么这个函数只在当前文件中可见。什么时候使用 static 函数当某个函数只是当前.cpp文件内部的辅助函数不希望外部调用。// sort.cpp static void swapHelper(int a, int b) { int temp a; a b; b temp; } void bubbleSort(vectorint nums) { // 内部使用 swapHelper }这里swapHelper是实现细节不应该暴露给其他文件。4. 类中的 static 成员变量普通成员变量属于每一个对象每个对象都有自己的一份。class Student { public: int age; };例如Student s1; Student s2; s1.age 18; s2.age 20;s1和s2各有自己的age。但如果是static成员变量它属于整个类而不是某个对象。class Student { public: static int count; };类外还需要定义int Student::count 0;完整例子#include iostream using namespace std; class Student { public: static int count; Student() { count; } }; int Student::count 0; int main() { Student s1; Student s2; Student s3; cout Student::count endl; // 3 }这里count不是某个学生对象自己的而是整个Student类共享的。什么时候使用 static 成员变量场景 1统计对象个数class Student { public: static int total; Student() { total; } }; int Student::total 0;场景 2所有对象共享同一个配置class Config { public: static int maxConnections; }; int Config::maxConnections 100;所有地方都可以通过Config::maxConnections来访问这个共享配置。场景 3类级别常量class Math { public: static const int MAXN 1000; };这种变量和具体对象无关而是属于整个类。5. 类中的 static 成员函数普通成员函数可以访问对象的成员变量因为它有一个隐藏的this指针。class Student { public: int age; void showAge() { cout age endl; } };但是static成员函数属于类本身不属于具体对象所以它没有this指针。class Student { public: static int count; static void showCount() { cout count endl; } }; int Student::count 0;调用方式Student::showCount();static 成员函数不能直接访问普通成员变量错误写法class Student { public: int age; static void showAge() { cout age endl; // 错误 } };原因是age属于具体对象而static函数不属于任何具体对象。正确写法class Student { public: int age; static void showAge(Student s) { cout s.age endl; } };什么时候使用 static 成员函数场景 1函数逻辑和具体对象无关class Math { public: static int add(int a, int b) { return a b; } }; int main() { cout Math::add(3, 5) endl; }这里add不需要依赖某个具体的Math对象所以适合写成static。场景 2访问 static 成员变量class Student { private: static int count; public: Student() { count; } static int getCount() { return count; } }; int Student::count 0;使用Student s1, s2; cout Student::getCount() endl; // 2七、const关键字const表示“不可修改”。1. const 修饰普通变量const int x 10;表示x初始化后不能再修改。x 20; // 错误什么时候使用 const 普通变量场景 1定义不会变化的常量const double PI 3.1415926; const int MAX_SIZE 1000;这样比直接写数字更清晰double area PI * r * r;2. const 修饰函数参数如果函数不需要修改参数就应该加const。比如void printVector(const vectorint nums) { for (int x : nums) { cout x ; } }表示函数不会修改nums。为什么常用 const 引用看这个函数void printVector(vectorint nums) { // ... }这是值传递会复制整个 vector开销比较大。改成引用void printVector(vectorint nums) { // ... }虽然不复制了但函数内部可能修改nums。最佳写法是void printVector(const vectorint nums) { // ... }它有两个优点不复制效率高不允许修改安全。3. const 修饰指针这是 C 里最容易混淆的地方。情况 1指向常量的指针const int* p;也可以写成int const* p;意思是p指向的内容不能通过p修改。int a 10; int b 20; const int* p a; *p 30; // 错误不能通过 p 修改 a p b; // 正确p 可以指向别的变量情况 2常量指针int* const p a;意思是指针本身不能改也就是p不能再指向别人。int a 10; int b 20; int* const p a; *p 30; // 正确可以修改 a p b; // 错误p 不能指向别的变量情况 3指向常量的常量指针const int* const p a;表示p 不能改*p 也不能改例子int a 10; int b 20; const int* const p a; *p 30; // 错误 p b; // 错误指针 const 判断口诀看const修饰谁const int* p;const在*左边说明指向的内容不能改。int* const p;const在*右边说明指针本身不能改。const int* const p;左边右边都有说明内容和指针都不能改。4、const 修饰成员函数在类中成员函数后面加const表示这个函数不会修改对象的成员变量。class Student { private: string name; int age; public: Student(string n, int a) : name(n), age(a) {} string getName() const { return name; } int getAge() const { return age; } };这里string getName() const表示getName()不会修改当前对象。const 成员函数不能修改成员变量class Student { private: int age; public: void changeAge() const { age 20; // 错误 } };因为函数后面有const承诺不修改对象。什么时候使用 const 成员函数只要这个成员函数只是“读取数据”不修改对象状态就应该加const。例如class Student { private: string name; int age; public: string getName() const { return name; } int getAge() const { return age; } void setAge(int a) { age a; } };这里getName() getAge()应该加const因为它们只是读取。而setAge()不能加const因为它要修改age。为什么 const 成员函数重要假设有一个函数void printStudent(const Student s) { cout s.getName() endl; }因为s是const Student所以它只能调用const成员函数。如果getName()没有加conststring getName() { return name; }那么下面会报错void printStudent(const Student s) { cout s.getName() endl; // 可能报错 }正确写法string getName() const { return name; }所以凡是只读函数建议都加const。八、static 和 const 一起使用static const 类常量class Config { public: static const int MAX_SIZE 1000; };表示MAX_SIZE属于类本身而且不能修改。使用cout Config::MAX_SIZE endl;这种适合定义类级别的常量。static 和 const 的区别总结关键字核心作用关注点static改变生命周期、作用域或归属变量存在多久、能在哪里访问、属于对象还是类const限制修改变量或对象能不能被改static const类级别常量或静态常量既共享又不可修改头文件vector - vector sort - algorithm abs - cstdlib参考代码随想录-二叉树的递归遍历gemini老师GPT老师