目录前言一、双指针二、滑动窗口三、二分算法四、前缀和五、位运算六、分治快排1. 三路划分铺垫2. 三路划分快排3. 快速选择算法七、分治归并快排和归并的区别八、链表九、哈希表十、栈十一、字符串十二、优先级队列堆十三、BFS 队列十四、BFS FloodFill十五、BFS 最短路问题十六、多源BFS问题十七、BFS 拓扑排序十八、递归 搜索 回溯前言遇见一个问题不妨先思考有没有暴力解法如果有再考虑如何在暴力解法上优化要考虑特殊情况比如是否为空、比如是否越界正难则反数据是否有序如果有序不妨考虑双指针和二分数据是否具有单调性如果有不妨考虑滑动窗口数据是否具有二段性如果有不妨考虑二分算法如果要快速求出某一段连续区间的和不妨考虑前缀和top k 问题堆排序 or 快速选择算法笔者对算法的理解还很浅显这些只是对笔者自己的提示不构成建议。常见排序算法常见排序算法的时间复杂度及其稳定性冒泡排序, O(N^2), 稳定的插入排序, O(N^2), 稳定的计数排序, O(NK), 稳定的K 为数据范围归并排序, O(N*logN), 稳定的选择排序, O(N^2), 不稳定希尔排序, O(N*logN), 不稳定堆排序, O(N*logN), 不稳定快速排序, O(N*logN), 不稳定各排序算法博客链接冒泡排序插入排序选择排序希尔排序堆排序快速排序归并排序计数排序一、双指针双指针有多种比如同向(滑动窗口) 、异向、快慢当数据有序或者存在单调性的时候不妨考虑双指针若我们可以根据某种条件将数据划分为若干个连续的区域。双指针或多指针可以通过维护不同区域的边界索引在一次遍历中就能将数据按特性归类整理到位。双指针思想并不仅局限于有序时才能使用例题283.移动零解题思路代码// 写法一 class Solution { public: void moveZeroes(vectorint nums) { int cur 0; //遍历数组左侧为已处理右侧为未处理 int des -1; //非0元素的最后一个位置左侧为非0元素右侧为0 // [非0des] [des1,cur-1] [cur, ] while(cur!nums.size()) { if(nums[cur]!0) { des; swap(nums[cur],nums[des]); } cur; } } }; // 写法二 class Solution { public: void moveZeroes(vectorint nums) { for(int cur 0,dest -1;cur nums.size();cur) { if(nums[cur]) { swap(nums[dest],nums[cur]); } } } };和为 s 的两个数解题思路代码class Solution { public: vectorint twoSum(vectorint price, int target) { int left 0; int right price.size()-1; while(left right) { if(price[left]price[right]target) { right--; } else if(price[left]price[right]target) { left; } else return {price[left],price[right]}; } // 不会走到这这一行是为了避免编译器报错 return {-1,-1}; } };15.三数之和解题思路代码class Solution { public: vectorvectorint threeSum(vectorint nums) { sort(nums.begin(),nums.end());//先排序方便使用双指针 vectorvectorint ret; for(int i 0; i nums.size(); ) { if(nums[i] 0) break; // 如果nums[i]大于0说明其后全为正数不可能再找到两数之和为其相反数的数 //[-1,0,1,2,-1,-4] int left i1; //(-1 [0,1,2,-1,-4]),left指向新区间首元素将-1摘出来后面元素作为新区间在新区间里找两个和为1的数 int right nums.size()-1; int target -nums[i];//开始时为 -1 的相反数 while(left right) { //这一部分与查找总价格为目标值的两个商品思路大致相同 if(nums[left]nums[right]target) { --right; } else if(nums[left]nums[right]target) { left; } else { //先插入然后在新区间里继续缩小区间查找保证不漏 ret.push_back({nums[left],nums[right],nums[i]}); left,right--; // 去重left和right要注意避免越界 while(left right nums[left]nums[left - 1])//新区间里下个值相同就跳过 { left; } while(left right nums[right]nums[right 1])//新区间里下个值相同就跳过 { --right; } } } // 去重i i; while(i nums.size() - 1 nums[i]nums[i - 1])//如果下个nums[i]值和之前相同也跳过也要注意避免越界 { i; } } return ret; } };二、滑动窗口滑动窗口是双指针的一种满足单调性时发现两个同向指针都可以做到不回退时就可以用滑动窗口。正确性利用单调性规避了很多没有必要的枚举行为正确性等同于暴力枚举但时间复杂度一般只有O(n)。基础步骤①定义 left0, right0②进窗口移动其中一个指针比如移动 right 让数据进窗口。③判断判断窗口内的数据是否满足条件是否需要移动 left 让 left 旧数据出窗口。④ 循环执行②和③直到right指针遍历完整个数组 / 字符串。注其中还有一步是更新结果但更新结果的时机是就题论题的有的题是进窗口时更新结果有的题是判断时更新结果有的题是判断加出窗口结束后更新结果注意解题步骤并不是最重要的最重要的是如何能分析出某一题需要使用或可以使用滑动窗口满足单调性时发现两个同向指针都可以做到不回退时就可以用滑动窗口。例题1004.最大连续1的个数III解题思想找出最长的连续子数组其中0的个数不超过k个。class Solution { public: int longestOnes(vectorint nums, int k) { int left 0,right 0,zero 0; int ret 0; while(right nums.size()) { if(nums[right]0) { zero; // 计算窗口内0的数量 } while(zero k) // 说明窗口内0的个数不符合要求 { if(nums[left]0) { --zero; } left; } // 到这说明窗口内的数据符合要求 ret max(ret,right-left1); // 更新结果 right; } return ret; } };209.长度最小的子数组三、二分算法二分不一定需要有序只要能找出一种规律使得其具有二段性即能被分成两段能淘汰其中一段就能使用。二分并非只能用在有序数组上它的核心前提其实是二段性而非 “有序” 本身。所谓 “二段性”指的是对于区间[L, R]存在一个分界点mid使得区间可以被划分为两个部分且满足 “前一部分都满足条件 A后一部分都满足条件 BA、B 互斥”。只要满足这个性质不管数组是否完全有序都可以通过判断mid的归属直接淘汰一半区间从而实现 O (log n) 的查找效率。基础模板1. 基础模板代码// 朴素二分查找模板适用于有序数组的精确查找 while (left right) { // 写法1向下取整的mid等价于 (left right) / 2 int mid left (right - left) / 2; if (/* 条件1mid位置不满足目标目标在右侧 */) { left mid 1; } else if (/* 条件2mid位置不满足目标目标在左侧 */) { right mid - 1; } else { // 找到目标值返回结果 return /* 结果值或索引 */; } }2. 向上取整mid写法常用于避免死循环的场景// 写法2向上取整的mid等价于 (left right 1) / 2 int mid left (right - left 1) / 2;两种mid写法的区别以区间[0,3]为例向下取整(0 3) / 2 1取区间偏左的中间值向上取整(0 3 1) / 2 2取区间偏右的中间值3. 关键细节说明循环条件left right表示闭区间[left, right]内还有元素未检查需要继续循环。二段性模板的核心逻辑依赖区间的二段划分通过mid的判断淘汰一半区间实现O(log n)的效率。溢出问题用left (right - left) / 2而非(left right) / 2是为了避免left right过大导致整数溢出。进阶模板例题704. 二分查找 - 力扣LeetCode34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣LeetCode35. 搜索插入位置 - 力扣LeetCode69. x 的平方根 - 力扣LeetCode852. 山脉数组的峰顶索引 - 力扣LeetCode162. 寻找峰值 - 力扣LeetCode四、前缀和作用快速求出数组中某一段连续区间的和一次前缀和时间复杂度可以达到O(1)解题过程先预处理出一个前缀和数组或矩阵根据题意使用前缀和数组或矩阵来解决问题一维前缀和#include iostream #include vector using namespace std; int main() { //获取数据 int n,m; cin n m; vectorint arr(n1); for(int i 1;i n;i) cin arr[i]; //构建前缀和数组 vectorlong long dp(n1); for(int i 1;i n;i) dp[i] dp[i-1] arr[i]; //使用前缀和数组 int l,r; while(m--) { cin l r; cout dp[r] - dp[l-1] endl; } return 0; }二维前缀和#include iostream #include vector using namespace std; int main() { //获取数据 int n 0,m 0;//行列 int q 0;// 查询次数 cin n m q; vectorvectorint arr(n1,vectorint(m1));// n1行,m1列 for(int i 1;i n;i) { for(int j 1;j m;j) { cin arr[i][j]; } } //构建前缀和矩阵 vectorvectorlong long dp(n1,vectorlong long(m1));// n1行,m1列,且要考虑防溢出 for(int i 1;i n;i) { for(int j 1;j m;j) { dp[i][j] dp[i-1][j] dp[i][j-1] arr[i][j] -dp[i-1][j-1]; } } //使用前缀和矩阵 int x1 0,y1 0,x2 0,y2 0;//坐标 while(q--) { cin x1 y1 x2 y2; cout dp[x2][y2] -dp[x1-1][y2] -dp[x2][y1-1] dp[x1-1][y1-1] endl; } return 0; }五、位运算1. 基础位运算左移0100(4) 1 1000(8)右移0100(4) 1 0010(2)~取反~0100各位翻转符号位一起变有 0 就是 00100 0011 0000|有 1 就是 10100 | 0011 0111^相同 0 不同 10100 ^ 0011 01112. 确定二进制第 x 位是 0 还是 1公式(n x) 1例子n 50101看第 1 位(0101 1) 1 0010 1 0→ 第 1 位是03. 把第 x 位改成 1公式n n | (1 x)例子n 40100把第 1 位变 10100 | (11) 0100 | 0010 0110(6)4. 把第 x 位改成 0公式n n (~(1 x))例子n 60110把第 1 位清 00110 ~(0010) 0110 1101 0100(4)5. 位图思想空间压缩例子用 1 个 int 存 32 个状态上面三条操作都是为位图操作服务的哈希表存 32 个布尔要32字节位图1 个 int4字节的 32 位分别记 0/1省 8 倍空间6. 提取最右侧的 1lowbit公式n -n-n 对n的二进制数进行先取再反加1-n的操作本质是将n的二进制数中最右侧的1的右侧部分全部变为相反1200001100-1211110100例子n 1200001100 11110100 00000100 → 十进制是 4只保留最右边那个 17. 干掉最右侧的 1公式n (n-1)n-1的操作本质上是将n二进制数的最右侧1包含1本身的右侧部分全变为相反1200001100(12-1)00001011例子n 12 00001100 00001011 1000(8)→ 最右边的 1 直接抹掉对应题位 1 的个数、汉明距离8. 位运算优先级原则能加括号就加括号反例a b c容易算错正确a (b c)强制顺序9. 异或 ^ 三大运算律a ^ 0 a例5 ^ 0 5a ^ a 0消消乐例5 ^ 5 0a ^ b ^ c a ^ (b ^ c)结合律例1^2^3 1^(2^3)对应题只出现一次的数字题目链接判定字符是否唯一class Solution { public: bool isUnique(string astr) { if(astr.size() 26) return false;//鸽巢原理 int bitmap 0; for(auto e : astr) { int tmp e - a;// e 在位图中的位置 //先判断e在位图中是否已经存在 if(((bitmap tmp) 1) 1) { return false; } //到此说明位图中e还未存在将e放入位图中即将该位置置1 bitmap | (1 tmp); } return true; } };丢失的数字两整数之和只出现一次的数字II消失的两个数字六、分治快排不了解基础快排的朋友可以先移步快速排序基础快排那篇里未提及的三路划分会在这里做讲解。这里会分三个部分引入1. 三路划分铺垫75.颜色分类解题思路class Solution { public: void sortColors(vectorint nums) { int n nums.size(); int left -1, right n, i 0; while(i right) { if(nums[i] 0) swap(nums[left], nums[i]); else if(nums[i] 1) i; else swap(nums[--right], nums[i]); } } };2. 三路划分快排基础快排在遇到数据中有大量相同元素时效率会降低三路划分可以解决这种情况。912.排序数组解题思路与颜色分类核心步骤基本类似。class Solution { public: vectorint sortArray(vectorint nums) { srand(time(NULL)); // 种随机数种子 qsort(nums, 0, nums.size() - 1); return nums; } //快排 void qsort(vectorint nums, int l, int r) { // 递归出口 if(l r) { return; } // 将数组分成3块 int key getRandom(nums, l, r); int i l, left l - 1, right r 1; // 核心操作 while(i right) { if(nums[i] key) swap(nums[left], nums[i]); else if(nums[i] key) i; else swap(nums[--right], nums[i]); } // 递归处理左右子区间中间元素都相同不用处理 // [l, left] [left 1, right - 1] [right, r] qsort(nums, l, left); qsort(nums, right, r); } // 随机选key int getRandom(vectorint nums, int left, int right) { int r rand(); return nums[r % (right - left 1) left]; } };3. 快速选择算法快速选择算法并未将数据排序只是借助三路划分将数据分成三块然后根据规则快速选择出某一部分数据。215. 数组中的第K个最大元素 - 力扣LeetCode解题思路七、分治归并不了解归并排序的朋友可以先移步归并排序912. 排序数组 - 力扣LeetCode快排和归并的区别快排是选定key将数组根据key分为两部分之后对子数组不断根据key细分归并是算出mid将数组均分为两部分对左子数组排序对右子数组排序循环快排类似二叉树的前根遍历将原数组分块将左子数组分块最后将右子数组分块归并类似二叉树的后根遍历对左子数组排序对右子数组排序最后合并左右子数组八、链表一链表常用技巧1. 画图核心原则遇到链表问题一定要画图作用直观 形象 便于我们理解指针的指向变化和节点的连接关系2. 引入虚拟头结点作用便于处理边界情况如头节点插入、删除头节点等需要特殊判断的场景方便我们对链表进行统一操作无需针对头节点做额外分支判断示意引入一个不存储实际数据的newHead节点让其next指向真正的第一个节点形成newHead → 1 → 2 → 3 → null的结构3. 不要吝啬空间大胆去定义变量比如给链表定义临时节点在操作节点时多定义几个指针变量如prev、cur、next等避免在复杂操作中丢失节点引用原则不要让链表断开说明以双向链表节点插入为例典型操作步骤需要讲究顺序容易出错导致链表断开prev-next-prev cur将原后继节点的前驱指向新节点cur-next prev-next新节点的后继指向原后继prev-next cur前驱节点的后继指向新节点cur-prev prev新节点的前驱指向前驱但如果先定义一个next将必要的节点引用保存起来再修改指针指向就不必考虑这些4. 快慢双指针应用场景判环快指针每次走两步慢指针每次走一步若相遇则存在环找链表中环的入口相遇后将一个指针重置到头部两指针同速前进再次相遇点即为环入口找链表中倒数第 n 个结点快指针先走 n 步然后快慢指针同速前进快指针到达末尾时慢指针即为目标节点二链表中的常用操作1. 创建一个新节点new基础操作申请节点内存并初始化数据域和指针域2. 尾插操作遍历链表找到最后一个节点cur指向尾节点即cur-next null将新节点链接到尾部示意cur指向尾节点尾节点的next指向新节点新节点的next指向null3. 头插重点操作操作将新节点插入到链表头部加了哨兵头结点后这一步很容易特殊应用逆序链表逐个取出原链表节点使用头插法插入到新链表中即可完成链表逆序例题2. 两数相加 - 力扣LeetCode24. 两两交换链表中的节点 - 力扣LeetCode143. 重排链表 - 力扣LeetCode23. 合并 K 个升序链表 - 力扣LeetCode25. K 个一组翻转链表 - 力扣LeetCode九、哈希表例题1. 两数之和 - 力扣LeetCode49. 字母异位词分组 - 力扣LeetCode面试题 01.02. 判定是否互为字符重排 - 力扣LeetCode217. 存在重复元素 - 力扣LeetCode219. 存在重复元素 II - 力扣LeetCode十、栈1047. 删除字符串中的所有相邻重复项 - 力扣LeetCode844. 比较含退格的字符串 - 力扣LeetCode227. 基本计算器 II - 力扣LeetCode394. 字符串解码 - 力扣LeetCode946. 验证栈序列 - 力扣LeetCode十一、字符串14. 最长公共前缀 - 力扣LeetCode5. 最长回文子串 - 力扣LeetCode67. 二进制求和 - 力扣LeetCode43. 字符串相乘 - 力扣LeetCode十二、优先级队列堆C 中的std::priority_queue是一种容器适配器提供优先队列堆的功能默认是大顶堆元素降序排列最大元素在队首。它定义在queue头文件中底层默认使用std::vector作为存储容器也可指定std::deque。特点容器适配器不直接存储元素而是封装其他容器如vector/deque。堆结构底层通过堆算法std::make_heap、std::push_heap、std::pop_heap实现优先级管理。默认大顶堆可通过自定义比较函数改为小顶堆或其他排序规则。常用接口以std::priority_queueint为例1. 构造函数构造方式说明priority_queueT默认构造大顶堆底层用vectorT。priority_queueT, Container指定底层容器如dequeT。priority_queueT, Container, Compare指定比较函数如greaterT实现小顶堆。priority_queue(InputIterator first, InputIterator last)用迭代器范围初始化。2. 成员函数函数说明时间复杂度push(const T val)插入元素val到队列自动调整堆。O(log n)emplace(Args... args)原地构造元素并插入C11 起。O(log n)pop()移除队首优先级最高元素。O(log n)top()返回队首元素的引用不删除。O(1)empty()判断队列是否为空返回bool。O(1)size()返回队列中元素个数。O(1)swap(priority_queue other)与另一个队列交换内容。O(1)1046.最后一块石头的重量class Solution { public: int lastStoneWeight(vectorint stones) { // 1.将所有石头全部放入大根堆 priority_queueint pq; for(auto st : stones) { pq.push(st); } // 2.每次取堆顶数据碰撞将碰撞后的结果再放入堆中 while(pq.size() 1) { int a pq.top(); pq.pop(); int b pq.top(); pq.pop(); if(a b)// 由于是大根堆a是大于等于b的 { pq.push(a - b); } } return pq.size() ? pq.top() : 0; } };703.数据流中的第K大元素class KthLargest { public: priority_queueint,vectorint,greaterint _heap;// 小根堆 int _k;// 小根堆的大小,主要是给add用 public: KthLargest(int k, vectorint nums) { _k k; for(auto e : nums) { _heap.push(e); if(_heap.size() _k) { _heap.pop(); } } } int add(int val) { _heap.push(val); if(_heap.size() _k) { _heap.pop(); } return _heap.top(); } }; /** * Your KthLargest object will be instantiated and called as such: * KthLargest* obj new KthLargest(k, nums); * int param_1 obj-add(val); */692. 前K个高频单词 - 力扣LeetCode295. 数据流的中位数 - 力扣LeetCode十三、BFS 队列429. N 叉树的层序遍历 - 力扣LeetCode解题思路在BFS的过程中统计每一层的元素及其个数103. 二叉树的锯齿形层序遍历 - 力扣LeetCode662. 二叉树最大宽度 - 力扣LeetCode515. 在每个树行中找最大值 - 力扣LeetCode十四、BFS FloodFill题目基本特征让寻找性质相同的联通块执行某种操作。题目图像渲染class Solution { typedef pairint,int PII; public: vectorvectorint floodFill(vectorvectorint image, int sr, int sc, int color) { int value image[sr][sc]; if(value color)//处理特殊情况 { return image; } //矩阵长宽 int m image.size(); int n image[0].size(); //坐标数组,方便快速遍历 int dx[4] {0,0,1,-1}; int dy[4] {1,-1,0,0}; queuePII q;// 存符合条件需要改色的位置的坐标 q.push({sr,sc}); while(!q.empty()) { //改色 auto [a,b] q.front(); image[a][b] color; q.pop(); //遍历 for(int i 0;i 4;i) { int x a dx[i]; int y b dy[i]; if(x 0 x m y 0 y n image[x][y] value) { q.push({x,y}); } } } return image; } };岛屿数量class Solution { public: //坐标数组 int dx[4] {0,0,1,-1}; int dy[4] {1,-1,0,0}; //bool类型的数组用于标记岛屿是否被遍历过 bool vis[301][301]; public: int numIslands(vectorvectorchar grid) { int ret 0; int m grid.size();//矩阵高 int n grid[0].size();//矩阵宽 for(int i 0;i m;i) { for(int j 0;j n;j) { if(grid[i][j] 1 !vis[i][j]) { ret; bfs(grid,i,j,m,n); } } } return ret; } void bfs(vectorvectorchar _grid,int i,int j,int m,int n) { queuepairint,int q;//存岛屿坐标 q.push({i,j}); while(!q.empty()) { auto [a,b] q.front(); q.pop(); for(int k 0;k 4;k) { int x a dx[k]; int y b dy[k]; if(x 0 x m y 0 y n _grid[x][y] 1 !vis[x][y]) { q.push({x,y}); vis[x][y] true; } } } } };岛屿的最大面积被围绕的区域十五、BFS 最短路问题例题1926. 迷宫中离入口最近的出口 - 力扣LeetCode433. 最小基因变化 - 力扣LeetCode127. 单词接龙 - 力扣LeetCode675. 为高尔夫比赛砍树 - 力扣LeetCode十六、多源BFS问题例题542. 01 矩阵 - 力扣LeetCode解题思路1020. 飞地的数量 - 力扣LeetCode1765. 地图中的最高点 - 力扣LeetCode1162. 地图分析 - 力扣LeetCode十七、BFS 拓扑排序拓扑排序的前提条件图必须是有向无环图DAG。如果图中有环则无法进行拓扑排序。常见概念1.有向无环图DAG图有向边是有方向的无环选择一个起点出发顺着箭头走不能回到起点出度有多少条边是从该节点出发比如1号的出度为22号的出度为1入度有多少条边指向该节点比如1号的入度为02号的入度为22. AOV 网顶点活动图AOV 网是一种用图来描述工程或项目活动之间依赖关系的模型顶点Vertex表示一个活动或任务。有向边Edge表示活动之间的先后顺序或依赖关系。例如若存在边 A → B则表示活动 A 必须在活动 B 之前完成即 B 依赖于 A。3. 什么是拓扑排序拓扑排序是对有向无环图DAG的节点进行线性排序的一种算法。目的找到做事情的先后顺序确保对于图中的每一条有向边u → v节点u在排序结果中总是位于节点v的前面即事件 v 必须要在事件 u 之后才能执行。结果不唯一一个 DAG 可能存在多种合法的拓扑排序序列。比如我想打手柄游戏其步骤可以是先连接手柄再打开游戏最后开始玩游戏也可以是先打开游戏再连接手柄最后开始玩游戏但无论哪种顺序想开始玩游戏都必须先执行前面两个动作。3.1 拓扑排序的思想遵循先完成没有前置依赖的任务这一规则取出入度为 0 的节点将其输出这些节点没有前置依赖可以立即执行。删除与该节点相连的所有边相当于完成该任务后解除后续任务的依赖。重复步骤 1 和 2直到图中没有节点或者找不到入度为 0 的节点为止。注意如果在某一步发现图中还有节点但不存在入度为 0 的节点说明图中存在环无法进行拓扑排序因为环中每个点的入度至少为1无法进行上面的第一步重要应用判断有向图中是否存在环如果拓扑排序能成功输出所有节点则无环反之则有环。4. 如何实现拓扑排序例题207. 课程表 - 力扣LeetCode解题思路如何建图1. 如何存连接关系即如何存边邻接矩阵二维数组空间复杂度为O(V²)当节点数多时非常浪费空间。邻接表链表/动态数组空间复杂度为O(V E)只存实际存在的边空间效率高。结论绝大多数情况下直接使用「邻接表」即可无需纠结稠密稀疏。邻接表的两种代码实现方式方式 1使用vectorvectorInteger有局限方式 2使用unordered_mapInteger, ListInteger更万能一些2. 如何统计入度拓扑排序等算法需要知道每个节点有多少条边进入它入度。方法使用一个 int 数组直接记录210. 课程表 II - 力扣LeetCodeLCR 114. 火星词典 - 力扣LeetCode十八、递归 搜索 回溯感谢阅读本文如有错漏之处烦请斧正。
【算法】常见基础算法
目录前言一、双指针二、滑动窗口三、二分算法四、前缀和五、位运算六、分治快排1. 三路划分铺垫2. 三路划分快排3. 快速选择算法七、分治归并快排和归并的区别八、链表九、哈希表十、栈十一、字符串十二、优先级队列堆十三、BFS 队列十四、BFS FloodFill十五、BFS 最短路问题十六、多源BFS问题十七、BFS 拓扑排序十八、递归 搜索 回溯前言遇见一个问题不妨先思考有没有暴力解法如果有再考虑如何在暴力解法上优化要考虑特殊情况比如是否为空、比如是否越界正难则反数据是否有序如果有序不妨考虑双指针和二分数据是否具有单调性如果有不妨考虑滑动窗口数据是否具有二段性如果有不妨考虑二分算法如果要快速求出某一段连续区间的和不妨考虑前缀和top k 问题堆排序 or 快速选择算法笔者对算法的理解还很浅显这些只是对笔者自己的提示不构成建议。常见排序算法常见排序算法的时间复杂度及其稳定性冒泡排序, O(N^2), 稳定的插入排序, O(N^2), 稳定的计数排序, O(NK), 稳定的K 为数据范围归并排序, O(N*logN), 稳定的选择排序, O(N^2), 不稳定希尔排序, O(N*logN), 不稳定堆排序, O(N*logN), 不稳定快速排序, O(N*logN), 不稳定各排序算法博客链接冒泡排序插入排序选择排序希尔排序堆排序快速排序归并排序计数排序一、双指针双指针有多种比如同向(滑动窗口) 、异向、快慢当数据有序或者存在单调性的时候不妨考虑双指针若我们可以根据某种条件将数据划分为若干个连续的区域。双指针或多指针可以通过维护不同区域的边界索引在一次遍历中就能将数据按特性归类整理到位。双指针思想并不仅局限于有序时才能使用例题283.移动零解题思路代码// 写法一 class Solution { public: void moveZeroes(vectorint nums) { int cur 0; //遍历数组左侧为已处理右侧为未处理 int des -1; //非0元素的最后一个位置左侧为非0元素右侧为0 // [非0des] [des1,cur-1] [cur, ] while(cur!nums.size()) { if(nums[cur]!0) { des; swap(nums[cur],nums[des]); } cur; } } }; // 写法二 class Solution { public: void moveZeroes(vectorint nums) { for(int cur 0,dest -1;cur nums.size();cur) { if(nums[cur]) { swap(nums[dest],nums[cur]); } } } };和为 s 的两个数解题思路代码class Solution { public: vectorint twoSum(vectorint price, int target) { int left 0; int right price.size()-1; while(left right) { if(price[left]price[right]target) { right--; } else if(price[left]price[right]target) { left; } else return {price[left],price[right]}; } // 不会走到这这一行是为了避免编译器报错 return {-1,-1}; } };15.三数之和解题思路代码class Solution { public: vectorvectorint threeSum(vectorint nums) { sort(nums.begin(),nums.end());//先排序方便使用双指针 vectorvectorint ret; for(int i 0; i nums.size(); ) { if(nums[i] 0) break; // 如果nums[i]大于0说明其后全为正数不可能再找到两数之和为其相反数的数 //[-1,0,1,2,-1,-4] int left i1; //(-1 [0,1,2,-1,-4]),left指向新区间首元素将-1摘出来后面元素作为新区间在新区间里找两个和为1的数 int right nums.size()-1; int target -nums[i];//开始时为 -1 的相反数 while(left right) { //这一部分与查找总价格为目标值的两个商品思路大致相同 if(nums[left]nums[right]target) { --right; } else if(nums[left]nums[right]target) { left; } else { //先插入然后在新区间里继续缩小区间查找保证不漏 ret.push_back({nums[left],nums[right],nums[i]}); left,right--; // 去重left和right要注意避免越界 while(left right nums[left]nums[left - 1])//新区间里下个值相同就跳过 { left; } while(left right nums[right]nums[right 1])//新区间里下个值相同就跳过 { --right; } } } // 去重i i; while(i nums.size() - 1 nums[i]nums[i - 1])//如果下个nums[i]值和之前相同也跳过也要注意避免越界 { i; } } return ret; } };二、滑动窗口滑动窗口是双指针的一种满足单调性时发现两个同向指针都可以做到不回退时就可以用滑动窗口。正确性利用单调性规避了很多没有必要的枚举行为正确性等同于暴力枚举但时间复杂度一般只有O(n)。基础步骤①定义 left0, right0②进窗口移动其中一个指针比如移动 right 让数据进窗口。③判断判断窗口内的数据是否满足条件是否需要移动 left 让 left 旧数据出窗口。④ 循环执行②和③直到right指针遍历完整个数组 / 字符串。注其中还有一步是更新结果但更新结果的时机是就题论题的有的题是进窗口时更新结果有的题是判断时更新结果有的题是判断加出窗口结束后更新结果注意解题步骤并不是最重要的最重要的是如何能分析出某一题需要使用或可以使用滑动窗口满足单调性时发现两个同向指针都可以做到不回退时就可以用滑动窗口。例题1004.最大连续1的个数III解题思想找出最长的连续子数组其中0的个数不超过k个。class Solution { public: int longestOnes(vectorint nums, int k) { int left 0,right 0,zero 0; int ret 0; while(right nums.size()) { if(nums[right]0) { zero; // 计算窗口内0的数量 } while(zero k) // 说明窗口内0的个数不符合要求 { if(nums[left]0) { --zero; } left; } // 到这说明窗口内的数据符合要求 ret max(ret,right-left1); // 更新结果 right; } return ret; } };209.长度最小的子数组三、二分算法二分不一定需要有序只要能找出一种规律使得其具有二段性即能被分成两段能淘汰其中一段就能使用。二分并非只能用在有序数组上它的核心前提其实是二段性而非 “有序” 本身。所谓 “二段性”指的是对于区间[L, R]存在一个分界点mid使得区间可以被划分为两个部分且满足 “前一部分都满足条件 A后一部分都满足条件 BA、B 互斥”。只要满足这个性质不管数组是否完全有序都可以通过判断mid的归属直接淘汰一半区间从而实现 O (log n) 的查找效率。基础模板1. 基础模板代码// 朴素二分查找模板适用于有序数组的精确查找 while (left right) { // 写法1向下取整的mid等价于 (left right) / 2 int mid left (right - left) / 2; if (/* 条件1mid位置不满足目标目标在右侧 */) { left mid 1; } else if (/* 条件2mid位置不满足目标目标在左侧 */) { right mid - 1; } else { // 找到目标值返回结果 return /* 结果值或索引 */; } }2. 向上取整mid写法常用于避免死循环的场景// 写法2向上取整的mid等价于 (left right 1) / 2 int mid left (right - left 1) / 2;两种mid写法的区别以区间[0,3]为例向下取整(0 3) / 2 1取区间偏左的中间值向上取整(0 3 1) / 2 2取区间偏右的中间值3. 关键细节说明循环条件left right表示闭区间[left, right]内还有元素未检查需要继续循环。二段性模板的核心逻辑依赖区间的二段划分通过mid的判断淘汰一半区间实现O(log n)的效率。溢出问题用left (right - left) / 2而非(left right) / 2是为了避免left right过大导致整数溢出。进阶模板例题704. 二分查找 - 力扣LeetCode34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣LeetCode35. 搜索插入位置 - 力扣LeetCode69. x 的平方根 - 力扣LeetCode852. 山脉数组的峰顶索引 - 力扣LeetCode162. 寻找峰值 - 力扣LeetCode四、前缀和作用快速求出数组中某一段连续区间的和一次前缀和时间复杂度可以达到O(1)解题过程先预处理出一个前缀和数组或矩阵根据题意使用前缀和数组或矩阵来解决问题一维前缀和#include iostream #include vector using namespace std; int main() { //获取数据 int n,m; cin n m; vectorint arr(n1); for(int i 1;i n;i) cin arr[i]; //构建前缀和数组 vectorlong long dp(n1); for(int i 1;i n;i) dp[i] dp[i-1] arr[i]; //使用前缀和数组 int l,r; while(m--) { cin l r; cout dp[r] - dp[l-1] endl; } return 0; }二维前缀和#include iostream #include vector using namespace std; int main() { //获取数据 int n 0,m 0;//行列 int q 0;// 查询次数 cin n m q; vectorvectorint arr(n1,vectorint(m1));// n1行,m1列 for(int i 1;i n;i) { for(int j 1;j m;j) { cin arr[i][j]; } } //构建前缀和矩阵 vectorvectorlong long dp(n1,vectorlong long(m1));// n1行,m1列,且要考虑防溢出 for(int i 1;i n;i) { for(int j 1;j m;j) { dp[i][j] dp[i-1][j] dp[i][j-1] arr[i][j] -dp[i-1][j-1]; } } //使用前缀和矩阵 int x1 0,y1 0,x2 0,y2 0;//坐标 while(q--) { cin x1 y1 x2 y2; cout dp[x2][y2] -dp[x1-1][y2] -dp[x2][y1-1] dp[x1-1][y1-1] endl; } return 0; }五、位运算1. 基础位运算左移0100(4) 1 1000(8)右移0100(4) 1 0010(2)~取反~0100各位翻转符号位一起变有 0 就是 00100 0011 0000|有 1 就是 10100 | 0011 0111^相同 0 不同 10100 ^ 0011 01112. 确定二进制第 x 位是 0 还是 1公式(n x) 1例子n 50101看第 1 位(0101 1) 1 0010 1 0→ 第 1 位是03. 把第 x 位改成 1公式n n | (1 x)例子n 40100把第 1 位变 10100 | (11) 0100 | 0010 0110(6)4. 把第 x 位改成 0公式n n (~(1 x))例子n 60110把第 1 位清 00110 ~(0010) 0110 1101 0100(4)5. 位图思想空间压缩例子用 1 个 int 存 32 个状态上面三条操作都是为位图操作服务的哈希表存 32 个布尔要32字节位图1 个 int4字节的 32 位分别记 0/1省 8 倍空间6. 提取最右侧的 1lowbit公式n -n-n 对n的二进制数进行先取再反加1-n的操作本质是将n的二进制数中最右侧的1的右侧部分全部变为相反1200001100-1211110100例子n 1200001100 11110100 00000100 → 十进制是 4只保留最右边那个 17. 干掉最右侧的 1公式n (n-1)n-1的操作本质上是将n二进制数的最右侧1包含1本身的右侧部分全变为相反1200001100(12-1)00001011例子n 12 00001100 00001011 1000(8)→ 最右边的 1 直接抹掉对应题位 1 的个数、汉明距离8. 位运算优先级原则能加括号就加括号反例a b c容易算错正确a (b c)强制顺序9. 异或 ^ 三大运算律a ^ 0 a例5 ^ 0 5a ^ a 0消消乐例5 ^ 5 0a ^ b ^ c a ^ (b ^ c)结合律例1^2^3 1^(2^3)对应题只出现一次的数字题目链接判定字符是否唯一class Solution { public: bool isUnique(string astr) { if(astr.size() 26) return false;//鸽巢原理 int bitmap 0; for(auto e : astr) { int tmp e - a;// e 在位图中的位置 //先判断e在位图中是否已经存在 if(((bitmap tmp) 1) 1) { return false; } //到此说明位图中e还未存在将e放入位图中即将该位置置1 bitmap | (1 tmp); } return true; } };丢失的数字两整数之和只出现一次的数字II消失的两个数字六、分治快排不了解基础快排的朋友可以先移步快速排序基础快排那篇里未提及的三路划分会在这里做讲解。这里会分三个部分引入1. 三路划分铺垫75.颜色分类解题思路class Solution { public: void sortColors(vectorint nums) { int n nums.size(); int left -1, right n, i 0; while(i right) { if(nums[i] 0) swap(nums[left], nums[i]); else if(nums[i] 1) i; else swap(nums[--right], nums[i]); } } };2. 三路划分快排基础快排在遇到数据中有大量相同元素时效率会降低三路划分可以解决这种情况。912.排序数组解题思路与颜色分类核心步骤基本类似。class Solution { public: vectorint sortArray(vectorint nums) { srand(time(NULL)); // 种随机数种子 qsort(nums, 0, nums.size() - 1); return nums; } //快排 void qsort(vectorint nums, int l, int r) { // 递归出口 if(l r) { return; } // 将数组分成3块 int key getRandom(nums, l, r); int i l, left l - 1, right r 1; // 核心操作 while(i right) { if(nums[i] key) swap(nums[left], nums[i]); else if(nums[i] key) i; else swap(nums[--right], nums[i]); } // 递归处理左右子区间中间元素都相同不用处理 // [l, left] [left 1, right - 1] [right, r] qsort(nums, l, left); qsort(nums, right, r); } // 随机选key int getRandom(vectorint nums, int left, int right) { int r rand(); return nums[r % (right - left 1) left]; } };3. 快速选择算法快速选择算法并未将数据排序只是借助三路划分将数据分成三块然后根据规则快速选择出某一部分数据。215. 数组中的第K个最大元素 - 力扣LeetCode解题思路七、分治归并不了解归并排序的朋友可以先移步归并排序912. 排序数组 - 力扣LeetCode快排和归并的区别快排是选定key将数组根据key分为两部分之后对子数组不断根据key细分归并是算出mid将数组均分为两部分对左子数组排序对右子数组排序循环快排类似二叉树的前根遍历将原数组分块将左子数组分块最后将右子数组分块归并类似二叉树的后根遍历对左子数组排序对右子数组排序最后合并左右子数组八、链表一链表常用技巧1. 画图核心原则遇到链表问题一定要画图作用直观 形象 便于我们理解指针的指向变化和节点的连接关系2. 引入虚拟头结点作用便于处理边界情况如头节点插入、删除头节点等需要特殊判断的场景方便我们对链表进行统一操作无需针对头节点做额外分支判断示意引入一个不存储实际数据的newHead节点让其next指向真正的第一个节点形成newHead → 1 → 2 → 3 → null的结构3. 不要吝啬空间大胆去定义变量比如给链表定义临时节点在操作节点时多定义几个指针变量如prev、cur、next等避免在复杂操作中丢失节点引用原则不要让链表断开说明以双向链表节点插入为例典型操作步骤需要讲究顺序容易出错导致链表断开prev-next-prev cur将原后继节点的前驱指向新节点cur-next prev-next新节点的后继指向原后继prev-next cur前驱节点的后继指向新节点cur-prev prev新节点的前驱指向前驱但如果先定义一个next将必要的节点引用保存起来再修改指针指向就不必考虑这些4. 快慢双指针应用场景判环快指针每次走两步慢指针每次走一步若相遇则存在环找链表中环的入口相遇后将一个指针重置到头部两指针同速前进再次相遇点即为环入口找链表中倒数第 n 个结点快指针先走 n 步然后快慢指针同速前进快指针到达末尾时慢指针即为目标节点二链表中的常用操作1. 创建一个新节点new基础操作申请节点内存并初始化数据域和指针域2. 尾插操作遍历链表找到最后一个节点cur指向尾节点即cur-next null将新节点链接到尾部示意cur指向尾节点尾节点的next指向新节点新节点的next指向null3. 头插重点操作操作将新节点插入到链表头部加了哨兵头结点后这一步很容易特殊应用逆序链表逐个取出原链表节点使用头插法插入到新链表中即可完成链表逆序例题2. 两数相加 - 力扣LeetCode24. 两两交换链表中的节点 - 力扣LeetCode143. 重排链表 - 力扣LeetCode23. 合并 K 个升序链表 - 力扣LeetCode25. K 个一组翻转链表 - 力扣LeetCode九、哈希表例题1. 两数之和 - 力扣LeetCode49. 字母异位词分组 - 力扣LeetCode面试题 01.02. 判定是否互为字符重排 - 力扣LeetCode217. 存在重复元素 - 力扣LeetCode219. 存在重复元素 II - 力扣LeetCode十、栈1047. 删除字符串中的所有相邻重复项 - 力扣LeetCode844. 比较含退格的字符串 - 力扣LeetCode227. 基本计算器 II - 力扣LeetCode394. 字符串解码 - 力扣LeetCode946. 验证栈序列 - 力扣LeetCode十一、字符串14. 最长公共前缀 - 力扣LeetCode5. 最长回文子串 - 力扣LeetCode67. 二进制求和 - 力扣LeetCode43. 字符串相乘 - 力扣LeetCode十二、优先级队列堆C 中的std::priority_queue是一种容器适配器提供优先队列堆的功能默认是大顶堆元素降序排列最大元素在队首。它定义在queue头文件中底层默认使用std::vector作为存储容器也可指定std::deque。特点容器适配器不直接存储元素而是封装其他容器如vector/deque。堆结构底层通过堆算法std::make_heap、std::push_heap、std::pop_heap实现优先级管理。默认大顶堆可通过自定义比较函数改为小顶堆或其他排序规则。常用接口以std::priority_queueint为例1. 构造函数构造方式说明priority_queueT默认构造大顶堆底层用vectorT。priority_queueT, Container指定底层容器如dequeT。priority_queueT, Container, Compare指定比较函数如greaterT实现小顶堆。priority_queue(InputIterator first, InputIterator last)用迭代器范围初始化。2. 成员函数函数说明时间复杂度push(const T val)插入元素val到队列自动调整堆。O(log n)emplace(Args... args)原地构造元素并插入C11 起。O(log n)pop()移除队首优先级最高元素。O(log n)top()返回队首元素的引用不删除。O(1)empty()判断队列是否为空返回bool。O(1)size()返回队列中元素个数。O(1)swap(priority_queue other)与另一个队列交换内容。O(1)1046.最后一块石头的重量class Solution { public: int lastStoneWeight(vectorint stones) { // 1.将所有石头全部放入大根堆 priority_queueint pq; for(auto st : stones) { pq.push(st); } // 2.每次取堆顶数据碰撞将碰撞后的结果再放入堆中 while(pq.size() 1) { int a pq.top(); pq.pop(); int b pq.top(); pq.pop(); if(a b)// 由于是大根堆a是大于等于b的 { pq.push(a - b); } } return pq.size() ? pq.top() : 0; } };703.数据流中的第K大元素class KthLargest { public: priority_queueint,vectorint,greaterint _heap;// 小根堆 int _k;// 小根堆的大小,主要是给add用 public: KthLargest(int k, vectorint nums) { _k k; for(auto e : nums) { _heap.push(e); if(_heap.size() _k) { _heap.pop(); } } } int add(int val) { _heap.push(val); if(_heap.size() _k) { _heap.pop(); } return _heap.top(); } }; /** * Your KthLargest object will be instantiated and called as such: * KthLargest* obj new KthLargest(k, nums); * int param_1 obj-add(val); */692. 前K个高频单词 - 力扣LeetCode295. 数据流的中位数 - 力扣LeetCode十三、BFS 队列429. N 叉树的层序遍历 - 力扣LeetCode解题思路在BFS的过程中统计每一层的元素及其个数103. 二叉树的锯齿形层序遍历 - 力扣LeetCode662. 二叉树最大宽度 - 力扣LeetCode515. 在每个树行中找最大值 - 力扣LeetCode十四、BFS FloodFill题目基本特征让寻找性质相同的联通块执行某种操作。题目图像渲染class Solution { typedef pairint,int PII; public: vectorvectorint floodFill(vectorvectorint image, int sr, int sc, int color) { int value image[sr][sc]; if(value color)//处理特殊情况 { return image; } //矩阵长宽 int m image.size(); int n image[0].size(); //坐标数组,方便快速遍历 int dx[4] {0,0,1,-1}; int dy[4] {1,-1,0,0}; queuePII q;// 存符合条件需要改色的位置的坐标 q.push({sr,sc}); while(!q.empty()) { //改色 auto [a,b] q.front(); image[a][b] color; q.pop(); //遍历 for(int i 0;i 4;i) { int x a dx[i]; int y b dy[i]; if(x 0 x m y 0 y n image[x][y] value) { q.push({x,y}); } } } return image; } };岛屿数量class Solution { public: //坐标数组 int dx[4] {0,0,1,-1}; int dy[4] {1,-1,0,0}; //bool类型的数组用于标记岛屿是否被遍历过 bool vis[301][301]; public: int numIslands(vectorvectorchar grid) { int ret 0; int m grid.size();//矩阵高 int n grid[0].size();//矩阵宽 for(int i 0;i m;i) { for(int j 0;j n;j) { if(grid[i][j] 1 !vis[i][j]) { ret; bfs(grid,i,j,m,n); } } } return ret; } void bfs(vectorvectorchar _grid,int i,int j,int m,int n) { queuepairint,int q;//存岛屿坐标 q.push({i,j}); while(!q.empty()) { auto [a,b] q.front(); q.pop(); for(int k 0;k 4;k) { int x a dx[k]; int y b dy[k]; if(x 0 x m y 0 y n _grid[x][y] 1 !vis[x][y]) { q.push({x,y}); vis[x][y] true; } } } } };岛屿的最大面积被围绕的区域十五、BFS 最短路问题例题1926. 迷宫中离入口最近的出口 - 力扣LeetCode433. 最小基因变化 - 力扣LeetCode127. 单词接龙 - 力扣LeetCode675. 为高尔夫比赛砍树 - 力扣LeetCode十六、多源BFS问题例题542. 01 矩阵 - 力扣LeetCode解题思路1020. 飞地的数量 - 力扣LeetCode1765. 地图中的最高点 - 力扣LeetCode1162. 地图分析 - 力扣LeetCode十七、BFS 拓扑排序拓扑排序的前提条件图必须是有向无环图DAG。如果图中有环则无法进行拓扑排序。常见概念1.有向无环图DAG图有向边是有方向的无环选择一个起点出发顺着箭头走不能回到起点出度有多少条边是从该节点出发比如1号的出度为22号的出度为1入度有多少条边指向该节点比如1号的入度为02号的入度为22. AOV 网顶点活动图AOV 网是一种用图来描述工程或项目活动之间依赖关系的模型顶点Vertex表示一个活动或任务。有向边Edge表示活动之间的先后顺序或依赖关系。例如若存在边 A → B则表示活动 A 必须在活动 B 之前完成即 B 依赖于 A。3. 什么是拓扑排序拓扑排序是对有向无环图DAG的节点进行线性排序的一种算法。目的找到做事情的先后顺序确保对于图中的每一条有向边u → v节点u在排序结果中总是位于节点v的前面即事件 v 必须要在事件 u 之后才能执行。结果不唯一一个 DAG 可能存在多种合法的拓扑排序序列。比如我想打手柄游戏其步骤可以是先连接手柄再打开游戏最后开始玩游戏也可以是先打开游戏再连接手柄最后开始玩游戏但无论哪种顺序想开始玩游戏都必须先执行前面两个动作。3.1 拓扑排序的思想遵循先完成没有前置依赖的任务这一规则取出入度为 0 的节点将其输出这些节点没有前置依赖可以立即执行。删除与该节点相连的所有边相当于完成该任务后解除后续任务的依赖。重复步骤 1 和 2直到图中没有节点或者找不到入度为 0 的节点为止。注意如果在某一步发现图中还有节点但不存在入度为 0 的节点说明图中存在环无法进行拓扑排序因为环中每个点的入度至少为1无法进行上面的第一步重要应用判断有向图中是否存在环如果拓扑排序能成功输出所有节点则无环反之则有环。4. 如何实现拓扑排序例题207. 课程表 - 力扣LeetCode解题思路如何建图1. 如何存连接关系即如何存边邻接矩阵二维数组空间复杂度为O(V²)当节点数多时非常浪费空间。邻接表链表/动态数组空间复杂度为O(V E)只存实际存在的边空间效率高。结论绝大多数情况下直接使用「邻接表」即可无需纠结稠密稀疏。邻接表的两种代码实现方式方式 1使用vectorvectorInteger有局限方式 2使用unordered_mapInteger, ListInteger更万能一些2. 如何统计入度拓扑排序等算法需要知道每个节点有多少条边进入它入度。方法使用一个 int 数组直接记录210. 课程表 II - 力扣LeetCodeLCR 114. 火星词典 - 力扣LeetCode十八、递归 搜索 回溯感谢阅读本文如有错漏之处烦请斧正。
