算法基础
第一章：基础算法
1、排序
- 各种排序算法
2、二分查找
- 描述：在一个有序数组里面查找某个目标值
- 解析：
- mid = left + (right - left)/2;
- mid所在的val小于target_val的时候，left = mid + 1，即区间取右半区间
- mid所在的val小于target_val的时候，right = mid - 1，即区间取左半区间
- mid = left + (right - left)/2;
- 牛客题目链接：二分查找
- 代码
class BinarySearch {
public:
int getPos(vector<int> A, int n, int val) {
// write code here
int left = 0,right = n-1;
while(left <= right)
{
int mid = left + (right - left)/2;
if(A[mid] == val)
{
auto i = mid - 1;
for(;i>=0 && A[i] == val;i--)
{
}
return i+1;
}
else if(A[mid] > val)
{
right = mid - 1;
}
else {
left = mid + 1;
}
}
return -1;
}
};
3、大数据量的加法和减法（高精度加减法）
3.1、加法
-
描述：超出数据类型范围的数的相加
-
解析：
- 存储：为了方便进位，则把低位数保存在容器的低位
- 运算：对应位的和为(C+Ai+Bi)%10，进位为C/10；
- 全部算完之后还要判断最高位是否有进位，有的话把进位再插入容器
- 输出的时候逆序输出
-
牛客题目链接：高精度加法
-
代码
#include <iostream>
#include<string>
#include<vector>
using namespace std;
const int N = 10000;
void add(vector<int>&A, vector<int>&B, vector<int>&C)
{
int t = 0;
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;
}
if(t > 0)
C.push_back(t);
}
int main() {
string a,b;
cin >> a >> b;
vector<int>A,B,C;
for(int i = a.length()-1; i >= 0; i--)
{
A.push_back(a[i] - '0');
}
for(int i = b.length()-1; i >= 0; i--)
{
B.push_back(b[i] - '0');
}
add(A,B,C);
for(int i = C.size()-1; i >= 0; i--)
{
printf("%d",C[i]);
}
}
// 64 位输出请用 printf("%lld")
3.2、减法
-
描述：超出数据类型范围的数的减法
-
解析：A>B则用A-B；A<B则用-（B-A)，相减的时候为对应位相减且减去借位c，c起始为0，得到的结果分为大于0和小于0，大于0则直接得到输出结果，小于0则还需要加上10，两个可合并为（sum+10）%10，最后还要判断下一位的借位
-
题目链接：未找到
#include<iostream>
#include<vector>
#include<string>
using namespace std;
/* 比较两个数的大小，从高位往低位依次比较 */
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;
for(int i = 0,c=0; i < A.size(); i++)
{
/* c是借位 */
c = A[i] - c;
if(i < B.size())
c -= B[i];
C.push_back((c+10)%10);
if(c < 0)
c = 1;
else
c = 0;
}
/* 去掉前导0，全为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;
/* 低位数存入容器的低位位置 */
for(int i = a.length()-1; i >= 0; i--)
{
A.push_back(a[i] - '0');
}
for(int i = b.length()-1; i >= 0; i--)
{
B.push_back(b[i] - '0');
}
if(cmp(A,B))
{
auto C = sub(A,B);
for(int i = C.size()-1; i >= 0; i--)
{
printf("%d",C[i]);
}
}
else
{
auto C = sub(B,A);
printf("-");
for(int i = C.size()-1; i >= 0; i--)
{
printf("%d",C[i]);
}
}
}
4、前缀和
4.1、一维前缀和
- 描述：在一个一维数组里面求某一段区间内的和
- 解析：
- 数组a[N]，S[i] = S[i-1]+a[i]，区间l到r的和为S[r]-S[l-1]
- 题目链接：前缀和
- 代码
#include <iostream>
#include<vector>
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N];
long long S[N];
int main() {
int n,q;
cin >> n >> q;
for(int i = 1; i <= n; i++)
{
scanf("%d",&a[i]);
S[i] = S[i-1] + a[i];
}
while(q--)
{
int l,r;
scanf("%d%d",&l,&r);
printf("%lld\n",S[r] - S[l-1]);
}
return 0;
}
// 64 位输出请用 printf("%lld")
4.2、二维前缀和
- 描述：一个二维矩阵A[n][m]，求其(x1,y1)和其(x2,y2)之间的矩阵和
- 解析：先算出S[i][j]，再算两点间的和
- 求S[i][j]的和
- 计算两点间的和，注意边界，需要包含x1,y1
- 题目链接：二维前缀和
- 代码
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int A[N][N];
long long 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];
S[i][j] = S[i][j-1] + S[i-1][j] - S[i-1][j-1] + A[i][j];
}
}
while(q--)
{
int x1,y1,x2,y2;
cin >> x1 >> y1 >> x2 >> y2;
cout << S[x2][y2] - S[x2][y1-1] - S[x1-1][y2] + S[x1-1][y1-1] << endl;
}
}
5、差分
5.1、一维差分
- 描述：在a[n]这个数组中的某一段全部加上某个数
- 解析：an是bn的前缀和，bn是an的差分，在bl+k，在b(r+1)-k，相当于只在l到r这段里面的数加上了k
- 题目链接：一维差分
- 代码
#include <iostream>
using namespace std;
const int N = 100010;
int n,m;
long long a[N],b[N];
void insert(int l,int r,int k)
{
b[l] += k;
b[r + 1] -= k;
}
int main() {
cin >> n >> m;
for(int i = 1; i <= n; i++)
{
cin >> a[i];
insert(i, i, a[i]);
}
while(m--)
{
int l,r,k;
cin >> l >> r >> k;
insert(l, r, k);
}
for(int i = 1; i <= n; i++)
{
b[i] += b[i-1];
cout << b[i] << " ";
}
}
5.2、二维差分
- 描述：将二维矩阵中的其中一个子矩阵每个数都加上一个数
- 解析：只将图中的子矩阵中的每个数加上c，表达式如图中所示
- 同样b[i][j]是a[i][j]的差分，a是b的前缀和，也就是b[i][i]上方的子矩阵的和就为a[i][j]，前缀和公式如图
- 题目链接：二维差分
- 代码
#include <iostream>
using namespace std;
const int N = 1010;
long long a[N][N],b[N][N];
int n,m,q;
void insert(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() {
cin >> n >> m >> q;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
cin >> a[i][j];
insert(i,j,i,j,a[i][j]);
}
while(q--)
{
int x1,y1,x2,y2,k;
cin >> x1 >> y1 >> x2 >> y2 >> k;
insert(x1,y1,x2,y2,k);
}
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];
cout << b[i][j] << " ";
}
cout << endl;
}
}
6、双指针
- 题目链接：最长连续无重复子序列
- 代码
#include <unordered_map>
class Solution {
public:
int maxLength(vector<int>& arr) {
int n = arr.size();
unordered_map<int, int>mp;
int ret = 0;
for(int i = 0,j = 0; i < n; i++)
{
mp[arr[i]]++;
while(mp[arr[i]] > 1)
{
mp[arr[j]]--;
j++;
}
ret = max(ret,i-j+1);
}
return ret;
}
};
7、位运算
7.1、lowbit的应用
- 描述：求x的第k位的大小
- 公式：（x >> k） & (-x)
- 题目链接：二进制数中1的个数
8、离散化
-
描述：在一个无限长的坐标中进行添加和询问操作，坐标上的数起始全为0，add的（1，2）表示在坐标1加2，query的（1，2）表示求区间1，2之间的和，和为5，所以输出5
-
解析：1、将操作的下标全部存进容器，排序后去重；2、使用二分查找算出离散化的值；3、再使用前缀和算出结果
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef pair<int,int>PII;
const int N = 300010;
int n,m;
int a[N],S[N];
vector<int>alls;
vector<PII>add,query;
int find(int 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;
}
int main()
{
cin >> n >> m;
for(int i = 0; i < n; i++)
{
int x,c;
cin >> x >> c;
add.push_back({x,c});
alls.push_back(x);
}
for(int i = 0; i < m; i++)
{
int l,r;
cin >> l >> r;
query.push_back({l,r});
alls.push_back(l);
alls.push_back(r);
}
sort(alls.begin(),alls.end());
alls.erase(unique(alls.begin(),alls.end()),alls.end());
for(auto item:add)
{
int x = find(item.first);
a[x] += item.second;
}
for(int i=1;i<=alls.size();i++)
S[i] = S[i-1] + a[i];
for(auto item:query)
{
int l = find(item.first),r = find(item.second);
cout << S[r] - S[l-1] << endl;
}
return 0;
}
9、区间合并
- 描述：给定多个区间，将能合并的合并，不能合并的保留，最后输出所有区间
- 解析：先将所有的区间排序，比较维护区间的右区间端点和新区间的左端点，如果新区间的左端点比维护区间的右端点大，则两个不能合并，将维护的区间保存起来，新区间变成维护区间接着往下比较，一直到最后一个
- 题目链接：区间合并
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef pair<int,int>PII;
vector<PII>store;
vector<PII>ret;
void merge(vector<PII>&tmp)
{
int st = -2e9,ed = -2e9;
sort(tmp.begin(),tmp.end());
for(auto c:tmp)
{
if(ed < c.first)
{
if(st != -2e9) ret.push_back({st,ed});
st = c.first,ed = c.second;
}
else
ed = max(ed,c.second);
}
if(st != -2e9) ret.push_back({st,ed});
}
int main()
{
int n,st,ed;
cin >> n >> st >> ed;
for(int i = 0; i < n; i++)
{
int l,r;
cin >> l >> r;
store.push_back({l,r});
}
store.push_back({st,ed});
merge(store);
/* 输出 */
for(auto c:ret)
{
cout << c.first << c.second << endl;
}
}
