前言
本专栏文章为本人AcWing算法基础课的学习笔记，课程地址在这。如有侵权，立即删除。
课前温习
课程提要：
课上理解算法的 主要思想。
课下 背过（能写出来并调试通过即可） 模板。
提高熟练度方法：一个模板题 重复3~5次 AC通过。
一、快速排序
基本思想：分治思想
确定分界点：q[l]、q[(l+r)/2]、q[r]、随机划分。上述任意一种划分方式均可。
调整区间：使得所有小于等于x的元素在x之前，大于等于x的元素在x之后（保证x左边的数均小于等于x，x右边的数均大于等于x）。
递归处理左右两段：（将左右两段排序），处理完后，原序列就变有序。
核心模板
代码基本思路：
注：如果递归变量传的是i，则分界点一定不能选q[l]；如果递归变量传的是j，则分界点一定不能选q[r]。否则都会造成死循环。
设置两个指针i和j，分别指向区间左右两边，然后两个指针同时往中间走，如果i指向的值满足小于x则继续走，否则停下；如果j指向的值，满足大于x则继续走，否则停下；当i和j指针都停下后，然后交换i和j所指向元素的位置。直到i与j指针相遇，结束。
void quick_sort(int q[],int l,int r){
//如果当前区间只有一个数或者没有数，不用排序，直接返回
if(l>=r) return; //确定分界点，指针指向 int x=q[l+r>>1],i=l-1,j=r+1; //前后指针遍历数组 while(i<j){ do i++;while(q[i]<x); do j--;while(q[j]>x); if(i<j) swap(q[i],q[j]); } //递归处理左右两边 quick_sort(q,l,j); quick_sort(q,j+1,r); }
题目链接：785. 快速排序
1.1题目描述
给定你一个长度为 n 的整数数列。
请你使用快速排序对这个数列按照 从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行，第一行包含整数 n。
第二行包含 n 个整数（所有整数均在 1∼109 范围内），表示整个数列。
输出格式
输出共一行，包含 n 个整数，表示排好序的数列。
数据范围
1≤n≤100000
输入样例：
5 3 1 2 4 5
输出样例：
1 2 3 4 5
1.2思路分析
套用模板即可，注意细节。
1.3代码实现
#include <iostream> using namespace std; const int N=1e6+10; int n; int q[N]; void quick_sort(int q[],int l,int r){ if(l>=r) return; int x=q[l+r>>1],i=l-1,j=r+1; while(i<j){ do i++;while(q[i]<x); do j--;while(q[j]>x); if(i<j) swap(q[i],q[j]); } quick_sort(q,l,j); quick_sort(q,j+1,r); } int main(){ int n; cin>>n; for(int i=0;i<n;i++){ cin>>q[i]; } quick_sort(q,0,n-1); for(int i=0;i<n;i++){ cout<<q[i]<<" "; } return 0; }
二、归并排序
基本思想：分治思想
确定分界点：将序列从中间分成两个部分（mid=(l+r)/2）。
递归排序左右两部分。
将 左右两部分归并，将两部分合二为一。
注：排序稳定性：元素值相同在排完序之后的相对位置是否会变化。快排不稳定，归并排序稳定。
核心模板
代码基本思路：
合并方法：分别有两个指针指向两个序列的头部，比较指向元素的大小，指向元素小的将元素放进合并数组中，然后再移动已输出元素序列的指针，重复上述步骤。直至某个序列被遍历完，然后把另一个序列剩余元素添在合并数组尾部即可。
void msort(int q[],int l,int r){
//如果当前区间只有一个数或者没有数，不用排序，直接返回
if(l>=r) return ; int mid=l+r>>1; //取当前区间中点 msort(q,l,mid); //递归排序左边 msort(q,mid+1,r); //递归排序右边 //归并过程 int k=0,i=l,j=mid+1; //i和j分别指向左右两边的起点 //每次将两个指针指向的值小的元素放入结果数组 while(i<=mid&&j<=r){ if(q[i]<=q[j]) temp[k++]=q[i++]; else temp[k++]=q[j++]; } //如果某一半边没有遍历完，直接把剩余元素加到数组尾部 while(i<=mid) temp[k++]=q[i++]; while(j<=r) temp[k++]=q[j++]; //将结果数组赋值给q数组 for(i=l,j=0;i<=r;i++,j++){ q[i]=temp[j]; } }
题目链接：787. 归并排序
2.1题目描述
给定你一个长度为 n 的整数数列。
请你使用归并排序对这个数列按照 从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行，第一行包含整数 n。
第二行包含 n 个整数（所有整数均在 1∼109 范围内），表示整个数列。
输出格式
输出共一行，包含 n 个整数，表示排好序的数列。
数据范围
1≤n≤100000
输入样例：
5 3 1 2 4 5
输出样例：
1 2 3 4 5
2.2思路分析
套用模板即可，注意细节。
2.3代码实现
#include <iostream> using namespace std; const int N=1e6+10; int n; int q[N],temp[N]; void msort(int q[],int l,int r){ if(l>=r) return ; int mid=l+r>>1; msort(q,l,mid); msort(q,mid+1,r); int k=0,i=l,j=mid+1; while(i<=mid&&j<=r){ if(q[i]<=q[j]) temp[k++]=q[i++]; else temp[k++]=q[j++]; } while(i<=mid) temp[k++]=q[i++]; while(j<=r) temp[k++]=q[j++]; for(i=l,j=0;i<=r;i++,j++){ q[i]=temp[j]; } } int main(){ int n; cin>>n; for(int i=0;i<n;i++){ cin>>q[i]; } msort(q,0,n-1); for(int i=0;i<n;i++){ cout<<q[i]<<" "; } return 0; }
三、二分查找
是否具有二段性（即一半区间满足，另一半区间不满足），若具有二段性可以二分。
注：有单调性一定可以二分，没有单调性也有可能可以二分。
二分的本质：寻找满足某种性质的边界点，该性质将区间一分为二（满足或不满足，两种情况）。
做题步骤：
做题首先写一个mid，想check函数或者是一个条件，根据此条件来判断如何划分下一次二分区间，如果是l=mid，则mid后+1；如果是r=mid，则不需要+1。
整数二分
check函数：
bool check(int x){ }//x是否满足某种性质，可写为函数或直接当成条件写在if中。
模板1：
// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用： int b1(int l,int r){ while(l<r){ int mid=l+r>>1; //注意别把这条语句写到循环外，否则死循环 if(check(mid)) r=mid; else l=mid+1; } return l; }
模板2：
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用： int b2(int l,int r){ while(l<r){ int mid=l+r+1>>1; //注意别把这条语句写到循环外，否则死循环 if(check(mid)) l=mid; else r=mid-1; } return l; }
题目一
题目链接： 789. 数的范围
3.1题目描述
给定一个按照升序排列的长度为 n 的整数数组，以及 q 个查询。
对于每个查询，返回一个元素 k 的起始位置和终止位置（位置从 0 开始计数）。
如果数组中不存在该元素，则返回 -1 -1。
输入格式
第一行包含整数 n 和 q ，表示数组长度和询问个数。
第二行包含 n 个整数（均在 1∼10000 范围内），表示完整数组。
接下来 q 行，每行包含一个整数 k，表示一个询问元素。
输出格式
共 q 行，每行包含两个整数，表示所求元素的起始位置和终止位置。
如果数组中不存在该元素，则返回 -1 -1。
数据范围
1≤n≤100000 1≤q≤10000 1≤k≤10000 输入样例： 6 3 1 2 2 3 3 4
输出样例：
3 4 5 5 -1 -1
3.2思路分析
应用二分模板即可，注意细节。
3.3代码实现
#include <iostream> using namespace std; const int N=100010; int n,m; int q[N]; int main(){ cin>>n>>m; for(int i=0;i<n;i++){ cin>>q[i]; } while(m--){ int x; cin>>x; //查找左端点 int l=0,r=n-1; while(l<r){ int mid=l+r>>1; if(q[mid]>=x) r=mid; //如果满足if条件，则x在左半边区间[l,mid]中 else l=mid+1; //否则在右半边区间[mid+1,r]中 } //如果没有找到，按题目要求输出 if(q[l]!=x) cout<<"-1 -1"<<endl; else{ cout<<l<<' '; //查找右端点 int l=0,r=n-1; while(l<r){ int mid=l+r+1>>1; if(q[mid]<=x) l=mid; //如果满足if条件，则x在[mid,r]中 else r=mid-1; } cout<<l<<endl; } } return 0; }
浮点数二分
bool check(double x){ }//x是否满足某种性质，可写为函数或直接当成条件写在if中。
或
bool check(float x){ }//x是否满足某种性质，可写为函数或直接当成条件写在if中。
double b3(double l,double r){ const double eps=1e-6;//eps表示精度，取决于题目对精度的要求 while(r-l>eps){ double mid=(l+r)/2; if(check(mid)) r=mid; else l=mid; } return l; }
题目二
例：求数的平方根
注：
题目链接：
790. 数的三次方根
3.1题目描述
给定一个浮点数 n ，求它的 三次方根。
输入格式
共一行，包含一个浮点数 n。
输出格式
共一行，包含一个浮点数，表示问题的解。
注意，结果保留 6 位小数。
数据范围
−10000≤n≤10000
输入样例：
1000.00
输出样例：
10.000000
3.2思路分析
直接套用模板即可，注意细节。
3.3代码实现
待更~
四、高精度加法
用 字符串 读入数字，用数组 倒序 存储每位，方便进位。
下图来源：这里。侵删。
核心模板
//C=A+B，A>=0,B>=0 vector<int> add(vector<int>&A,vector<int>&B){ if(A.size()<B.size()) return add(B,A); vector<int> C; int t=0; for(int i=0;i<A.size();i++){ t+=A[i]; if(i<B.size()) t+=B[i]; C.push_back(t%10); t/=10; } if(t) C.push_back(t); //去除前导0 while(C.size()>1&&C.back()==0) C.pop_back(); return C; }
题目链接：791. 高精度加法
4.1题目描述
给定两个 正整数（不含前导 0），计算它们的和。
输入格式
共两行，每行包含一个整数。
输出格式
共一行，包含所求的和。
数据范围
1≤整数长度≤100000
输入样例：
12 23
输出样例：
35
4.2思路分析
模拟加法过程即可，注意细节，具体见代码注释。
4.3代码实现
#include <iostream> #include <string> #include <vector> using namespace std; vector<int> add(vector<int> &A,vector<int> &B){ vector<int> C; int t=0; //记录每次的进位 //从个位开始依次按加法原则进行模拟 for(int i=0;i<A.size()||i<B.size();i++){ //下两行t记录不进位时当前位计算结果 if(i<A.size()) t+=A[i]; if(i<B.size()) t+=B[i]; C.push_back(t%10); //将当前位进位后计算结果记入C数组中 t/=10; //记录进位 } if(t) C.push_back(1); //如果A,B均遍历完，还有进位，则在最高位补1 return C; } int main() { string a,b; vector<int> A,B; cin>>a>>b; //a,b正序读入 //逆序存储a,b每位数字 for(int i=a.size()-1;i>=0;i--){ A.push_back(a[i]-'0'); } for(int i=b.size()-1;i>=0;i--){ B.push_back(b[i]-'0'); } vector<int> C=add(A,B); //倒序存储，需倒序输出 for(int i=C.size()-1;i>=0;i--){ cout<<C[i]; } return 0; }
五、高精度减法
核心模板
//C=A-B,满足A>=B,A>=0,B>=0; vector<int> sub(vector<int>&A,vector<int>&B){ vector<int> C; for(int i=0,t=0;i<A.size(),i++){ t=A[i]-t; if(i<B.size()) t-=B[i]; C.push_back((t+10)%10); if(t<0) t=1; else t=0; } while(C.size()>1&&C.back()==0) C.pop_back(); return C; }
题目链接：792. 高精度减法
5.1题目描述
给定两个 正整数（不含前导 0），计算它们的差，计算结果可能为负数。
输入格式
共两行，每行包含一个整数。
输出格式
共一行，包含所求的差。
数据范围
1≤整数长度≤105
输入样例：
32 11
输出样例：
21
5.2思路分析
模拟减法过程即可，注意细节，具体见代码注释。
5.3代码实现
#include <iostream> #include <string> #include <vector> using namespace std; //判断是否有A>=B bool cmp(vector<int> &A,vector<int> &B){ //若A,B位数不同，直接比较位数 if(A.size()!=B.size()) return A.size()>B.size(); //如果A,B位数相同从高位开始逐位数字比较 for(int i=A.size()-1;i>=0;i--){ if(A[i]!=B[i]){ return A[i]>B[i]; } } //如果A和B相等，返回true return true; } vector<int> sub(vector<int> &A,vector<int> &B){ vector<int> C; int t=0; //判断是否需要借位 //从个位开始依次按减法原则进行模拟 //减法已保证A的长度大于等于B的长度，直接枚举A每位数字即可 for(int i=0;i<A.size();i++){ //下两行t记录不借位时当前位计算结果 t=A[i]-t; if(i<B.size()) t-=B[i]; C.push_back((t+10)%10); //将当前位借位后计算结果记入C数组中 //将t>=0（够减）和t<0（不够减）两种情况合二为一 if(t<0) t=1; //如果不够减需要借位（下次循环时就将下一位减去借位1，再计算当前位结果） else t=0; } //去除前导0 while(C.size()>1&&C.back()==0) C.pop_back(); return C; } int main() { string a,b; vector<int> A,B; cin>>a>>b; //a,b正序读入 //逆序存储a,b每位数字 for(int i=a.size()-1;i>=0;i--){ A.push_back(a[i]-'0'); } for(int i=b.size()-1;i>=0;i--){ B.push_back(b[i]-'0'); } //计算减法需保证大的数减去小的数，若数据正好符合，则直接相减，否则用大的数减去小的数，然后加负号 if(cmp(A,B)){ vector<int> C=sub(A,B); //倒序存储，需倒序输出 for(int i=C.size()-1;i>=0;i--){ cout<<C[i]; } } else{ vector<int> C=sub(B,A); cout<<"-"; //倒序存储，需倒序输出 for(int i=C.size()-1;i>=0;i--){ cout<<C[i]; } } return 0; }
六、高精度乘法(高精度乘低精度)
将低精度作为 整体 来按乘法原则计算、进位。
核心模板
//C=A*b,A>=0,b>=0 vector<int> mul(vector<int>&A,int b){ vector<int> C; int t=0; for(int i=0;i<A.size()||t;i++){ if(i<A.size()) t+=A[i]*b; C.push_back(t%10); t/=10; } while(C.size()>1&&C.back()==0) C.pop_back(); return C; }
题目链接：793. 高精度乘法
6.1题目描述
给定两个非负整数（不含前导 0） A 和 B，请你 计算 A×B 的值。
输入格式
共两行，第一行包含整数 A，第二行包含整数 B。
输出格式
共一行，包含 A×B 的值。
数据范围
1≤A的长度≤100000,0≤B≤10000
输入样例：
2 3
输出样例：
6
6.2思路分析
模拟乘法过程即可，注意 将b看做整体去乘，具体见代码注释。
6.3代码实现
#include <iostream> #include <string> #include <vector> using namespace std; vector<int> mul(vector<int> &A,int b){ vector<int> C; int t=0; //记录进位 //从个位开始依次按乘法原则进行模拟 for(int i=0;i<A.size();i++){ t+=A[i]*b; //此时t记录当前位不进位时计算结果 C.push_back(t%10); //将当前位进位后计算结果记入C数组中 t/=10; //记录进位（低位到高位权重多10） } //如果遍历完A还有进位，则在最高位添上进位（如果有多位数，直接将进位存储在了一个数组元素中和模板中多出来的进位每个数字存储在一个数组元素中一样，不影响结果） if(t) C.push_back(t); //去除前导0 while(C.size()>1&&C.back()==0) C.pop_back(); return C; } int main() { string a; int b; vector<int> A; cin>>a>>b; //a,b正序读入 //逆序存储a每位数字 for(int i=a.size()-1;i>=0;i--){ A.push_back(a[i]-'0'); } vector<int> C=mul(A,b); for(int i=C.size()-1;i>=0;i--){ cout<<C[i]; } return 0; }
