算法模版（C++ 版）更新版

reference1.牛客网在线编程_算法笔面试篇_笔试模板必刷2.LeetCode 热题 100 - 学习计划 - 力扣LeetCode全球极客挚爱的技术成长平台0.前言本文志在梳理面试手撕和算法笔试中常考算法的模版题和基本实现代码便于有需要的同学自行查阅复习并会一定程度梳理一些进阶的内容算是倒逼自己学习的一种方式打牢算法基础拿下理想offer1.简单库函数数据结构1.1序列操作就一些简单的增删改查还是遇到了一些bug的比如从小到大排列的话用的是lessint(),类似于可以想象为一个排列的小于号 1 2 3从大到小就是greaterint()vector的插入是插入到指定的位置比如vector.begin(),就是插入到index 0的位置而不是插入到index 0的后面#include iostream #include vector #includealgorithm using namespace std; int main() { int ops; cin ops; vectorint seq; int x; int size ; for (int opIndex 0; opIndex ops; opIndex) { int op; cin op; //需要根据操作类型决定输入的参数 switch (op) { //正好很久没有写过switch case了 case 1: cin x; seq.emplace_back(x); //末尾添加 break; case 2: seq.pop_back(); break; case 3: int i; size seq.size(); cin i; // for(auto a : seq){ // coutsss; // couta i; // } if (i size ) { cout seq[i] endl; } else { cout Index out of scope endl; } break; case 4: int idx; cin idx x; seq.insert(seq.begin() idx1, x); break; case 5: sort(seq.begin(), seq.end(), lessint()); break; case 6: sort(seq.begin(), seq.end(), greaterint()); break; case 7: size seq.size(); cout size endl; break; case 8: for (auto s : seq) { cout s ; } cout endl; break; } } } // 64 位输出请用 printf(%lld)1.2 TODO待补充2.排序算法2.1 快速排序主要是快排其他的用库函数就行一般手撕都是让写快排就完事了。原理分区操作Partition快速排序的关键步骤是分区操作。通常选择一个基准值pivot将数组分为两部分左子数组所有元素小于或等于基准值。右子数组所有元素大于基准值。分区操作的具体实现选择基准值通常为数组的第一个元素、最后一个元素或随机元素。使用双指针i和j从数组起点开始扫描j向右移动直到找到大于基准值的元素。交换i和j指向的元素i直到j指向最后一个元素将基准值与相遇点的元素交换完成分区。递归排序分区完成后对左右子数组分别递归调用快速排序对左子数组小于基准值的部分进行快速排序。对右子数组大于基准值的部分进行快速排序。递归的终止条件是子数组的长度为0或1此时数组已经有序。代码有几个需要注意的地方1.选择初始基准需要随机化否则当数组有序的时候每次选择都是待排序的最大需要交换所有的元素复杂度退化到On^2)2.注意判断的条件得写成 nums[j] povit否则对于元素都相等的数组复杂度退化到On^2)#include iostream #include vector using namespace std; //参考这个 int partition_v2(vectorint nums,int low,int high){ int i lowrand()%(high-low1); swap(nums[high],nums[i]);//把基准值先放到最后 int povit nums[high]; i low; //1.注意开始的时候i设置为-1比较方便 for(int j low; j high; j){ //2.注意这里需要小于high因为我们选择的是high作为基准所以是不动的 if(nums[j] povit){ swap(nums[i],nums[j]); // 这一步是把所有大于基准的元素交换到小的这一边来 i; } } swap(nums[i],nums[high]); // 基准元素归位 return i; } int partition(vectorint nums,int low,int high){ int i lowrand()%(high-low1); swap(nums[high],nums[i]); int povit nums[high]; i low-1; //1.注意开始的时候i设置为-1比较方便,设置为0也是可以的不过要确定好i和交换的顺序就行以及最后返回基准值的位置 for(int j low; j high; j){ //2.注意这里需要小于high因为我们选择的是high作为基准所以是不动的 if(nums[j] povit){ i; swap(nums[i],nums[j]); // 这一步是把所有大于基准的元素交换到小的这一边来 } } swap(nums[i1],nums[high]); // 基准元素归位 return i1; } void quick_sort(vectorint nums,int low,int high){ if(low high){ int pos partition(nums,low,high); quick_sort(nums,low,pos-1); quick_sort(nums,pos1,high); } } int main() { srand(time(NULL)); int n; cinn; vectorint nums; for(int i 0; i n; i){ int a; cina; nums.emplace_back(a); } quick_sort(nums,0,n-1); for(int num : nums){ coutnum ; } } // 64 位输出请用 printf(%lld)练习题【模板】序列操作_牛客题霸_牛客网912. 排序数组 - 力扣LeetCode3.数学算法3.1判断素数原理原理很简单所有大于3的素数均可表示为6k±1如56×1-176×11可自行判断 6k2 3 4的时候必然是合数6k5本质就是6k1-1,综合一下就是6k±1代码注意关键点1.注意函数的含义是素数返回true不是返回false2.传入参数的范围看清楚是int还是long long范围不对可能因为数值溢出导致判断出错牛客上的模版题目数字范围在1~$$10^{12}$$int范围约-2.1×10⁹2.1×10⁹32位超出会溢出导致判断错误或死循环。long long范围约-9.2×10¹⁸9.2×10¹⁸64位足以容纳题目常见的10^9或更大数值3.注意循环起始数字是从5开始。可能会疑惑明明我们只需要检查i-1和i1就行为什么不从i6开始。因为num的平方根可能恰好等于i-1这时候你从i试图进入循环就会漏检这一个。比如829921911×911i从6开始倍增到912循环判断会直接跳出不会去检查i-1 911是否是因数所以要从最小的因子开始逐一检查避免漏掉因子的情况bool is_prime(long long num){ if(num 2) return false; if(num 2 || num 3) return true; if(num % 2 0 || num % 3 0) return false; for(long long i 5; i*i num; i i 6){ if(num % (i) 0 || num % (i2) 0){ return false; } } return true; }练习题判断质数_牛客题霸_牛客网3.2 快速幂原理参考灵神的题解50. Pow(x, n) - 力扣LeetCode代码需要注意的细节1.把N转成 long long当 n时−n比 32 位整数的最大值还大溢出了。可以转成 64 位整数解决。2.注意ans 初始化为1不是0double myPow(double x, int N) { long long n N; if(n 0) { n -n; x 1/x; } double ans 1.0; while(n 0){ if(n % 2 ! 0){ ans * x; } n 1; x * x; } return ans; }练习题50. Pow(x, n) - 力扣LeetCode【模板】快速幂Ⅰ ‖ 模小整数_牛客题霸_牛客网3.2组合数 TODO原理代码练习题[]原理代码练习题4.搜索/查找算法4.1 二分查找原理参考灵神的讲解-视频讲解二分查找 红蓝染色法【基础算法精讲 04】代码需要注意的地方也很简单1.mid的计算建议用leftbias的方式防止数值溢出2.注意更新方式这里求出来的是大于等于target的第一个数其中left始终维持的一个特点就是下标为left-1对应的数字是小于target的你可能会问那target直接小于nums[0]怎么办这时候其实代码最后会right一直不断减小到-1返回值是0而left -1 -1那这时候我们默认为INT_MIN这样去理解就行// 这就是找第一个大于等于index的 int lower_bound(vectorint nums, int target) { int left 0, right (int) nums.size() - 1; // 闭区间 [left, right] while (left right) { // 区间不为空 int mid left (right - left) / 2; if (nums[mid] target) left mid 1; // 范围缩小到 [mid1, right] else right mid - 1; // 范围缩小到 [left, mid-1] } return left; // 或者 right1 } //这就是找第一个大于target的index这个在处理数组中有重复数字的计数问题的时候很有用 int upper_bound(vectorlong long nums, long long target) { int l 0, r nums.size() - 1; while (l r) { int mid l (r - l) / 2; if (nums[mid] target) { l mid 1; } else { r mid - 1; } }练习题704. 二分查找 - 力扣LeetCode【模板】整数域二分_牛客题霸_牛客网5.滑动窗口1. 同向滑窗适合“子串/子数组/连续区间”问题核心是维护一个合法窗口。记法int l 0, ans 0; for (int r 0; r n; r) { // 先把 s[r] 纳入窗口 add(s[r]); while (window 不合法) { remove(s[l]); l; } ans max(ans, r - l 1); }- r 扩大窗口- l 收缩窗口- 先加右边再修窗口再更新答案你这题 3. 无重复字符的最长子串 就是这个模板。2. 对撞双指针适合“有序数组、容器、两端夹逼”问题。int l 0, r n - 1; while (l r) { if (满足条件) { // 记录答案 } if (需要变大) l; else r--; }常见题- 11 盛最多水的容器- 15 三数之和- 167 两数之和 II3. 快慢指针适合“去重、原地修改、链表环、路径追踪”。int slow 0; for (int fast 0; fast n; fast) { if (nums[fast] ! 0) { swap(nums[slow], nums[fast]); slow; } }记法- fast 探路- slow 负责落位对链表还常见- slow slow-next- fast fast-next-next最重要的通用模板思路就一句话先定义“窗口/区间/路径”的不变量再决定谁负责扩谁负责收最后在合法状态更新答案。