双指针算法

发表于 2021-08-23 更新于 2021-08-25 分类于基础算法

双指针算法，可以优化一些朴素算法，减少遍历的次数，降低算法的时间复杂度。

一般模板

for (int i = 0, j = 0; i < n; i ++ )
{
    while (j < i && check(i, j)) j ++ ; //指针的移动

    // 具体问题的逻辑
}

常见问题分类：

(1) 对于一个序列，用两个指针维护一段区间
(2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作

例题：最长连续不重复子序列

给定一个长度为 n 的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。

#include <iostream>

using namespace std;

const int N = 100010;

int n;
int a[N], s[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++)	//双指针， i指针先往前
    {
        s[a[i]]++;						//将这个数加入当前i ，j 之间
        while (s[a[i]] > 1)				//如果数量大于1 ， 那么就是有重复的
        {
            s[a[j]]--;					//将重复的T出去
            j++;						//指针右移，直到与i指针重合了，继续开始下一个序列
        }

        res = max(res, i - j + 1);		//记录当前的最大值
    }
    cout << res << endl;
    return 0;
}

例题：[数组元素的目标和](AcWing 800. 数组元素的目标和 - AcWing)

给定两个升序排序的有序数组 A 和 B，以及一个目标值 x。

数组下标从 0 开始。

请你求出满足 A[i] + B[j] = x A[i]+B[j]= x 的数对 (i,j)(i,j)。

数据保证有唯一解。

求目标和的时候双指针一个指向首位，一个指向末尾

#include <iostream>

using namespace std;

const int N = 100010;

int A[N], B[N];
int n, m, x;

int main()
{
    cin >> n >> m >> x;
    for (int i = 0; i < n; i++)
        cin >> A[i];
    for (int i = 0; i < m; i++)
        cin >> B[i];
    for (int i = 0, j = m - 1; i < n; i++) //一个指向首位，一个指向末尾
    {
        while (j >= 0 && A[i] + B[j] > x)	//先用大数， 太大了就用小数。
            j--;							//把一个数组看成大数序列 ，一个数组看成是小数序列
        if (A[i] + B[j] == x)				//输出答案即可
        {
            printf("%d %d", i, j);
            break;
        }
    }
    return 0;
}

前缀和与差分

发表于 2021-08-20 更新于 2021-08-21 分类于基础算法

前缀和

前缀和数组s[ ]，即数列的前 n 项和，作用是快速求出数列中连续一段数字的总和，降低算法复杂度

前缀和的求法很简单，以下只放一小段代码

for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        s[i] = s[i - 1] + a[i];
    }

求其中一小段 l 到 r 中的所有数的和。

s[r] - s[l - 1]

二维前缀和

在一个二维的矩阵中同样可以使用前缀和来简便地计算某一个矩形的和

前缀和数组 s[i][j]表达的意思是以点(i , j)为右下角坐标，以零点为左下角坐标的矩形的和，利用这个定义得出以下代码，是每一个坐标的二维前缀和数组

1	s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j]

利用这个求出任意矩形的和 ( x1 , y1) 和 ( x2 , y2) 确定的矩形的和

1	s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1])

附上一个求子矩阵的模板题及代码

输入一个 n 行 m 列的整数矩阵，再输入 q 个询问，每个询问包含四个整数 x1,y1,x2,y2，表示一个子矩阵的左上角坐标和右下角坐标。对于每个询问输出子矩阵中所有数的和。

#include <iostream>

const int N = 1010;

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

int main()
{
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= n; i++)    //前缀和和差分一般都以1为下标和，方便统一方法
        for (int j = 1; j <= m; j++)
        {
            scanf("%d", &a[i][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] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]); //利用前缀和求目标矩阵的和
    }
    return 0;
}

差分

差分和前缀和是一组逆运算。

计算差分的前缀和就可以得到原数组，计算原数组的前缀和就可以得到前缀和数组

差分就是一个数组中相邻两个数的差值，使用差分可以快速便捷地将数组的某一连续段的每一个全部加上一个相同的值，不需要遍历每一个数。

使用一道例题来解释形式和用法

输入一个长度为 n 的整数序列。

接下来输入 m 个操作，每个操作包含三个整数 l,r,c l,r,c，表示将序列中 [l,r][l,r] 之间的每个数加上 c。

请你输出进行完所有操作后的序列。

#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int a[N], b[N]; //定义数组和差分数组
int n, m;

void insert ( int l , int r , int c) //插入操作，作用有二
{									 //一   初始化差分数组，相当于把每一个数插入全部为0的数组
    b[l] += c ;						 //二   插入，使某段 l r 之间的所有数都加上 c
    b[r + 1] -= c ;					 //原理： 将l处的差分加上一个数，使用差分的前缀和计算原数组的时候，l后的所有数都加上c
}									 //		  将 r+1 处的差分减去 c 抵消了后续所有数加上的 c ， 保持不变
									 //       最终达到只在此段全部加 c 的目标

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);			////初始化差分数组
        insert( i , i, a[i]);
    }

    while( m --)
    {
        int l , r , c ;
        scanf("%d%d%d" , &l , &r , &c);//进行插入
        insert( l , r, c);
    }

    for ( int i = 1; i <= n ; i++) //对差分进行前缀和求原数组
    {
        b[i] += b[i - 1];		
        printf( "%d " , b[i]);
    }
    return 0;
}

二维差分（差分矩阵）

改变二维差分的意义：以此坐标为左上角确定的矩阵中所有数都加或减去 c ，

实现方法与二维前缀和相似，加加减减的。似乎有容斥原理的思想。

代码模板：

#include <iostream>

const int N = 1010;

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

void insert(int x1, int y1, int x2, int y2, int c)
{
    b[x1][y1] += c;								//右下角全加
    b[x1][y2 + 1] -= c;							//减去两个长方形
    b[x2 + 1][y1] -= c;
    b[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]);
            insert(i, j, i, j, a[i][j]);	//初始化差分数组
        }

    while (q--)
    {
        int x1, x2, y1, y2, c;
        scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c); //进行q次操作
        insert(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];//使用差分的前缀和计算原数组
            printf("%d ", b[i][j]);
        }
        printf("\n");
    }

    return 0;
}

C++高精度算法

发表于 2021-08-17 更新于 2021-08-18 分类于基础算法

大整数的存储方式

大整数以数组的方式储存，把每一位都存进数组，把个位存进低位数组，即倒着存。目的是方便进位，只需在数组后面再添加一个元素即可。

高精度加法

模拟加法运算的竖式，两个数组中的数分别相加，定义一个变量来模拟进位

加法模板

#include <iostream>
#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++)
    {
        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;
    cin >> a >> b;
    vector<int> 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');
    auto C = add(A, B);						//auto 关键字，自动识别类型

    for (int i = C.size() - 1; i >= 0; i--) //反向输出
        printf("%d", C[i]);

    return 0;
}

高精度减法

减法同样是遵循竖式运算的方式，相较于加法，需要处理的点从进位变成了借位

需要注意的点

借位的实现方法。
保证是大数减去小数，所以减之前要先判断两个数的大小
减完之后注意处理前缀零，比如 199 - 198 = 001 ，最后的答案要把前面的零除掉。

减法模板

#include <iostream>
#include <vector>

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;							//全都一样，大小相等，0，不用加负号
}

vector<int> sub(vector<int> &A, vector<int> &B)
{		
    vector<int> C;							//定义一个每个循环开始的时候值是0或1的t来表示借位
    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);			//(t + 10) % 10可以同时处理借位与不借位的情况
        if (t < 0)							//标记是否借位了
            t = -1;
        else
            t = 0;
    }

    while (C.size() > 1 && C.back() == 0)	//如果不是只有一位 0 ，且前导有的时，去掉前导零
        C.pop_back();

    return C;
}
int main()
{
    string a, b;								//输入大数与储存
    cin >> a >> b;
    vector<int> 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))								//判断两个数的大小，决定用谁减谁
    {
        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]);
    }
    return 0;
}

高精度乘法

这里的高精度乘法指的是一个大数乘一个小数，并不是一个大数乘一个大数。

同样的模拟竖式的乘法。和加法是类似进位机制。

代码模板

#include <iostream>
#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() || 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;
}

int main()
{
    string a;
    int b;
    cin >> a >> b;
    vector<int> A;
    for (int i = a.size() - 1; i >= 0; i--)
        A.push_back(a[i] - '0');
    auto C = mul(A, b);
    for (int i = C.size() - 1; i >= 0; i--)
        printf("%d", C[i]);
    return 0;
}

高精度除法

同样是一个高精度的数除以一个低精度的数

同样是模拟竖式计算除法的每一步

代码模板如下

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

using namespace std;

vector<int> div(vector<int> &A, int b, int &r)
{
    vector<int> C;
    r = 0;
    for (int i = A.size() - 1; i >= 0; i--)
    {
        r = r * 10 + A[i];						//每一次除完接下一位数，即余数 *10 ，加上下一位数
        C.push_back(r / b) ;					//上商
        r %= b;									//得余数

    }

    reverse( C.begin() , C.end());				//因为C队列里的数是正向排进的，为了与一般储存习惯相同，将其反向一下。

    while (C.size() > 1 && C.back() == 0)		//去掉前导零
        C.pop_back();

    return C;
}

int main()
{
    string a;
    int b;
    cin >> a >> b;
    vector<int> A;
    for (int i = a.size() - 1; i >= 0; i--)
        A.push_back(a[i] - '0');
    int r;									//除法还要多一个余数
    auto C = div(A, b, r);
    for (int i = C.size() - 1; i >= 0; i--)
        printf("%d", C[i]);
    printf( "\n") ; 
    printf( "%d" , r);
    return 0;
}

二分模板（坑）

发表于 2021-08-16 更新于 2021-08-17 分类于基础算法

二分法又可以分为整数二分和实数二分

整数二分

使用二分的目的是寻找到某一个符合要求的数，因为数量的庞大，不可能把整个数组全部都遍历，所以使用二分来减少算法的复杂度。

基本思路

在一个区间的内部，来寻找边答案所在的区间，在这个区间里面继续缩小区间。
当区间的长度是一的时候区间里面的就是所求的答案
二分模板一定是有解的，（即定义的性质一定是有边界的），但是不一定是题目需求的答案，这时根据题目判断有没有解。

简单来说
假设目标值在闭区间中，[l, r] 每次将区间长度缩小一半，当l = r时，我们就找到了目标值。

下面就是两种模板：
1. 当我们将区间[l, r]划分成[l, mid]和[mid + 1, r]时，其更新操作是r = mid或者l = mid + 1;，计算mid时不需要加1。
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  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;
  }
2. 当我们将区间[l, r]划分成[l, mid - 1]和[mid, r]时，其更新操作是r = mid - 1或者l = mid;，此时为了防止死循环，计算mid时需要加1。
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  int bsearch_2(int l, int r)
  {
  while (l < r)
  {
  int mid = l + r + 1 >> 1;
  if (check(mid)) l = mid;
  else r = mid - 1;
  }
  return l;
  }
  记住这两个模板就可以应对基本所有的二分题目了
浮点数的二分
浮点数的二分比整数的二分简单，不用考虑边界设置导致的死循环

唯一需要注意的是结束二分的条件的改变。

从l == r变为判断浮点数的差值 r - l < 1e-6

注意：
一般设置判断差值的时候将，设置为比题目要求更往后的两位，来保证答案的准确性。

代码模板：
1
2
3
4
5
6
7
8
9
10
int bsearch_1(int l, int r)
{
while ( r - l < 1e-6)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid ;
}
return l;
}

归并排序

发表于 2021-08-15 更新于 2021-08-23 分类于基础算法

基本思路

归并排序，即通过先递归再排序的方法来实现排序。

将一组数从中间分为两组，分别进行递归
在不断的分组中，最终每一组都被分割为只有一个数，可以看作是本组完成了排序
递归之后一步步将每一组合并
合并的过程中使用双指针算法，取两个指针，分别指向要合并的两个组的开头，比较指针所指数的大小，将较小的放入临时数组 t m p [ ] , 并且指针向后移动，以此类推，放完一个，再将剩下的一组直接全部放入 t m p[ ]。
最后将已经完成排序的临时数组放入最终数组的相应位置

代码实现模板

#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int n;
int q[N];
int 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++];                   //把较大组剩下的都排进去

    for (int i = l, j = 0; i <= r; i++, j++) //l是这个组的开始，把这个组的tmp都塞进去。
        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]);

    return 0;
}

应用例题：逆序对的数量

逆序对：一个数组中，下标 i ， j 两个数，满足：i < j 且 a[ i ] > a[ j ]

用归并排序的过程完成逆序对数量的计算。

进行归并操作时 , 其中一个判断正好符合逆序的定义

while (i <= mid && j <= r)              //两组指针指着的数谁大就把谁塞进去。
       if (q[i] <= q[j])
           tmp[k++] = q[i++];
       else
       { 	
           tmp[k++] = q[j++]； 			//如果q[i] > q[j] ,满足逆序对的定义
          	res += mid - i + 1;			//那么从i 到 mid 的所有数都比 q[j] 要大，加上那么多的数量。
       }

快速排序

发表于 2021-08-15 更新于 2021-08-17 分类于基础算法

快速排序

基本思路

确认基准点 X
调整顺序
使用递归处理左右两端

找到一个基准点X，一般取这一组数中间位置的，可以减少算法的复杂度。
调整基准点左右两边的数，左边比它小，右边比它大。
然后使用递归分别对左右两边再进行一二两步

实现顺序调整的方法

使用两个指针分别指向左右两端 i j

移动左边的 i，直到遇到第一个大于等于X的数停下

移动右边的 j，直到遇到第一个小于等于X的数停下

交换两个指针所指的数，实现 i 左边 <=X , j 右边 >= X

交换完成后继续进行以上步骤，直到 i >= j ,实现顺序交换

代码模板实现

#include <iostream>

using namespace std;

const int N = 1e6 + 10 ;
 
int q[N];
int n ; 

void quick_sort( int q[] , int l , int r )
{
    if (l >= r)					//排序完成，退出函数
        return; 
    int x = (q[l]+q[r]) /2;		//设置基准点
    int i = l -1 ;
    int j = r + 1 ;
    while( i < j )				//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()
{
    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]);
    
    return 0;
        
}

引申：快速选择算法

给定一个长度为 n 的整数数列，以及一个整数 k，请用快速选择算法求出数列从小到大排序后的第 k 个数。

#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int n , k;
int q[N];

int quick_sort( int l, int r, int k )					//直接返回第k个数值
{
    if (l == r)     return q[l];						//相当于只有一个数字了，直接返回就可以了

    int x = (q[l] + q[r]) / 2, 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]);
    }
    
    int sl = j- l +1;									//计算 左边的数字数目, 与k比较
    
    if( sl >= k)
    return  quick_sort( l, j, k );						//数目 大于 等于 k ， 只需要对左边进行递归就可以了
    											
    return  quick_sort( j + 1, r , k-sl);				//小于 k ， 则对右边进行递归
    
}

int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++)
        scanf("%d", &q[i]);
        
    printf("%d", quick_sort( 0, n - 1,k));
    return 0;
}

时间复杂度比直接快排要低。

建站之初

发表于 2021-08-14 更新于 2021-08-15 分类于分类标签测试类

这个简陋的个人网站的搭建过程和搭建目的

一。搭建目的

不知不觉大学的生活已经完完整整的过去了一年，回顾下这一年都学到了什么东西。似乎不能完全的表达出来。就是一种，好像学了但是并没有什么收获的感觉。在自己学过的一些内容中不乏牺牲考试课程而投入了时间。

想来，这是没有记录和复习的缘故，对于本专业的内容来说，记在纸质笔记本上显然是不合适的，markdown的语法记录才是最合适的方法。

想要随时对自己的笔记进行查看和复习，只保存在本地的文件显然是不能满足这个要求的。一个个人博客网站是最佳的解决方案。

二。搭建过程

查阅了很多教程，最终选择了较为简单的方式，使用GitHub page + Hexo的进行博客的搭建，现在已经有了初步的基本功能，将来会进行美化和完善。

Hexo 是一个部署个人博客的工具，为了一个比较好记的网站，而不是GitHub.io的网址，另购买了本站的snowdawn.top 的域名。原本的设想是.com为结尾的域名，但是比top贵了好多。

三。展望

希望这个花了心思搭建的网站会是我大学学习过程中最好的见证与记录。它的页面也一定会越来越美好。

献给未来

Hello World

发表于 2021-08-12 更新于 2021-08-15 分类于分类标签测试类

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1	$ hexo new "My New Post"

More info: Writing

Run server

1	$ hexo server

More info: Server

Generate static files

1	$ hexo generate

More info: Generating

Deploy to remote sites

1	$ hexo deploy

More info: Deployment

一般模板

常见问题分类：

例题： 最长连续不重复子序列

例题：[数组元素的目标和](AcWing 800. 数组元素的目标和 - AcWing)

前缀和

二维前缀和

差分

二维差分（差分矩阵）

大整数的存储方式

高精度加法

加法模板

高精度减法

需要注意的点

减法模板

高精度乘法

代码模板

高精度除法

代码模板如下

二分法又可以分为整数二分和实数二分

整数二分

基本思路

简单来说

浮点数的二分

注意：

基本思路

代码实现模板

应用例题：逆序对的数量

快速排序

基本思路

实现顺序调整的方法

代码模板实现

引申：快速选择算法

时间复杂度比直接快排要低。

这个简陋的个人网站的搭建过程和搭建目的

一。搭建目的

二。 搭建过程

三。 展望

献给未来

Quick Start

Create a new post

Run server

Generate static files

Deploy to remote sites

例题：最长连续不重复子序列

二。搭建过程

三。展望