第一讲 基础算法
一、快速排序
快速排序步骤：
- 确定分界点 q[l] q[(hr)/2] q[r]
- 调整区间
- 递归处理左右两端
void quick_sort(int q[],int l,int r){
if(l >= r){
return;
}
// >>是位运算 二进制右移以为 相当于/2
//x=q[l+r >> 1]
//或者改成x = q[(l+r+1)/2];
int i = l - 1, j = r + 1, x = q[(l+r+1)/2];
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,i - 1);
quick_sort(q,i,r);
}
二、归并排序–分治
- 确定分界点
- 递归排序left、right
- 归并–合二为一
void merge_sort(int q[],int l, int r){
if( l >= r){
return;
}
//相当于(l + r) / 2
int mid = l + r >> 1;
//分
merge_sort(q,l,mid);
merge_sort(q,mid+1,r);
//寻找最小放入tmp
int k = 0,i = l,j = mid + 1;
while(i <= mid && j <= r){
if(q[i] <= q[j]){
tmp[k++] = q[i++];
}else{
tmp[k++] = q[j++];
}
}
while(i<=mid){
tmp[k++] = q[i++];
}
while(j<=r){
tmp[k++] = q[j++];
}
for(i = l, k = 0;i <= r; i++,k++){
q[i] = tmp[k];
}
}
逆序对的数量
在数组a[1],a[2],a[i],a[j],,...,a[n]中，如果 i < j && a[i] > a[j] ,则表示a[i] a[j]是一对逆序对。
//首先我们想到暴力解法，便是
for(int i = 0;i < n;i++){
for(int j = i + 1;j < n;j++){
if(a[i] > a[j]){
res++;
}
}
}
// 这样时间复杂度是 O(n^2) 毫无疑问是超时的
// 逆序对存在的位置有三种情况
[HTML_REMOVED]
由此我们的计算方式是：
- 递归计算左边[红色]
- 递归计算右边[蓝色]
- 计算存在与两边的[绿色]
- 把结果加在一起
这里我们需要知道一个性质，左边红色元素的位置调换，是不影响第三步的计算的，也就是红色元素在判断逆序对时，本生红色元素互不干扰。因此我们可以在计算完逆序对的数量后，对其进行排序。排序的作用在于，在计算第三步时：
[HTML_REMOVED]
#include<iostream>
using namespace std;
typedef long long LL;
const int N = 100010;
int n;
int a[N],tmp[N];
LL merge_sort(int l,int r){
if( l >= r){
return 0;
}
int mid = l + r >> 1;
LL res = merge_sort(l,mid) + merge_sort(mid + 1,r);
//归并的过程：
int k = 0, i = l,j = mid + 1;
while(i <= mid && j <= r){
if(a[i] <= a[j]){
tmp[k++] = a[i++];
}else{
tmp[k++] = a[j++];
res += mid - i + 1;
}
}
// 扫尾
while(i <= mid){
tmp[k++] = a[i++];
}
while(j <= r){
tmp[k++] = a[j++];
}
// 物归原主
for(int i = l,j = 0; i <= r;i++,j++){
a[i] = tmp[j];
}
return res;
}
int main(){
scanf("%d",&n);
for(int i = 0;i < n;i++){
scanf("%d",&a[i]);
}
cout<< merge_sort(0,n-1) <<endl;
return 0;
}
三、二分
题目：在给定有序序列中找到所给x的初始下标和终止下标，也就是x出现的第一个位置和最后一个位置，首先查找第一个即p[i]>=x 然后找最后一个即p[i]<=x
const int N = 100010;
int q[N];
int n,m;
int main(){
scanf("%d%d",&n,&m);
for(int i = 0;i < n;i++){
scanf("%d",&q[i]);
}
while(m--){
int x;
scanf("%d",&x);
int l = 0, r = n-1;
//q[mid] >= x 即寻找位于左部分 区间分为 l mid mid+1 r
while(l < r){
int mid = l + r >> 1;
if(q[mid] >= x){
r = mid;
}else{
l = mid + 1;
}
}
if(q[l] != x){
cout<<"-1 -1"<<endl;
}else{
cout<< l <<' ';
//q[mid] <= x 即寻找位于右部分 区间分为 l mid-1 mid r
int l = 0, r = n - 1;
while(l < r){
//这时候就需要 mid = l + r + 1 >> 1
int mid = l + r + 1 >> 1;
if(q[mid] <= x){
l = mid;
}else{
r = mid - 1;
}
}
cout<< l << endl;
}
}
return 0;
}
四、高精度
4.1 高精度加法
- 大整数存储
- 模拟计算过程[将整数按位存入vector数组中，低位放入下标靠前位置]
- 按位计算t=A[i] + B[i] 存入数组C时去除进位C.push_back[t%10], t保留进位：t /= 10;
vector<int> add(vector<int> &A, vector<int> &B){
vector<int> C;
int t = 0; //t进位
for(int i = 0;i < A.size() || i < B.size();i++) {
if(i < A.size()) t += A[i];
if(i < B.size()) t += B[i];
C.push_back(t%10);//t%10 = 去掉t进位
t /= 10; // t/=10 保留进位给下一次循环
}
if(t)C.push_back(1);
return C;
}
int main(){
string a,b; // a = 123456
vector<int> A,B;
cin>>a>>b;
// A = [6,5,4,3,2,1]
for(int i = a.size() - 1; i >= 0; i--){
A.push_back(a[i] - '0'); //注意放入vector数组中需要 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--){
printf("%d" , C[i]);
}
}
4.2 高精度减法：
原理与高精度加法类似，都是逐位进行计算，t = A[i] - B[i] - t
//判断是否有 A>=B
bool cmp(vector<int> &A,vector<int> &B){
if(A.size() != B.size()) return A.size() > B.size();
for(int i = A.size() - 1;i >= 0;i--){
if(A[i] != B[i]) return A[i] > B[i];
}
return true;
}
vector<int> sub(vector<int> &A, vector<int> &B){
vector<int> C;
int t = 0;
for(int i = 0; i < A.size();i++){
//t = A[i] - B[i] - t;
t = A[i] - t;
//在cmp保证了A>=B的情况下，当B的位数还没走完即需要减去B
if(i < B.size()) t -= B[i];
/*
对于t 位数相减后
t >= 0 t = t
t < 0 需要向前借一位，即本位+10
(t + 10) % 10 综合了以上两种情况
*/
C.push_back((t + 10) % 10);
if(t<0) t = 1;
else t = 0;
}//去除前导0
while(C.size() > 1 && C.back() == 0){
C.pop_back();
}
return C;
}
4.3 高精度乘法：
1234 * 12
4.4 高精度除法：
五、前缀和、差分、差分矩阵
5.1 前缀和
假设有数列 a[1],a[2],a[3]...a[n]
其前缀和数组： s[n] = a[1] + a[2] + a[3] + ... + a[n]
以此类推
前缀和计算公式便可写成:s[i] = s[i-1] + a[i]
现要求计算区间为[l,r] 内的数列和
由于
[l,r]内 = a[l] + a[l+1] + a[l+2] + ...a[r]
s[l] = a[1] + a[2] + ... + a[l]
s[r] = a[1] + a[2] + ... + a[l]+ ... + a[r]
故a[l]+ ... + a[r] = s[r] - s[l - 1]
#include<iostream>
using namespace std;
const int N = 100010;
int a[N],b[N];
int n,m;
int main(){
scanf("%d%d",&n,&m);
for(int i = 1;i <= n;i++){
scanf("%d",&a[i]);
b[i] = b[i-1] + a[i];//前缀和数组
}
int l,r;
while(m--){
scanf("%d%d",&l,&r);
printf("%d\n",b[r] - b[l - 1]);
}
return 0;
}
#include<iostream>
#include<cstdio>
using namespace std;
const int N = 1010;
int a[N][N], b[N][N];
int n,m,q;
int main(){
scanf("%d%d%d",&n,&m,&q);
for(int i = 1;i <= n;i++){
for(int j = 1; j <= m;j++){
scanf("%d",&a[i][j]);
b[i][j] = b[i-1][j] + b[i][j-1] - b[i-1][j-1] + a[i][j];
}
}
while(m--){
int x1,y1,x2,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
printf("%d\n",b[x2][y2] - b[x1 - 1][y2] - b[x2][y1 - 1] + b[x1-1][y1-1]);
}
return 0;
}
5.2差分
-
前缀和 与 差分 是互逆运算
-
给定一个原数组 a:
a[1],a[2],a[3],...,a[n] - 再构造一个数组 b:
b[1],b[2],b[3],...,b[m] - 使得：
a[i] = b[1] + b[2] + b[3] + ... + b[i] - 也就是说a 数组是b 数组的前缀和数组，反之b数组是a数组的 差分数组，也就是说，每一个a[i] 都是b 数组从头开始的一段区间和。
那么构造差分数组的作用是什么呢？举个例子：
在区间 [l , r],把a数组中的每一个元素都加上c，即a[l] + c,a[l+1] + c,a[l+2] + c,...,a[r] + c, 此问题的暴力解法便是直接for循环，时间复杂度是O(n), 假设有m次操作那么时间复杂度是O(n*m),一般来说题目这么些会超时的。
那么如何解呢，使用差分数组，我们要知道，a数组是b数组的前缀和数组，也就是说对b数组的b[i]进行修改，会影响a数组中从a[i] 及往后的每一个数。
首先让差分数组 b数组中的b[l] + c, 相当于 a 数组变成 a[l] + c, a[l+1] + c, a[l+2] + c, ...,a[r] + c, a[r+1] + c, ... ,a[n] + c,
由于我们只需要区间[l , r]内的元素加上c，故在元素a[r+1]后的元素就需要减去 c
即b数组中的b[r+1] - c , a 数组变成 a[r+1] - c, a[r+1] r c, a[r+2] - c, ... ,a[n] - c,
两者结合便是在区间[l , r]内的元素加上c。
#include<iostream>
using namespace std;
const int N = 100010;
int a[N],b[N];
int n,m;
int main(){
scanf("%d%d",&n,&m);
for(int i = 1;i<=n;i++){
scanf("%d",&a[i]);
}
//构建差分数组
for(int i = 1;i <=n ;i++){
b[i] = a[i] - a[i-1];
}
while(m--){
int l,r,c;
scanf("%d%d%d",&l,&r,&c);
b[l] += c;
b[r + 1] -= c;//将序列 l 和 r 之间加上 c
}
////前缀和计算
for (int i = 1; i <= n; i++){
a[i] = b[i] + a[i - 1];
printf("%d ", a[i]);
}
return 0;
}
5.3 二维差分
以上的是一维差分，扩展到二维，也就是说在矩阵中某子矩阵中的每个元素都加上一个 c ，暴力解法与一维类似，一定会超时，那么考虑二维差分。
我们知道一维差分的本质就是元素差，那么二维差分就是矩阵差。差分就是后面的元素减去前面的元素，由前面决定后面。所以我们需要做的是 a[][]数组 是b[][]数组的前缀和数组， b[][]数组 是a[][]数组的差分数组
原数组：a[][]
构造差分数组：b[][]数组
使得 a数组中 a[i][j] 是 b数组 从左上角(1 , 1)到右下角(i , j)所包围矩阵的和
如何构造差分数组 b数组 呢？ 同一维差分，a数组是b数组的前缀和，对b数组的b[i][j]修改会影响到a数组从a[i][j]及往后的每一个元素，选定的子矩阵是 (x1, y1) , (x2, y2)
b[x1][y1]+= c ;
b[x1][y2 + 1] -= c ;
b[x2 + 1][y1] -= c ;
b[x2 + 1][y2 + 1] += c ;
效果如图所示，我们要求的是蓝色矩阵 (x1, y1) , (x2, y2)内的元素都加上 c ，首先进行绿色部分的计算也就是b[x1][y1]+= c ; 绿色部分便是从（x1，y1） 到矩阵末尾，随后减去红色部分和紫色部分b[x1][y2 + 1] -= c ;b[x2 + 1][y1] -= c ;，随后我们发现两者有重叠也就是减了两次需要加回来一次也就是b[x2 + 1][y2 + 1] += c ;
#include<iostream>
using namespace std;
const int N = 1010;
int n,m,q;
int s[N][N] , a[N][N];
void insert(int x1,int y1,int x2,int y2,int c){
s[x1][y1] += c;
s[x1][y2 + 1] -= c;
s[x2 + 1][y1] -= c;
s[x2 + 1][y2 + 1] += c;
}
int main(){
scanf("%d%d%d",&n,&m,&q);
for(int i = 1;i <= n ;i++)
for(int j = 1;j <= m;j++)
scanf("%d",&a[i][j]);
for(int i = 1;i <= n;i++)
for(int j = 1;j <= m;j++)// 构建差分数组
insert(i,j,i,j,a[i][j]);
while(q--){
int x1,y1,x2,y2,c;
scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&c);
insert(x1,y1,x2,y2,c);
}
for(int i = 1;i <=n ;i++){
for(int j =1 ;j <= m;j++){
// 一维前缀和： a[i] = b[1] + b[2] + ... + b[i] = b[i-1] + a[i]
// 二维前缀和: a[i][j] = b[i][j] + a[i-1][j] + a[i][j-1] - a[i-1][j-1]
// 跟以下写法是一样的 a[i][j] = b[i][j] + a[i-1][j] + a[i][j-1] - a[i-1][j-1] 更符合前缀和性质 也便以理解
s[i][j] = s[i][j] + s[i-1][j] + s[i][j-1] - s[i-1][j-1];
}
}
for(int i = 1;i <=n ;i++){
for(int j =1 ;j <= m;j++){
printf("%d ",s[i][j]);
}
printf("\n");
}
return 0;
}
六、双指针
核心思想：
//在双指针中，如果采用暴力解法如
// 核心思想
for(int i = 0; i< n; i++){
for(int j = 0; j < m; j++){
//时间复杂度： O(n^2);
}
}
//我们在此学习地双指针算法地目的就是把上述算法优化到O(n)
for(int i = 0,j = 0;i < n; i++){
while( j < i && check(i, j)){
j++
}
//具体题目逻辑
}
寻找最长连续不重复子序列，有i，j 两个指针，最长res = i - j +1 也就是两个指针之间的长度，那么就是说 i 指针往右走，记录遇到个每一个元素并计算当前最长子序列；当遇到一个已经被记录的元素时，j 往右走，计算当前最长子序列。
#include<iostream>
using namespace std;
const int N = 100010;
int n;
int a[N], s[N];
int main(){
cin>>n;
for(int i = 0; i < n;i++)cin>>a[i];
int res = 0;
for(int i =0,j = 0;i < n;i++){
s[a[i]]++;
while(s[a[i]] > 1){
s[a[j]]--;
j++;
}
res = max(res, i - j + 1);
}
cout<<res<<endl;
return 0;
}
七、位运算
7.1 lowbit(x) ：求x的最后一位 1 ，一个数x的二进制中有多少个1
x & -x = x & (~x + 1)
1. x = 1010 ... 1 00 ... 0
2. ~x = 0101 ... 0 11 ... 1
3. ~x + 1 = 0101 ... 1 00 ... 0
4. x & (~x + 1) = 0000 ... 1 00 ... 0
//若计算一个数x的二进制中有多少个1 或 最后一个1的位置
1 - 4 即可减去末尾的1
x = x - (x & -x)
7.2 原码 反码 补码
x = 1010
原码 0...01010
反码 1...10101
补码 = 反码 + 1
= 1...10110
八、整数离散化
我们很容易九可以看出来其中存在的问题
a[i]中可能有重复元素 – 去重- 如何算出
a[i]离散化后的值
vector容器中unique(alls.begin(), alls.end()) 去重， unique是吧重复的元素放到了数组的最后面，返回重复区间的左下标
erase删除vector容器的元素
vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end()); // 去掉重复元素
// 二分求出x对应的离散化的值
int find(int x) // 找到第一个大于等于x的位置
{
int l = 0, r = alls.size() - 1;
while (l < r)
{
int mid = l + r >> 1;
if (alls[mid] >= x) r = mid;
else l = mid + 1;
}
return r + 1; // 映射到1, 2, ...n
}
题目：区间和
九、区间合并
// 将所有存在交集的区间合并
void merge(vector<PII> &segs)
{
vector<PII> res;
sort(segs.begin(), segs.end());
int st = -2e9, ed = -2e9;
for (auto seg : segs)
if (ed < seg.first)
{
if (st != -2e9) res.push_back({st, ed});
st = seg.first, ed = seg.second;
}
else ed = max(ed, seg.second);
if (st != -2e9) res.push_back({st, ed});
segs = res;
}
区间合并中思路是简单的，给定多个区间，有交集的合并，思路是：使用struct或者pari保存一对对区间，对左端点进行排序，再利用贪心思路第 i 个的左端点 小于第 i - 1 个的右端点的话【有序】，那么如果i-1的右端点 小于 i 的右端点的话，更新此时的最大右端点max，res++；
