基础算法（一）：
1，排序
高效快速的排序法有快速排序和归并排序(考虑到时间复杂度，如果数据过大，一般的冒泡或者sort容易超时，这时候我们的快排和归并排序就发挥了作用)，其中快速排序和归并排序在于前者是==先排序==再==递归==到下一层排序，后者是==先递归==到最底层再==排序==然后回到上一层重复排序的操作。
这里比较简单
直接上快排的代码：
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int a[N];
void quick_sort(int l,int r)
{
if(l>=r) return; //递归终止的条件
int mid = r+l >>1; //相当于mid=(r+l)/2
int x = a[mid];
int i = l-1,j = r+1; //这里的i和j代表着从左和从右边开始的指针
while(i<j)
{
do i++;while(a[i]<x); //分别遍历，直到找到满足需要换位置的条件
do j--;while(a[j]>x);
if(i < j) swap(a[i],a[j]); //因为从小到大排序，所以再x左边的数一定要小于x，右边同理
}
quick_sort(l,j); //进入下一层
quick_sort(j+1,r);
}
int main()
{
int n;
cin>>n;
for(int i = 0;i < n;++ i) cin>>a[i];
quick_sort(0,n-1);
for(int i = 0;i < n;++ i) cout<<a[i]<<" ";
return 0;
接下来是归并排序的模板：
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int a[N],b[N];
void merge_sort(int l ,int r)
{
if(l >= r) return; //同样是递归终止的条件
int mid = l+r>>1;
merge_sort(l,mid); //进入下一层递归中
merge_sort(mid+1,r);
int k = 0,i = l,j = mid+1;
while(i<=mid&&j<=r) //这里的i和j都是下标（要注意！！！）
{
if(a[i]<a[j]) b[k++]=a[i++]; //将数组分成两组，i的一组一定要满足小于j的一组
else b[k++]=a[j++]; //如果i中有比j的大的数，那么就吧j放在前面
}
while(i<=mid) b[k++]=a[i++];
while(j<=r) b[k++]=a[j++];
for(int i = l,j = 0;i <= r;i ++,j ++) a[i]=b[j]; //将数组重新回归到a[i]中去
}
int main()
{
int n;
cin>>n;
for(int i = 0;i < n;i ++) cin>>a[i];
merge_sort(0,n-1);
for(int i = 0;i < n;i ++ ) cout<<a[i]<<" ";
return 0;
}
2,二分查找
2，1整数二分
整数二分的情况比较复杂，需要考虑==边界问题==，这里我们边写边分析:
int l=0,r=n-1; //假定数组是单调的(这里的0和n-1是数组的下标)
int x; cin>>x; //x为要查找的数
while(l<r)
{
int mid=l+(r-l)/2; //为什么不直接写mid=(r+l)/2呢，是为了防止数值溢出；
if(a[mid]>=x) r=mid; //因为a[mid]在x的右边，所以要缩小右边的范围，即让r=mid
else l=mid+1; //同理 l=mid+1;
}
if(a[l]==x) cout<<l<<endl; //输出下标
else cout<<"NO"<<endl; //如果从左往右遍历完仍没有这个数，说明数组中不存在这个数
完整的代码如下(要注意的是这个是查找左边界后面会讲)：
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int a[N];
int main()
{
int n,x;
cin>>n>>x;
for(int i = 0; i < n;i ++) cin>>a[i];
int l=0,r=n-1;
while(l<r)
{
int mid = (r-l)/2+l;
if(a[mid]>=x) r=mid;
else l=mid+1;
}
if(a[l] == x) cout<<l<<endl;
else cout<<"NO"<<endl;
return 0;
}
为什么说是查找左边界呢
例如1 2 5 5 8 10这个数组，我们如果要查找5这个数，那么上述代码只可以输出的下标为2
下面我们来分析一下右边界的情况：
int l = 0,r = n-1; //和上面的一样为数组下标；
int x; cin>>x;
while(l<r)
{
int mid = l+(r-l+1)/2; //这里为什么要加一呢，这个是为了防止出现死循环，在下面我会详细讲一下
if(a[mid] <= x) l = mid; //判断右边界
else r = mid-1; //同理，给出等价关系式
}
if(a[i] == x) cout<<l<<endl; //这里输出l和r其实是一样的，因为循环结束的条件就是l==r
else cout<<"NO"<<endl;
-
==现在来说一下为什么要mid=(r-l+1)/2+l了==
假设我们还是用mid = (r-l+1)/2+l,我们来手动模拟一下：
假设这里有一个数组1 2，如果我们要查找’2‘这个数，那么mid=（1+0）/2的结果应该是0，a[0]=1小于x，那么l=mid应该是0，即一次循环后l和r的值都没有发生变换，那么就会陷入死循环
2，2浮点二分
浮点二分就简单多了，没有那么多的边界情况
这里我们引入一个例题来完成这个代码：
输入一个数字x（1=<x<=1000000） 求它的三次方根
#include<bits/stdc++.h>
using namespace std;
double cheak(double x)
{
return x*x*x;
}
int main()
{
double x;
cin>>x;
double l = 1.0,r = x; //一个范围为1~1000000的数，其三次方根一定在1~1000000范围内
while(r-l>1e-6) //这里是防止精度不同，所以不能直接r>l
{
double mid=(l+r)/2; //相当于除二
if(cheak(mid)>x) r=mid;
else l=mid;
}
printf("%.2f",l);
return 0;
}
3，高精度
这里我们先不用stl，先学会最基础
3.1高精度加减法
- ==高精度加法==
这里我们考虑高精度加高精度，如何将高精度储存和计算呢？这个就需要用字符串来储存和计算
我们先回忆一下我们小学是怎么算两数之和的？ 是不是从个位开始加，然后逢十进一，那么接下来我们用代码实现一下：
#include<bits/stdc++.h>
using namespace std;
string add(string a,string b)
{
string c;
reverse(a.begin(),a.end()); //反转a，b目的是从后往前进位；
reverse(b.begin(),b.end());
if(a.size()<b.size()) swap(a,b); //将位数多的那一个数放在a里面，方便后面的计算
int t = 0; //用t表示每一次进位的值
for(int i = 0;i < a.size();i ++)
{
t+=a[i]-'0';
if(i<b.size()) t+=b[i]-'0'; //这里是处理数据，大家可以手动模拟一下
c+=t%10+'0';
t/=10;
}
if(t) c+=t/10+'0'; //判断最后一次加法有没有进位一；
reverse(c.begin(),c.end()); //将c反转后返回
return c;
}
int main()
{
string a,b,c; //给定三个字符串来存放数字
cin>>a>>b;
c=add(a,b);
cout<<c;
return 0;
}
-
==高精度减法==
和高精度加法一样，这里我们直接给出：
#include<bits/stdc++.h> using namespace std; bool cheak(string a,string b) //判断a与b的大小 { if(a.size()>b.size()) return true; else if(a.size()<b.size()) return false; else { for(int i = 0;i <a.size();i ++ ) { if(a[i]>b[i]) return true; if(a[i]<b[i]) return false; } } return false; } string sub(string a,string b) { string c; int t = 0; reverse(b.begin(),b.end()); for(int i = 1;i <= a.size()-b.size();i++) b+='0'; //这个是将b前面补齐0 reverse(b.begin(),b.end()); for(int i = a.size()-1;i >= 0;i -- ) //同样的数据处理过程，不过这里的a和b不需要反转 { t=t+(a[i]-'0')-(b[i]-'0'); if(t < 0) { c+=(t+10)%10+'0'; t=-1; } else { c+=t+'0'; } } return c; } int main() { string a,b,c; cin>>a>>b; if(cheak(a,b)) //判断a,b大小 { c=sub(a,b); cout<<c<<endl; } else { c=sub(b,a); cout<<'-'<<c<<endl; //记得带负号 } return 0; }3,2高精度乘除法
这里的代码会有点长，建议会python的同学可以润了
-
值得注意的一点，我们每次写代码其实都是==手动模拟==的过程，所以同学们可以先试着直接模拟一边再观看，效果会更好哦。
我们先讲高精度乘法：说实在的，高精度乘法可以理解为**一个高精度的==数==乘以另一个高精度的==每一位数==的==和==**运算
那么我们来开始我们的代码之旅吧：
#include<bits/stdc++.h> using namespace std; string add(string a,string b) //借用高精度加法，但是这里的a和b不需要翻转了，因为mul函数里面已近翻过一次了 { string res; // reverse(a.begin(),a.end()); // reverse(b.begin(),b.end()); if(a.size() < b.size()) swap(a,b); int t = 0; for(int i = 0;i < a.size();++i) { t += a[i] - '0'; if(i < b.size()) t += b[i] - '0'; res += t % 10 + '0'; t/= 10; } if(t) res += t % 10 + '0'; // reverse(res.begin(),res.end()); return res; } string mul(string a,string b) //高精度乘 { string res; reverse(a.begin(),a.end()); //同样，翻转防进位 reverse(b.begin(),b.end()); for(int i = 0;i < a.size();++i) { string res1; //这里定义的res1是b的一个位上的数与a数相乘的结果 int t = 0; for(int j = 0;j < i;++j) res1 += '0'; for(int j = 0;j < b.size();++j) { t += (b[j] - '0') * (a[i] - '0'); res1 += t % 10 + '0'; t /= 10; } while(t) { res1 += t % 10 + '0'; t /= 10; } res = add(res,res1); //将res1相加得结果 } reverse(res.begin(),res.end()); return res; } int main() { string a,b,res; cin >> a >> b; // res = add(a,b); res = mul(a,b); cout << res << endl; return 0; }
4.前缀和与差分
4.1一维前缀和
前缀和分一维前缀和和二维前缀和
先说前缀和是什么：
假设有一个数组：a[1] a[2] a[3] ... a[n] ，其中s[i]=a[1]+a[2]+...+a[i],像这样的s[i]便是关于a[i]的前缀和
再说前缀和的作用：
仍然是上面的数组：a[1] a[2]...a[n],给定T组数据，其中给定两个数l，r，求a[l]到a[r]之间的所有数组之和
如果是暴力枚举每一次都是for(int i = l;i <= r;i ++ )那么时间复杂度是o(n),如果用前缀和s[r]-s[l-1],那么时间复杂度就会变成o(1).
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int a[N],s[N]; //全局变量默认s[0]=0
int main()
{
int t,n;
cin>>n>>t;
for(int i = 1;i <= n;i ++ ) cin>>a[i];
for(int i = 1;i <= n;i ++ ) s[i]=a[i]+s[i-1]; //前缀和运算
while(t--)
{
int l,r;
cin>>l>>r;
cout<<s[r]-s[l-1]<<endl;
}
return 0;
}
4.2二维前缀和
这里结合例题理解：
输入一个 n行 m 列的整数矩阵，再输入 q 个询问，每个询问包含四个整数 x1,y1,x2,y2，表示一个子矩阵的左上角坐标和右下角坐标。
对于每个询问输出子矩阵中所有数的和。
这里我们给出模板，大家可以画方格作二维数组并结合下面的注释方便理解：
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3+10;
int a[N][N],s[N][N];
int main()
{
int n,m,q;
cin>>n>>m>>q;
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= m;j ++)
cin>>a[i][j];
for(int i = 1;i <= n;i ++)
{
for(int j = 1;j <= m;j ++)
{
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
}
}
while(q--)
{
int x1,x2,x3,x4;
cin>>x1>>x2>>x3>>x4;
cout<<s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]<<endl;
}
return 0;
}
4.3一维差分
差分是什么：差分可以看作前缀和的逆运算，像求导和积分的一样。比如有一个
a[n]数组，构造b[n]使得a[n]=b[1]+b[2]+...+b[n]让a[n]是b[n]的前缀和。那么b[n]就叫做a[n]的差分一维差分的构造：让
b[1]=a[1] b[2]=a[2]-a[1] ... b[n]=a[n]-a[n-1]差分的作用：（这里我们给出打卡题方便理解）
输入一个长度为 n 的整数序列。
接下来输入 m 个操作，每个操作包含三个整数 l,r,c表示将序列中 [l,r][l,r] 之间的每个数加上 c
请你输出进行完所有操作后的序列。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int a[N],b[N];
int main()
{
int n,m;
cin>>n>>m;
for(int i = 1;i <= n;i ++) cin>>a[i];
for(int i = 1;i <= n;i ++) b[i]=a[i]-a[i-1]; //差分计算
while(m--)
{
int l,r,c;
cin>>l>>r>>c;
b[l]+=c; //这里让b[l]=b[l]+c，那么a[l]到a[n]都会等于它本身加上c
b[r+1]-=c; //这里让b[r+1]=b[r+1]-c,那么a[r+1]到a[n]都会等于它本身减c
}
for(int i = 1;i <= n;i ++ )
{
a[i]=a[i-1]+b[i]; //前缀和计算
cout<<a[i]<<" ";
}
return 0;
}
4.4二维差分
同样是二维前缀和的逆运算
放打卡题：
输入一个 n 行 m 列的整数矩阵，再输入 q 个操作，每个操作包含五个整数 x1,y1,x2,y2,c其中 (x1,y1)和 (x2,y2)表示一个子矩阵的左上角坐标和右下角坐标。
每个操作都要将选中的子矩阵中的每个元素的值加上 c。
请你将进行完所有操作后的矩阵输出。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3+10;
int a[N][N],b[N][N];
void intt(int x1,int y1,int x2,int y2,int c)
{
b[x1][y1]+=c;
b[x2+1][y1]-=c;
b[x1][y2+1]-=c;
b[x2+1][y2+1]+=c;
}
int main()
{
int n,m,q;
cin>>n>>m>>q;
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= m;j ++)
cin>>a[i][j];
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= m;j ++)
intt(i,j,i,j,a[i][j]);
while(q--)
{
int x1,x2,y1,y2,c;
cin>>x1>>y1>>x2>>y2>>c;
intt(x1,y1,x2,y2,c);
}
for(int i = 1;i <= n;i ++ )
{
for(int j = 1;j <= m;j ++ )
b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1];
}
for(int i = 1;i <= n;i ++ )
{
for(int j = 1;j <= m;j ++ )
cout<<b[i][j]<<" ";
cout<<endl;
}
return 0;
}
5.双指针算法
概念：双指针算法是一种通过设置两个不同的指针不断进行单向移动来解决问题的算法。
有两种形式：
- 两个指针同时指向同一序列 比如：快速排序的划分区间过程
- 两指针指向不同的序列 比如：归并排序的合并过程
双指针的用处：将两个或者一个数列中需要经过两层for循环的时间复杂度o(n^2^)降低到一层for循环的时间复杂度o(n)
例题：
给定两个升序排序的有序数组 A 和 B，以及一个目标值 x。数组下标从 0 开始。请你求出满足 A[i]+B[j]=x 的数对 (i,j)。数据保证有唯一解。
输入格式
第一行包含三个整数 n,m,x分别表示 A 的长度，B 的长度以及目标值 x。
第二行包含 n 个整数，表示数组 A。
第三行包含 m 个整数，表示数组 B。
输出格式
共一行，包含两个整数 i 和 j。
分析：如果我们直接暴力枚举，j从0到m-1，i从0到n-1.那这个题目就会超时（毕竟没有什么地方会出这么简单的题目）。
但是我们将i和j的关系连接起来，那么问题就会简化
#include<bits/stdc++.h>
using namespace std;
const long long N = 1e5+10;
long long a[N],b[N];
int main()
{
int n,m,x;
scanf("%d%d%d",&n,&m,&x);
for(int i = 0;i < n;i ++ ) scanf("%d",&a[i]);
for(int i = 0;i < m;i ++ ) scanf("%d",&b[i]);
int j = m - 1;
for(int i = 0,j=m-1;i < n;i ++ )
{
while(j >= 0&&a[i]+b[j] > x) j--;
if(j >= 0&&a[i]+b[j] == x)
{
printf("%d %d\n",i,j);
return 0;
}
}
return 0;
}
京公网安备 11010502036488号