基础算法

上课的主要任务：理解算法的主要思想，在理解的基础上进行记忆

*课下的任务：把代码背过，能够快速的把代码写出来，调试通过就可以啦（利用课后习题来进行背诵，用模版题检验背诵的效果，写完之后删掉再重复写3到5遍）

排序

快排

主要基于分而治之的思想：
确认定边界点
*调整区间，把整个区间划分为两个区间，左边区间的数都小于等于x，右边的数都大于等于x
递归处理左右两边

#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){
    // 找到小于x的数字
    do i++; while(q[i]<x);
    do j--; while(q[j]>x);
    // 找到大于x的数字
    if(i<j) swap(q[i],q[j]);
  }
  // 递归左边的区域
  quick_sort(q,l,j);
  // 递归右边的区域
  quick_sort(q,j+1,r);
}

int main(){
  scanf("%d",&n);
  // 数据输入
  for (int i=0;i<n;i++) scanf("%d",&q[i]);
  quick_sort(q,0,n-1);
  for(int i = 0;i < n;i++) printf("%d",q[i]);
}

归并排序

还是主要运用分而治之的思想
确定分界点，数组的中间点
递归排序，左边和右边
*归并，合二为一（双指针算法）

#include <iostream>

using namespace std;

const int N = 1e6 + 10;

int n;
int q[N],tmp[N];

void merge_sort(int q[],int l,int r){
  if (l >= r) return;
  int mid = l + r >> 1;
  merge_sort(q,l,mid), merge_sort(q,mid+1,r);
  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++];
  // 将tmp中的数放回到q中
  for(i = l,j = 0;i <= r;i++,j++) q[i] = tmp[j];
}

int main(){
  scanf("%d",&n);
  // 数据输入
  for (int i=0;i<n;i++) scanf("%d",&q[i]);
  merge_sort(q,0,n-1);
  for(int i = 0;i < n;i++) printf("%d",q[i]);
}

二分

整数二分

二分的本质是：对于一个区间，整个区间可以被一分为二，左半边满足某个性质，右半边不满足某个性质，那么二分查找就可以找到这个性质的边界
先写mid
写check函数，思考如何更新区间

bool check(int x){/* ... */} // 检查x是否满足某种性质

// 区间[l, r]被划分为[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l,int r){
  while(l < r){
    int mid = l + r >> 1;
    if(check(mid)) r = mid;
    else l = mid + 1;
  }
  return l;
}

// 区间[l, r]被划分为[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l,int r){
  while(l < r){
    int mid = 1 + l + r >> 1;
    if(check(mid)) l = mid;
    else r = mid - 1;
  }
  return l;
}  

浮数二分

直接更新左右边界即可，将两个边界的重合区域的范围作为阈值

高精度

大整数相加
大整数相减
大整数乘以小整数
大整数除以小整数
基本思路：把大整数的每一位存入到数组当中
存入的数应该是小端的，因为如果有进位的话在数组的末尾添加一个数会比较简单
“用代码去模拟人工加法的方式进行计算”

高精度加法

tip

算法步骤：

将数字倒序存储在vector当中
使用t来存储时候需要进位，加法最多进位一次
遍历A和B的每一位进行加法计算，t%10是这一位的计算结果
不要忘了处理最后一位的进位情况

#include <iostream>
#include <vector>

using namespace std;


// 大整数相加模板
vector<int> add(vector<int> &A,vector<int> &B){
  vector<int> C;
  int t = 0; // t = 0表示需要借位，t   = 1表示需要借位
  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) C.push_back(1); // 处理有进位的情况
  return C;
}


int main(){
  string a,b;
  vector<int> A,B;
  
  cin >> 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--) printf("%d",c[i]);
}

高精度减法

tip

判断一下那个数大，用大数减去小数
用t来表示借位, t为0表示没有借位，为1表示有借位
循环遍历每一位进行计算
首先先处理借位问题，t = A[i] - t
然后计算每一位相减 t -= B[i]
存储第i位的计算结果：(t + 10)%10
更新t（判断是否有进位）
去除多余的0

#include <iostream>
#include <vector>
#include <string>
using namespace std;

bool cmp(string a,string b){
    if(a.size() > b.size()) return true;
    if(a.size() < b.size()) return false;
    int i = 0;
    bool flag = true;
    for(int i = 0;i<a.size();i++)
    {
        if(a[i] < b[i])
        {
            flag = false;
            break;
        }else if(a[i] > b[i]){
            break;
        }
    }
    return flag;
}

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] - 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 and C.back() == 0) C.pop_back();
    return C;
}

int main()
{
    vector<int> A;
    vector<int> B;
    string a;
    string b;
    cin >> 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;
    if(cmp(a,b)){
        C = sub(A,B);    
    }else{
        cout << "-";
        C = sub(B,A);
    }
    
    for(int i = C.size()-1;i>=0;i--) cout << C[i];
    
}

大整数乘一个小数

tip

大整数乘以一个较小数的模板

倒序存储数字
使用t作为进位标志，t%10为该位的计算结果，t/10为进位
模拟乘法进行计算
去除多余的0

#include <iostream>
#include <vector>

using namespace std;

vector<int> mul(vector<int> &A,int b)
{
  int t = 0;
  vector<int> C;
  for(int i = 0;i<A.size() || t;i++){
    if(i<A.size()) t += A[i] * b;
    C.push_back(t%10);
    t /= 10;
  }
  return C;
}

int main()
{
  string a;
  int b;
  vector<int> A;
    cin << a << b;
  if(b == 0) cout << 0;
  return 0;
  for(int i=a.size()-1;i >= 0;i--) A.puck_back(a[i] - '0');
  vector<int> C = mul(A,b);
  
}

大整数除以一个较小整数

tip

使用vector逆序存储大数
逆序对大数进行处理
使用一个r，然后用乘10的操作来模拟除法时候的后退操作
将结果取反
去除多余的0
保存余数

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> divi(vector<int> A,int b)
{
    int r = 0;
    vector<int> C;
    for(int i=A.size()-1;i>=0;i--)
    {
        r = r * 10 + A[i];
        C.push_back(r / b);
        r %= b;
    }
    reverse(C.begin(),C.end());
    while(C.size() > 1 and C.back() == 0) C.pop_back();
    C.push_back(r); // 保存余数
    return C;
}

int main()
{
    vector<int> A;
    string a;
    int b;
    cin >> a >> b;
    for(int i=a.size()-1;i>=0;i--) A.push_back(a[i] - '0');
    vector C = divi(A,b);
    for(int i=C.size()-2;i>=0;i--) cout << C[i]; 
    cout << endl;
    cout << C[C.size()-1];
    
    return 0;
}

前缀和和差分

前缀和：
$S_i = a_1 + a_2 + ... + a_n$
$S_i$ 如何求？
for (int i=0;i<n;i++) S[i]= S[i-1]+a[i]
$S_i$ 的作用是什么？
快速的求出来原数组一段数据的和

/* 一维序列 */
#include <iostream>
using namespace std;

const int N = 1e5  +10;

int n,m;
int a[N],s[N];

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++) s[i] = s[i-1] + a[i]; // 前缀和的初始化
  
  while(m--)
  {
    int l,r;
    scanf("%d%d",&l,&r);
    printf("%d\n",s[r] - s[l - 1]) // 区间和的计算
  }
}

/* 二维前缀和 */

int n;
const int N = 1010;

int n,m,q;
int a[N][N],s[N][N];

int main()
{
  scanf("%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++)
      s[i][j] = s[i-1][j] + s[i][j - 1] - s[i-1][j-1] + a[i][j];
  while(q--)
  {
    int x1,y1,x2,y2;
    scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
    printf("%d\n",s[x2][y2] - s[x1-1][y2#include <iostream>

using namespace std;

int n,m,q;
const int N = 1010;
int a[N][N],s[N][N];

int main()
{
    cin >> 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++)
            s[i][j] = s[i-1][j] + s[i][j-1] - 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;
    }
}] - s[x2][y1-1] + s[x1-1][y1-1]);
    }
}

差分算法可以看做前缀和的逆运算
构造： $b_1$ , $b_2$ , $b_3$ ...
使得： $a_i = b_1 + b_2 + ...$

双指针运算

归并排序就是一个双指针算法
一个双指针算法可以分为两大类：
两个指针指向两个数组
两个指针都指向一个数组
写双指针算法的思路：首先写一个暴力的方法，然后看i和j之间有没有什么方式可以减少时间复杂度

// 最基础的双指针模板
int main()
{
  ...
  for(int i=0,j=m;i<n;i++)
  {
        while(j<n){
      j--
    }
    i++;
  }
}

位运算

c++转换无符号整数：unsigned int x = 100
// 计算一个数字中1的个数
#include <iostream>
using namespace std;
int n,m;

int main() { cin >> n; while(n--) { cin >> m; int a = 0; int b; while(m != 0) { int b = m & 1; // 获取最后一位数 if(b) a++; // 二进制向右移动一位 m >>= 1; } cout << a << " "; } }

## 离散化
> 对于一些特别大的数，可以把这些数`a[i]`映射到从0开始的连续自然数`b[i]`当中，这个映射的过程就称作离散化；
> 
> 离散化中可能遇到的问题：
> 
> 1. 原数组当中可能存在重复的数 -> 去重（使用c++中的库来实现）
> 
> `sort(alls.begin(),alls.end()); // 排序` 
> `alls.erase(unique(alls.begin(), alls.end()), alls.end()); // 去重`
> 
>2.  如何算出`a[i]` 离散化之后的数值 -> 二分
>
    特点：`数值跨度很大，但是用到的数值并不多`

```c++
int main()
{
    // 去重的代码
    sort(alls.begin(),alls.end());
    alls.erase(unique(alls.begin(),alls.end()));
}

// 二分查询的基本模板
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; // 映射到1，2，... n
}

例题: https://www.acwing.com/problem/content/804/

#include <iostrea>
#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 l + 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;
    }
}

美团面试题：格子染色问题

区间合并

将多个区间进行合并 （贪心算法）
将区间按照左端点进行排序
扫描整个区间，扫描过程当中将所有可能有交集的区间进行合并

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef pair<int,int> PII;

const int N = 100010;

int n;
vector<PII> segs;

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;
}

int main()
{
    cin >> n;
    for(int i =0;i<n;i++)
    {
        int l,r;
        cin >> l >> r;
        segs.push_back({l,r});
    }

    merge(segs);
    cout << segs.size() << endl;
}

基础算法

排序​

快排​

归并排序​

二分​

整数二分​

浮数二分​

高精度​

高精度加法​

tip

高精度减法​

tip

大整数乘一个小数​

tip

大整数除以一个较小整数​

tip

前缀和和差分​

双指针运算​

位运算​

区间合并​

排序

快排

归并排序

二分

整数二分

浮数二分

高精度

高精度加法

高精度减法

大整数乘一个小数

大整数除以一个较小整数

前缀和和差分

双指针运算

位运算

区间合并