0%

单调栈

即栈内的元素是有某种单调性的。

用于求特定问题的解。

作用情景

[求一个数列的每个数的左边第一个比它小的数字](830. 单调栈 - AcWing题库)

要求左边第一个比它小的数,那么在之前每一个数入栈的时候就进行判断,只将满足递减单调性的数据存入,其余的弹出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>

using namespace std;

const int N = 100010;

int stk[N], tt;

int main()
{
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
int x;
scanf("%d", &x);
//如果栈是非空的,且栈顶元素不比要入栈的元素小,将栈顶弹出,以形成单调栈
while (tt && stk[tt] >= x)
tt--;
//形成单调栈以后的栈顶就是要找的第一个比要入栈元素小的值
if (tt)
printf("%d ", stk[tt]);
else
printf("-1 ");
//最后将这个元素入栈
stk[++tt] = x;
}
return 0;
}

优先队列

与单调栈的定义类似,优先队列里的元素是按照某种单调性排列的。

使用优先队列可以简化特定要求的与队列有关的问题。

作用情景

[滑动窗口](154. 滑动窗口 - AcWing题库)

一组数据

给定一个大小为 k的窗口,从数组的头开始滑动,窗口里最多只能同时存在k个数。

求每次滑动时,窗口里的最大值和最小值。

与优先队列的处理方式类似,只将满足单调性的元素从队尾入队,不满足的 从队尾出队

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>

using namespace std;

const int N = 1000010;

int n, k;
//a[N]数组中存储要处理的数组,q[N]数组中存储队列里的数在a[N]数组里的下标
int a[N], q[N];

int main()
{
scanf("%d%d", &n, &k);
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
//定义队头和队尾
int hh = 0, tt = -1;
for (int i = 0; i < n; i++)
{
//使用 i - k + 1 来控制队列(滑动窗口)中的元素数量,每当队列中的元素超出k, 就把队头元素出队
if (hh <= tt && q[tt] - k + 1 > q[hh])
hh++;
//要入队的元素要比队列中的所有元素都要大
while (hh <= tt && a[q[tt]] >= a[i])
tt--;
q[++tt] = i;
if (i >= k - 1)
//队头的元素永远是最小的
printf("%d ", a[q[hh]]);
}
printf("\n");
//找最大值与最小值方法一样,改变入队的限制即可
hh = 0, tt = -1;
for (int i = 0; i < n; i++)
{
if (hh <= tt && i - k + 1 > q[hh])
hh++;
//要入队的元素要比队列中的所有元素都小
while (hh <= tt && a[q[tt]] <= a[i])
tt--;
q[++tt] = i;
if (i >= k - 1)
printf("%d ", a[q[hh]]); //输出队头的最大元素
}
return 0;
}

总结

单调栈和优先队列的使用是为了满足特定集中情况下的算法需求,应用的场景比较有限

通常的使用场景是:

某个问题使用到了栈和队列的结构,但是朴素算法的遍历的复杂度太高,单调栈和优先队列可以优化栈和队列,使其具有一定的单调性,降低解决这些问题的复杂度。

队列

一个线性表,在一端放入数据,在另一端弹出数据,先放入的数据先弹出。

与链表的实现方式基本相同

数组模拟的队列的基本操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>

using namespace std;

const int N = 100010;

//将tail设为-1 , 这样在插入了一个数的时候,队头head 就是 tail 队列长度是1
int queue[N], head, tail = -1;

//在队尾插入元素,在队头弹出元素

void push(int x)
{
queue[++tail] = x;
}

string ifempty()
{
if (head > tail)
return "YES";
else
return "NO";
}

void pop()
{
//指针移动,队头的元素相当于被切掉了
head++;
}

int query()
{
return queue[head];
}

int main()
{
int m;
cin >> m;
string op;
while (m--)
{
cin >> op;
if (op == "push")
{
int x;
cin >> x;
push(x);
}
else if (op == "pop")
{
pop();
}
else if (op == "empty")
{
cout << ifempty() << endl;
}
else
cout << query() << endl;
}
return 0;
}

只能从一头进出的线性表

最后被放入的必须最先被取出

数组模拟栈的基本操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>

using namespace std;

const int N = 100010;

int stk[N], k;

void push(int x)
{
stk[++k] = x;
}

string ifempty()
{
if (k <= 0)
return "YES";
else
return "NO";
}

void pop()
{
k--;
}

int query()
{
return stk[k];
}

int main()
{
int m;
cin >> m;
string op;
while (m--)
{
cin >> op;
if (op == "push")
{
int x;
cin >> x;
push(x);
}
else if (op == "pop")
{
pop();
}
else if (op == "empty")
{
cout << ifempty() << endl;
}
else
cout << query() << endl;
}
return 0;
}

挺简单的,随便记录一下。

双链表

与单链表相比,区别是:
双链表的每一个节点都有对应的前驱和后继。

可以完成一些单链表无法完成的任务。

[基础的双链表操作](827. 双链表 - AcWing题库)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <iostream>

using namespace std;

const int N = 100010;

int e[N], l[N], r[N], idx;

void init()
{
//将0 , 1 分别设为头节点和尾部节点
l[1] = 0;
r[0] = 1;
idx = 2;
}

//向插入的第k个数后面插入一个数
//也可以通过将参数k 改为l[k]来实现向k的左边插入一个数
void add(int k, int x)
{
e[idx] = x;
l[idx] = k;
r[idx] = r[k];
l[r[k]] = idx;
r[k] = idx;
idx++;
}

//移去第k个插入的数
void remove(int k)
{
r[l[k]] = r[k];
l[r[k]] = l[k];
}

int main()
{
init();
int m;
cin >> m;
string op;
while (m--)
{
cin >> op;
if (op == "L")
{
//向头节点的后面添加一个数,就是在最前面加上一个数
int x;
cin >> x;
add(0, x);
}
else if (op == "R")
{
//向尾节点前面一个数的后面加一个数,就是在最后加上一个数
int x;
cin >> x;
add(l[1], x);
}
else if (op == "D")
{
//删去第k个插入的数
int x;
cin >> x;
remove(x + 1);
//第一个插入的数的下标是2 ,因为将 1 定义为了末尾
}
else if (op == "IL")
{
//在第k个插入的数前面插入一个数
int k, x;
cin >> k >> x;
add(l[k + 1], x);
//在第k个左边的右面插入,就是在k的左边插入
}
else
{
int k, x;
cin >> k >> x;
add(k + 1, x);
}
}
for (int i = r[0]; i != 1; i = r[i])
cout << e[i] << " ";
return 0;
}

数组模拟单链表(静态链表)

链表

数据对象的存储结构可以分为两种:0顺序存储结构和链式存储结构

顺序存储结构要求所有的元素依次存放在一片连续的存储空间中

链式存储结构无需占用一整块存储空间,但是为了表示节点之间的关系,需要给每一个节点附加指针字段,用于存放后继元素的存储地址。

单链表的数组模拟实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <iostream>

using namespace std;

const int N = 100010;

//e[N] : 当前节点的值
//ne[N] : 当前节点指向的下一个节点下标
//head :头节点指向的节点的下标
//idx :当前插入了几个 ,也就是最新节点的插入次序
int e[N], ne[N], head, idx;

//整个结构的初始化
void init()
{
//head 开始时指向空,表示为-1
head = -1;
//已经插入了零个数据
idx = 0;
}
//向头节点后面插入数据
void add_to_head(int x)
{
e[idx] = x;
ne[idx] = head;
head = idx;
idx++;
}

//向第k个插入的数据后面插入一个数据
void add(int k, int x)
{
e[idx] = x;
ne[idx] = ne[k];
ne[k] = idx;
idx++;
}

//移除第k个插入的数据后面的一个数据
void remove(int k)
{
ne[k] = ne[ne[k]];
}

int main()
{
init();
int m;
cin >> m;
while (m--)
{
int x, k;
char op;
cin >> op;
if (op == 'H')
{
cin >> x;
add_to_head(x);
}
else if (op == 'D')
{
cin >> k;
// k为0的时候的特判
if (k == 0)
head = ne[head];
//下表是从0开始的,所有第k个的下标是k - 1
remove(k - 1);
}
else
{
cin >> k >> x;
add(k - 1, x);
}
}
for (int i = head; i != -1; i = ne[i])
cout << e[i] << ' ';

return 0;
}

单链表的局限性

单链表不能在链表的任意位置插入一个数据,因为单链表只能找到某一个数据的后继,而不能找到一个数据的前导。

要解决这一个问题,要使用到双链表。

概念

在一个很大的范围内 , 只有 很小的数据容量。

使用离散化,将这些数据 存储在从 1 开始的数组里 , 再进行后续的处理。


处理方法

  • 将输入的 值存入动态数组 vector
  • 将所有的值排序
  • 储存进数组的值相当于坐标 , 所以要进行去重的操作,方便后续的使用和处理。
  • 编写一个find()函数,用于找到原数据对应的离散化之后的数据位置(动态数组中的位置)
  • 根据题目的逻辑进行相应的 操作。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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
}

模板例题

[求区间和](802. 区间和 - AcWing题库)

假定有一个无限长的数轴,数轴上每个坐标上的数都是 0。

现在,我们首先进行 n 次操作,每次操作将某一位置 xx 上的数加 c。

接下来,进行 m 次询问,每个询问包含两个整数 l 和 r,你需要求出在区间 [l ,r] 之间的所有数的和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 300010; //数据范围限制,可能有 1e5 个add , 和 2e5 个坐标

int n, m;
int a[N], s[N]; //相应坐标的数据,和最后求和时使用的前缀和

vector<int> alls; //存储所有数据
vector<PII> add, query; //两个操作,使用pair<int,int>存储一次操作中的两个参数

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}); //存储add操作
alls.push_back(x); //存储原数据
}

for (int i = 0; i < m; i++) //存储query操作
{
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) //处理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) //处理query询问操作
{
int l, r;
l = find(item.first), r = find(item.second);//获取离散化后坐标
cout << s[r] - s[l - 1] << endl; //利用前缀和求值输出
}

return 0;
}

lowbit( )

作用: 获取一个二进制数的 最后一位 1 及以后的数

1
2
3
4
int lowbit()
{
return x & -x;
}

例题:[二进制中 1 的个数](801. 二进制中1的个数 - AcWing题库)

给定一个长度为 n的数列,请你求出数列中每个数的二进制表示中 1 的个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>

using namespace std;

int n ;

int lowbit( int x)
{
return x & -x; //实现方法:x 与运算 x 的取反
}

int main( )
{
cin >> n ;
for ( int i = 0 ; i < n ; i++)
{
int x ;
cin >> x ;
int res = 0 ;
while (x)
{
x -= lowbit(x); //把最后一位1 及以后的都减去
res ++ ; //计数加一
} //重复
cout << res << ' ' ;
}
return 0 ;
}

求n的第k位数字(二进制)

n >> k & 1

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

一般模板

1
2
3
4
5
6
for (int i = 0, j = 0; i < n; i ++ )
{
while (j < i && check(i, j)) j ++ ; //指针的移动

// 具体问题的逻辑
}

常见问题分类:

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


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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#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)

数据保证有唯一解。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#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;
}

前缀和

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

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

1
2
3
4
5
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,表示一个子矩阵的左上角坐标和右下角坐标。对于每个询问输出子矩阵中所有数的和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#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。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#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 ,

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

代码模板:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#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;
}

大整数的存储方式

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


高精度加法

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

加法模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#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;
}


高精度减法

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

需要注意的点

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

减法模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#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;
}


高精度乘法

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

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

代码模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#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;
}

高精度除法

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

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

代码模板如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#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;
}