Sky's blog

保研机试C++算法复习

Word count: 8,717 / Reading time: 46 min
2018/06/13 Share

前言

即便我很讨厌c++和算法,但是我没有办法,只能硬着头皮的学,为了保研,也为了成长。
本文持续更新

标准模板库中的相应模板——优先队列

1
2
#include<queue>
using namespace std;

利用语句

1
priority_queue<int> Q

即创建一个保存元素为int的堆Q,但是堆其默认为大顶堆
创建小顶堆

1
priority_queue<int,vector<int>,greater<int>> Q

有关堆的操作

1
2
3
Q.push(x)
Q.top()
Q.pop()

堆会自动调整为小顶堆

哈夫曼树

题目

1
2
哈夫曼树,第一行输入一个数n,表示叶结点的个数。需要用这些叶结点生成哈夫曼树。
根据哈夫曼树的概念,这些结点有权值,即weight,题目需要输出所有结点的值与权值的乘积之和。

输入

1
2
5  
1 2 2 5 9

输出

1
37

代码如下

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>
#include<queue>
using namespace std;

int main()
{
priority_queue<int,vector<int>,greater<int> > Q;
int n;
while(cin>>n)
{
for(int i=0;i<n;i++)
{
int tmp;
cin>>tmp;
Q.push(tmp);
}
int sum=0;
while(Q.size()>=2)
{
int a=Q.top();
Q.pop();
int b=Q.top();
Q.pop();
sum +=(a+b);
Q.push(a+b);
}
cout<<sum<<endl;
}
}

二叉排序树

二叉树结点基本结构

1
2
3
4
5
struct Node{
Node *lchild;
Node *rchild;
char c; //结点的值
};

根据前序+空值结果生成二叉树

例如:

1
abc##de#g##f###

代码如下

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
#include<iostream>
using namespace std;
int len;
string x;
struct Node
{
Node *lchild;
Node *rchild;
char c;
} Tree[110];

void createTree(Node *&T)
{
if(len == x.length())return;
char ch = x[len];
len++;
if(ch=='#'){
T = NULL;
}
else{
T = new Node;
T->c = ch;
createTree(T->lchild);
createTree(T->rchild);
}
}

int main()
{
while(cin>>x)
{
len = 0;
Node *T=NULL;
createTree(T);
}
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
#include<iostream>
#include<string.h>
using namespace std;

struct Node
{
Node *lchild;
Node *rchild;
char c;
} Tree[110];

int loc;
Node *create()
{
Tree[loc].lchild=Tree[loc].rchild=NULL;
return &Tree[loc++];
}
char str1[30],str2[30];
Node *build(int s1,int e1,int s2,int e2)
{
Node *ret=create();
ret->c=str1[s1];
int rootIdx;
for(int i=s2;i<=e2;i++)
{
if(str2[i] == str1[s1])
{
rootIdx = i;
break;
}
}
if(rootIdx != s2)
{
ret->lchild=build(s1+1,s1+(rootIdx-s2),s2,rootIdx-1);
}
if(rootIdx != e2)
{
ret->rchild=build(s1+(rootIdx-s2)+1,e1,rootIdx+1,e2);
}
return ret;
}

int main()
{
while(cin>>str1)
{
cin>>str2;
loc=0;
int L1=strlen(str1);
int L2=strlen(str2);
Node *T = build(0,L1-1,0,L2-1);
}
return 0;
}

前序遍历

1
2
3
4
5
6
void postOrder(Node *T)
{
cout<<T->c<<" ";
if(T->lchild!=NULL) postOrder(T->lchild);
if(T->rchild!=NULL) postOrder(T->rchild);
}

中序遍历

1
2
3
4
5
6
void postOrder(Node *T)
{
if(T->lchild!=NULL) postOrder(T->lchild);
cout<<T->c<<" ";
if(T->rchild!=NULL) postOrder(T->rchild);
}

后序遍历

1
2
3
4
5
6
void postOrder(Node *T)
{
if(T->lchild!=NULL) postOrder(T->lchild);
if(T->rchild!=NULL) postOrder(T->rchild);
cout<<T->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
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
86
87
#include<iostream>
using namespace std;
bool flag = false;
struct Node
{
Node *lchild;
Node *rchild;
int c;
} Tree[110];

int loc;
Node *create()
{
Tree[loc].lchild=Tree[loc].rchild=NULL;
return &Tree[loc++];
}

void postOrder(Node *T)//后序遍历
{
if(T->lchild!=NULL) postOrder(T->lchild);
if(T->rchild!=NULL) postOrder(T->rchild);
if(flag) cout<<" ";
cout<<T->c;
flag = true;
}

void inOrder(Node *T)//中序遍历
{
if(T->lchild!=NULL) inOrder(T->lchild);
if(flag) cout<<" ";
cout<<T->c;
flag = true;
if(T->rchild!=NULL) inOrder(T->rchild);

}
void preOrder(Node *T)//前序遍历
{
if(flag) cout<<" ";
cout<<T->c;
flag = true;
if(T->lchild!=NULL) preOrder(T->lchild);
if(T->rchild!=NULL) preOrder(T->rchild);
}

Node *Insert(Node *T,int x)
{
if(T==NULL)
{
T=create();
T->c=x;
return T;
}
else if(x<T->c)
{
T->lchild=Insert(T->lchild,x);
}
else if(x>T->c)
{
T->rchild=Insert(T->rchild,x);
}
return T;
}

int main()
{
int n;
while(cin>>n)
{
loc=0;
Node *T=NULL;
for(int i=0; i<n; i++)
{
int x;
cin>>x;
T=Insert(T,x);
}
preOrder(T);//前序遍历
cout<<endl;
flag = false;
inOrder(T);//中序遍历
cout<<endl;
flag = false;
postOrder(T);//后序遍历
cout<<endl;
}
return 0;
}

一些伪二叉树

1.题目描述

1
2
由正整数1,2,3……组成了一颗特殊二叉树。我们已知这个二叉树的最后一个结点是n。现在的问题是,结点m所在的子树中一共包括多少个结点。     
比如,n = 12,m = 3那么上图中的结点13,14,15以及后面的结点都是不存在的,结点m所在子树中包括的结点有3,6,7,12,因此结点m的所在子树中共有4个结点。

输入

1
3 12

输出

1
4

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using namespace std;
int res=0;
void add(int a,int last)
{
if(a>last) return;
res++;
add(2*a,last);
add(2*a+1,last);
}

int main()
{
int n,m;
while(cin>>n>>m)
{
add(n,m);
cout<<res<<endl;
res=0;
}
}

2.题目描述

1
2
3
如上图所示,由正整数 1, 2, 3, ...组成了一棵无限大的二叉树。从某一个结点到根结点(编号是1的结点)都有一条唯一的路径,比如从5到根结点的路径是(5, 2, 1),从4到根结点的路径是(4, 2, 1),从根结点1到根结点的路径上只包含一个结点1,因此路径就是(1)。
对于两个结点x和y,假设他们到根结点的路径分别是(x1, x2, ... ,1)和(y1, y2,...,1),那么必然存在两个正整数i和j,使得从xi 和yj 开始,有xi = yj,xi + 1 = yj + 1,xi + 2 = yj + 2,...
现在的问题就是,给定x和y,要求他们的公共父节点,即xi(也就是 yj)。

输入

1
4 10

输出

1
2

代码如下

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
#include<iostream>
#include<math.h>
#include<algorithm>
using namespace std;

bool issamefloor(int a,int b)
{
int floor_a = (int)(log(a)/log(2));
int floor_b = (int)(log(b)/log(2));
if(floor_a == floor_b) return true;
else return false;
}

int main()
{
int a,b;
while(cin>>a>>b)
{
int min_num = min(a,b);
int max_num = max(a,b);
while(!issamefloor(min_num,max_num))
{
max_num /=2;
}
while(min_num!=max_num)
{
min_num /=2;
max_num /=2;
}
cout<<min_num<<endl;
}
}

大数运算

大数运算之加法

思路就是从后往前,每位相加,进位的数除10存储,下次相加,取余10的数存入栈中,最后出栈即可

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<bits/stdc++.h>
using namespace std;

int main()
{
string a,b;
while(cin>>a>>b)
{
int a_len=a.length();
int b_len=b.length();
stack<int> res;
int max_len = max(a_len,b_len);
int index=0;
int carry = 0;
int a_len_tmp = a_len;
int b_len_tmp = b_len;
while(index<max_len)
{
int a_num=0;
int b_num=0;
if(a_len_tmp>=1) a_num = (int)(a[a_len_tmp-1]-'0');
if(b_len_tmp>=1) b_num = (int)(b[b_len_tmp-1]-'0');
int tmp_res = a_num+b_num+carry;
if(tmp_res>=10)
{
carry = tmp_res/10;
}
else carry = 0;
res.push(tmp_res%10);
a_len_tmp--;
b_len_tmp--;
index++;
}
while(!res.empty())
{
cout<<res.top();
res.pop();
}
cout<<endl;
}
}

大数运算之乘法

简答的模拟手算乘法即可
代码如下

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 <algorithm>
using namespace std;

int num1[1000];
int num2[1000];
int res[1000];

int main()
{
string num_a,num_b;
while(cin>>num_a>>num_b)
{
int a_len = num_a.length();
int b_len = num_b.length();
int res_len = a_len+b_len;
for(int i=0;i<a_len;i++) num1[i]=num_a[i]-'0';
for(int i=0;i<b_len;i++) num2[i]=num_b[i]-'0';
for(int i=0;i<res_len;i++) res[i]=0;
for(int i=0;i<a_len;i++)
{
for(int j=0;j<b_len;j++)
{
res[i+j+1] += num1[i]*num2[j];
}
}
for(int i=res_len;i>=1;i--)
{
res[i-1] += res[i]/10;
res[i] = res[i]%10;
}
int w;
for(w=0;w<res_len;w++)
{
if(res[w]==0) continue;
else break;
}
for(int i=w;i<res_len;i++) cout<<res[i];
cout<<endl;
}
}

大数运算之除法(大数/小数)

也是简单的模拟除法手算即可
这里可常见于大数的进制转换,因子计算等
小数的意思为:可以用long long以内的类型表示的数
代码如下

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
#include <iostream>
#include <string>
#include <stack>
using namespace std;

stack<int> res;

int main()
{
string num;
int a;
while(cin>>num>>a)
{
int num_len = num.length();
int mod = 0;
for(int i=0;i<num_len;i++)
{
int now_num = num[i]-'0';
if(mod*10+now_num<a)
{
mod = mod*10+now_num;
res.push(0);
}
else
{
res.push((mod*10+now_num)/a);
mod = (mod*10+now_num)%a;
}
}
long long ans=0;
long long bei=1;
while(!res.empty())
{
ans += res.top()*bei;
bei *= 10;
res.pop();
}
cout<<ans<<endl;
}
}

当然这里只是大体思路,因为这里的结果可能也是大数,最好用数组进行存储

大整数的因子

这里题目可能也帮助我们简化了,只需要大整数去除2~9即可,查看是否可以整除即可
方法也很简单,只要看最后的余数是否为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
#include <iostream>
#include <string>
#include <stack>
using namespace std;
int res[10];

int main()
{
string num;
for(int i=0;i<10;i++) res[i]=0;
while(cin>>num)
{
int res_index=0;
int num_len=num.length();
int index = 0;
for(int k=2;k<=9;k++)
{
int mod=0;
for(int i=0;i<num_len;i++)
{
int now_num = num[i]-'0';
if(mod*10+now_num<k) mod=mod*10+now_num;
else mod = (mod*10+now_num)%k;
}
if(mod == 0)
{
res[index] = k;
index++;
}
}
if(index==0) cout<<"none"<<endl;
else
{
for(int i=0;i<index;i++)
{
if(i!=0) cout<<" ";
cout<<res[i];
}
cout<<endl;
}
}
}

进制转换

详细算法解释
https://blog.csdn.net/jaster_wisdom/article/details/52107785
看完感觉很强的操作,设计的很好
代码如下

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
#include<iostream>
#include<string>
using namespace std;
int input[1000];
int bits[5000];

int main()
{
string num;
while(cin>>num)
{
int num_len = num.length();
for(int i=0;i<num_len;i++) input[i]=num[i]-'0';
int sum=1;
int d=0;
int bits_index = 0;
while(sum)
{
sum=0;
for(int i=0;i<num_len;i++)
{
d=input[i]/2;
sum+=d;
if(i==num_len-1) bits[bits_index++]=input[i]%2;
else input[i+1] += (input[i]%2)*10;
input[i]=d;
}
}
for(int i=bits_index-1;i>=0;i--) cout<<bits[i];
cout<<endl;
}
}

10进制 VS 2进制

同理,代码如下

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
#include<iostream>
#include<string>
using namespace std;
int input[1000];
int bits[5000];

int main()
{
string num;
while(cin>>num)
{
int num_len = num.length();
for(int i=0;i<num_len;i++) input[i]=num[i]-'0';
int sum=1;
int d=0;
int bits_index = 0;
while(sum)
{
sum=0;
for(int i=0;i<num_len;i++)
{
d=input[i]/2;
sum+=d;
if(i==num_len-1) bits[bits_index++]=input[i]%2;
else input[i+1] += (input[i]%2)*10;
input[i]=d;
}
}
sum=1;
d=0;
int input_index = 0;
while(sum)
{
sum=0;
for(int i=0;i<bits_index;i++)
{
d=bits[i]/10;
sum+=d;
if(i==bits_index-1) input[input_index++]=bits[i]%10;
else bits[i+1] += (bits[i]%10)*2;
bits[i]=d;
}
}
for (int i = input_index-1; i >=0; i--)
{
cout<<input[i];
}
cout<<endl;
}
}

大数的任意进制转换

由上面的题目不难总结出方式,代码如下

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
#include <iostream>
#include <string>
using namespace std;

string bignum_change(string oldnum,int oldbase,int newbase)
{
int num_len = oldnum.length();
int data[1000];
string res="";
for(int i=0;i<num_len;i++)
{
if(oldnum[i]<='z'&&oldnum[i]>='a') data[i]=oldnum[i]-'a'+10;
else if(oldnum[i]<='Z'&&oldnum[i]>='A') data[i]=oldnum[i]-'A'+10;
else data[i]=oldnum[i]-'0';
}
int sum=1;
int d=0;
while(sum)
{
sum=0;
for(int i=0;i<num_len;i++)
{
d=data[i]/newbase;
sum+=d;
if(i==num_len-1)
{
char tmp;
if(data[i]%newbase >= 10) tmp=(char)(data[i]%newbase+'a'-10);
else tmp=(char)(data[i]%newbase+'0');
res = tmp+res;
}
else
{
data[i+1] += (data[i]%newbase)*oldbase;
}
data[i] = d;
}
}
return res;
}


int main()
{
string num;
cout<<"please input num"<<endl;
while(cin>>num)
{
cout<<"please input oldbase and newbase"<<endl;
int oldbase,newbase;
cin>>oldbase>>newbase;
string res = bignum_change(num,oldbase,newbase);
cout<<num<<"的"<<oldbase<<"进制转"<<newbase<<"进制结果为:"<<res<<endl;
cout<<endl;
cout<<"please input num"<<endl;
}
}

BFS广度优先搜索

BFS:使用队列保存未被检测的结点。结点按照宽度优先的次序被访问和进出队列。
通俗算法

1
2
3
4
5
6
7
8
初始化队列Q
Q={起点s};标记s已访问;
while(Q非空){
取Q队首元素u;u出队;
if(u == 目标状态){....}
所有与u相邻且未被访问的点进入队列;
标记u为已访问;
}

通俗的例子:
你的100块掉在地上了,你去找
你趴在地上,总是先摸自己身边的位置,如果都没有,再摸远一些的位置

胜利大逃亡

hdu pro id 1253
典型的BFS搜索,代码如下

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>
#include <queue>
using namespace std;
int flag[50][50][50];
int map[50][50][50];

typedef struct Node
{
int x,y,z;
int t;
}Node;
queue<Node> Q;

int go[][3]={
1,0,0,
0,1,0,
0,0,1,
-1,0,0,
0,-1,0,
0,0,-1
};

int BFS(int a,int b,int c)
{
while(!Q.empty())
{
Node now = Q.front();
Q.pop();
for(int i=0;i<6;i++)
{
int nx=now.x+go[i][0];
int ny=now.y+go[i][1];
int nz=now.z+go[i][2];
if(nx<0 || nx>=a || ny<0 || ny>=b || nz<0 || nz>=c) continue;
if(map[nx][ny][nz] == 1) continue;
if(flag[nx][ny][nz]) continue;
Node tmp;
tmp.x=nx;
tmp.y=ny;
tmp.z=nz;
tmp.t=now.t+1;
Q.push(tmp);
flag[nx][ny][nz]=1;
if(nx == a-1 && ny==b-1 && nz==c-1) return tmp.t;
}
}
return -1;
}

int main()
{
int k;
cin>>k;
while(k--)
{
int a,b,c,t;
scanf("%d%d%d%d",&a,&b,&c,&t);
for(int i=0;i<a;i++)
{
for(int j=0;j<b;j++)
{
for(int k=0;k<c;k++)
{
scanf("%d",&map[i][j][k]);
flag[i][j][k]=0;
}
}
}
while(!Q.empty()) Q.pop();
flag[0][0][0]=1;
Node tmp;
tmp.x=tmp.y=tmp.z=tmp.t=0;
Q.push(tmp);
int res = BFS(a,b,c);
if(res<=t) cout<<res<<endl;
else cout<<-1<<endl;
}
return 0;
}

DFS深度优先搜索

DFS使用递归进行搜索,从初始位置出发,不断向下一步递归,直至找到符合条件的值
这里涉及到剪枝问题,比如走迷宫
起始位置坐标和+已走步数的奇偶性 = 终点坐标和的奇偶性
就可以利用这一点来进行剪枝
一般用来进行解的存在性问题的解决

Temple of the bone

代码如下:

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
#include <iostream>
using namespace std;

char map[8][8];
int m,n,t;
bool success;

int go[][2]={
1,0,
0,1,
-1,0,
0,-1
};

void DFS(int x,int y,int time)
{
for(int i=0;i<4;i++)
{
int nx=x+go[i][0];
int ny=y+go[i][1];
if(nx<0 || nx>n || ny<0 || ny>n) continue;
if(map[nx][ny] == 'X') continue;
if(map[nx][ny] == 'D')
{
if(time+1 == t)
{
success = true;
return;
}
else continue;
}
map[nx][ny] = 'X';
DFS(nx,ny,time+1);
if(success) return;
}
}

int main()
{
while(cin>>n>>m>>t)
{
int sx,sy;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>map[i][j];
if(map[i][j] == 'D')
{
sx = i;
sy = j;
}
}
}
success = false;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(map[i][j]=='S' && (i+j)%2 == ((sx+sy)%2+t%2)%2)
{
map[i][j] = 'X';
DFS(i,j,0);
}
}
}
if(success == true) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}

递归搜索

讲到前面的DFS,就不得不提一下,递归还是很好用的,可以用来解决一些排列组合的问题

10个烧饼问题

这个问题来自某年北航面试,老师随口问的一个问题
10个烧饼,每天可以吃1~10个,问有多少吃法?
这里和上楼梯问题差不多
用脑子想排列组合问题太难受,不如写个代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;
int ans = 0;
void eat(int left)
{
if(left == 0)
{
ans++;
return;
}
for(int i=1;i<=10;i++)
{
if(left<i) return;
eat(left-i);
}
}

int main()
{
eat(3);
cout<<ans<<endl;
}

全排列

北大的一道字符串题目
例如输入abc,可以字典序输出abc的全排列

1
2
3
4
5
6
abc
acb
bac
bca
cab
cba

这里还是用递归,至于字典序,操作之前对输入的数组sort一下即可

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>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
char ans[6];
char input[6];
bool flag[6];
int n;

void DFS(int num)
{
if(num == n-1)
{
for(int i=0;i<n;i++) cout<<ans[i];
cout<<endl;
return;
}
for(int i=0;i<n;i++)
{
if(flag[i] == false){
flag[i] = true;
ans[num+1] = input[i];
DFS(num+1);
flag[i] = false;
}
}
}

int main()
{
while(cin>>input)
{
n = strlen(input);
sort(input,input+n);
for(int i=0;i<n;i++) flag[i]=false;
for(int i=0;i<n;i++)
{
ans[0] = input[i];
flag[i] = true;
DFS(0);
flag[i] = false;
}
cout<<endl;
}
}

并查集

1.判断两个结点是否在同一集合只需要判断两个结点的根结点是否是同一个结点即可
2.将两个集合合并,只需要将两个集合的根节点合并即可
3.合并后的集合存在查询复杂度问题,如果合并的好,即所以结点都通过一个根节点就可以找到,若合并的不好,则需要遍历n个结点才可以找到想要的结点n
故此,我们的算法为在搜索或者遍历的同时将所有结点都指向根节点
搜索根结点的优化算法

1
2
3
4
5
6
7
8
9
10
11
12
13
int findroot(int x)
{
if(Tree[x]==-1)
{
return x;
}
else
{
int tmp=findroot(Tree[x]);
Tree[x]=tmp;
return tmp;
}
}

畅通工程

典型的并查集问题,将所有连通在一起的结点都指向根结点
这样留下的Tree[i]=-1的结点都将成为待连接结点
最后遍历出这样结点的个数,即ans-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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<iostream>
using namespace std;

#define N 1000

int Tree[N];

int findroot(int x)
{
if(Tree[x]==-1)
{
return x;
}
else
{
int tmp=findroot(Tree[x]);
Tree[x]=tmp;
return tmp;
}
}

int main()
{
int n,m;
while(cin>>n>>m)
{
for(int i=1;i<=n;i++) Tree[i]=-1;
for(int i=0;i<m;i++)
{
int a,b;
cin>>a>>b;
a=findroot(a);
b=findroot(b);
if(a!=b) Tree[a]=b;
}
int ans=0;
for(int i=1;i<=n;i++)
{
if(Tree[i]==-1) ans++;
}
cout<<ans-1<<endl;
}
}

连通图

最后查看有几个-1的根节点即可,只有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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
using namespace std;
#define N 1000

int Tree[N];

int findroot(int x)
{
if(Tree[x]==-1)
{
return x;
}
else
{
int tmp=findroot(Tree[x]);
Tree[x]=tmp;
return tmp;
}
}

int main()
{
int n,m;
while(cin>>n>>m)
{
for(int i=1;i<=n;i++) Tree[i]=-1;
for(int i=0;i<m;i++)
{
int a,b;
cin>>a>>b;
a=findroot(a);
b=findroot(b);
if(a!=b) Tree[a]=b;
}
int ans=0;
for(int i=1;i<=n;i++)
{
if(Tree[i]==-1) ans++;
}
if(ans-1 == 0) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
}

More is better

hdu pro id 1856
依旧是典型的并查集问题,将所有连通的结点指向该集合的根节点,并由根结点记录当前集合里所有的结点个数,最后遍历Tree[i],其中值最大的即为答案
这里由于数据量过大,如果使用递归版的findroot,则会超时,所以这里我改成了非递归版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int findroot(int x)
{
int ret;
int tmp=x;
while(Tree[x]!=-1) x = Tree[x];
ret=x;
x=tmp;
while(Tree[x]!=-1)
{
int t=Tree[x];
Tree[x]=ret;
x=t;
}
return ret;
}

完整AC代码

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
#include <iostream>
using namespace std;
#define N 10000001

int Tree[N];
int sum[N];
int findroot(int x)
{
int ret;
int tmp=x;
while(Tree[x]!=-1)
{
x = Tree[x];
}
ret=x;
x=tmp;
while(Tree[x]!=-1)
{
int t=Tree[x];
Tree[x]=ret;
x=t;
}
return ret;
}
int main()
{
int n;
while(cin>>n)
{
for(int i=0;i<n;i++) {
Tree[i]=-1;
sum[i]=1;
}
for(int i=0;i<n;i++)
{
int a,b;
cin>>a>>b;
a = findroot(a);
b = findroot(b);
if (a!=b){
Tree[a]=b;
sum[b]+=sum[a];
}
}
int ans=1;
for(int i=0;i<n;i++)
{
if(Tree[i] == -1 && sum[i]>ans) ans = sum[i];
}
cout<<ans<<endl;
}
}

How many tables

hdu pro id 1213
依旧是典型的并查集,代码如下

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
#include <iostream>
using namespace std;
#define N 1001

int Tree[N];
int findroot(int x)
{
if(Tree[x] == -1) return x;
else
{
int tmp = findroot(Tree[x]);
Tree[x] = tmp;
return tmp;
}
}
int main()
{
int T;
cin>>T;
while(T--)
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) Tree[i]=-1;
for(int i=0;i<m;i++)
{
int a,b;
cin>>a>>b;
a = findroot(a);
b = findroot(b);
if(a!=b)
{
Tree[a]=b;
}
}
int tables=0;
for(int i=1;i<=n;i++)
{
if(Tree[i] == -1) tables++;
}
cout<<tables<<endl;
}
}

最小生成树(MST)

Kruskal算法

这里利用并查集寻找最小生成树
即将所有边从小到大排序
然后从最小的边开始,如果这两个边不在一起集合里,就将二者合并,反之则不合并
最后检测,若所有结点没有属于同一个根,则不存在最小生成树
即Kruskal算法
边结构体如下

1
2
3
4
5
6
7
8
struct Edge
{
int a,b;
int cost;
bool operator < (const Edge &A) const{
return cost<A.cost;
}
}edge[6000];

还是畅通工程

hdu pro id 1233
代码如下

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
#include <iostream>
#include <algorithm>
using namespace std;

#define N 101
int Tree[N];
int findroot(int x)
{
if(Tree[x] == -1) return x;
else
{
int tmp = findroot(Tree[x]);
Tree[x] = tmp;
return tmp;
}
}

struct Edge
{
int a,b;
int cost;
bool operator < (const Edge &A) const{
return cost<A.cost;
}
}edge[6000];

int main()
{
int n;
while(cin>>n)
{
if(n==0) break;
for(int i=1;i<=n*(n-1)/2;i++)
{
cin>>edge[i].a>>edge[i].b>>edge[i].cost;
}
sort(edge+1,edge+1+n*(n-1)/2);
for(int i=1;i<=n;i++) Tree[i]=-1;
int ans = 0;
for(int i=1;i<=n*(n-1)/2;i++)
{
int a = findroot(edge[i].a);
int b = findroot(edge[i].b);
if(a!=b)
{
Tree[a]=b;
ans+=edge[i].cost;
}
}
cout<<ans<<endl;
}
}

畅通工程(带不存在MST情况)

牛客网直接有4个畅通工程= =
代码如下
最后判断是不是只有一个根节点即可
根节点特征:Tree[i]=-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
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
#include <iostream>
#include <algorithm>
using namespace std;
#define N 101
int Tree[N];
int findroot(int x)
{
if(Tree[x] == -1) return x;
else
{
int tmp=findroot(Tree[x]);
Tree[x] = tmp;
return tmp;
}
}

struct Edge
{
int a,b;
int cost;
}edge[150];

bool cmp(Edge A,Edge B)
{
return A.cost<B.cost;
}

int main()
{
int n,m;
while(cin>>n>>m)
{
if(n==0) break;
for(int i=1;i<=m;i++) Tree[i]=-1;
for(int i=1;i<=n;i++)
{
cin>>edge[i].a>>edge[i].b>>edge[i].cost;
}
sort(edge+1,edge+1+n,cmp);
int ans = 0;
int flag=0;
for(int i=1;i<=n;i++)
{
int a=findroot(edge[i].a);
int b=findroot(edge[i].b);
if(a!=b)
{
Tree[a]=b;
ans+=edge[i].cost;
}
}
for(int i=1;i<=m;i++)
{
if(Tree[i]==-1) flag++;
}
if(flag==1) cout<<ans<<endl;
else cout<<"?"<<endl;
}
}

继续畅通工程

本题在之前的基础上,还涉及到已建好路
这里在比较的时候加入状态即可
即如果修好了路,则优先排在前面,这样就能优先参与并查集运算

1
2
3
4
5
bool cmp(Edge A,Edge B)
{
if(A.status==B.status) return A.cost<B.cost;
else return A.status>B.status;
}

最后AC代码如下

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
#include<iostream>
#include<algorithm>
using namespace std;
#define N 101
int Tree[N];
int findroot(int x)
{
if(Tree[x] == -1) return x;
else
{
int tmp = findroot(Tree[x]);
Tree[x] = tmp;
return tmp;
}
}

struct Edge
{
int a,b;
int cost;
int status;
}edge[6000];

bool cmp(Edge A,Edge B)
{
if(A.status==B.status) return A.cost<B.cost;
else return A.status>B.status;
}

int main()
{
int n;
while(cin>>n)
{
if(n==0) break;
for(int i=1;i<=n;i++) Tree[i]=-1;
for(int i=1;i<=n*(n-1)/2;i++)
{
cin>>edge[i].a>>edge[i].b>>edge[i].cost>>edge[i].status;
}
sort(edge+1,edge+1+n*(n-1)/2,cmp);
int res = 0;
for(int i=1;i<=n*(n-1)/2;i++)
{
int a = findroot(edge[i].a);
int b = findroot(edge[i].b);
if(a!=b)
{
Tree[a]=b;
if(edge[i].status == 0) res+=edge[i].cost;
}
}
cout<<res<<endl;
}
}

最短路径算法

详细介绍

1
https://blog.csdn.net/qq_35644234/article/details/60875818

我就不赘述了

Floyd算法(全源最短路问题)

由于路径长度不存在负数,所以这里使用-1代表无穷大
自身到自身的路径长度设为0
遍历为3重,假设只有3个结点,则
以下列名为
起始地 中间路过地 终点

1
2
3
4
5
6
7
8
9
10
11
12
13
1 1 1
1 1 2
1 1 3
2 1 1
2 1 2
2 1 3
3 1 1
3 1 2
3 1 3
1 2 1
1 2 2
.....
3 3 3

复杂度为n^3
在结点不大于200的时候,一般适用
二维数组a[i][j]中存放的即i到j的最短路径长度
最后只要输出a[src][dst]即可获得答案
基本代码如下

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>
using namespace std;
int ans[101][101];

int main()
{
int n,m;
while(cin>>n>>m)
{
if(n==0 && m==0) break;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
ans[i][j] = -1;
}
ans[i][i] = 0;
}
while(m--)
{
int a,b,c;
cin>>a>>b>>c;
ans[a][b] = ans[b][a]=c;
}
for(int k=1;k<=n;k++)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(ans[i][k] == -1 || ans[k][j] == -1) continue;
if(ans[i][j] == -1 || ans[i][j]>ans[i][k]+ans[k][j])
{
ans[i][j] = ans[i][k]+ans[k][j];
}
}
}
}
cout<<ans[1][n]<<endl;
}
}

Dijkstra算法(单源最短路算法)

我就不多说什么了,大致就是不断从出发点结点开始,找到与出发点最短的结点,不断扩充,直至可以到达目的结点
详细看代码,中间有注释

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
#include <iostream>
#include <vector>
using namespace std;
struct E
{
int next; //代表直接相邻的结点
int c; //代表该边的权值
};
vector<E> edge[101]; //邻接链表
bool mark[101]; //若为true则代表已加入集合K,例如mark[j]=true,代表结点j的最短路径长度已经得到
int Dis[101]; //若mark[i]为true,则Dis[i]为已得的最短路径长度,即结点1到结点i的最短路径

int main()
{
int n,m;
while(cin>>n>>m)
{
if(n==0 && m==0) break;
for(int i=1;i<=n;i++) edge[i].clear(); //初始化邻接链表
while(m--)
{
int a,b,c;
cin>>a>>b>>c;
E tmp;
tmp.c=c;
tmp.next=b;
edge[a].push_back(tmp);
tmp.next=a;
edge[b].push_back(tmp); //由于这里是无向图,所以两边都添加进单链表中
}
for(int i=1;i<=n;i++) //初始化
{
Dis[i]=-1; //所有结点不可达
mark[i]=false; //所有结点都不属于集合k
}
Dis[1]=0; //从结点1开始,最短距离就是本身到本身,即1
mark[1]=true; //将结点1加入集合k
int newP=1; //当前集合k中加入的新结点为newP,即其值1
for(int i=1;i<n;i++) //确认其他结点的情况
{
for(int j=0;j<edge[newP].size();j++) //遍历k集合中新加入结点的相邻结点
{
int t=edge[newP][j].next; //相邻结点的顶点
int c=edge[newP][j].c; //与相邻结点边的长度
if(mark[t]==true) continue; //如果该边已在集合中,则跳过
if(Dis[t]==-1 || Dis[t]>Dis[newP]+c) Dis[t] = Dis[newP]+c; //相邻结点尚未打通,或者当前距离小于从新加入结点打通的长度,就重新赋值
}
int min=0xfffffff; //最小值先赋最大值,为后续初始化
for(int j=1;j<=n;j++) //遍历所有结点
{
if(mark[j]==true) continue; //若该结点已在集合K中,则跳过
if(Dis[j]==-1) continue; //若该结点仍然不可达,则跳过
if(Dis[j]<min) //寻找本次加入K集合的结点,该结点必须为目前所有结点中的最短路径
{
min=Dis[j];
newP=j;
}
}
mark[newP]=true; //将目前找到的最短路径的结点加入集合k
}
cout<<Dis[n]<<endl; //遍历完所有结点,输出结点1到结点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
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
#include <iostream>
#include <vector>
using namespace std;

struct E
{
int next;
int c;
int cost;
};
vector <E> edge[1001];
int Dis[1001];
int cost[1001];
bool mark[1001];
int main()
{
int n,m;
int S,T;
while(cin>>n>>m)
{
if(n==0 && m==0) break;
for(int i=1;i<=n;i++) edge[i].clear();
while(m--)
{
int a,b,c,cost;
cin>>a>>b>>c>>cost;
E tmp;
tmp.c=c;
tmp.cost = cost;
tmp.next = b;
edge[a].push_back(tmp);
tmp.next = a;
edge[b].push_back(tmp);
}
cin>>S>>T;
for(int i=1;i<=n;i++)
{
Dis[i]=-1;
mark[i]=false;
}
Dis[S]=0;
mark[S]=true;
int newP = S;
for(int i=1;i<n;i++)
{
for (int j = 0; j<edge[newP].size();j++)
{
int t=edge[newP][j].next;
int c=edge[newP][j].c;
int co=edge[newP][j].cost;
if(mark[t]==true) continue;
if(Dis[t]==-1 || Dis[t]>Dis[newP]+c || (Dis[t]==Dis[newP]+c && cost[t]>cost[newP]+co))
{
Dis[t] = Dis[newP]+c;
cost[t] = cost[newP]+co;
}
}
int min=0xfffffff;
for(int j=1;j<=n;j++)
{
if(mark[j]==true) continue;
if(Dis[j]==-1) continue;
if(Dis[j]<min)
{
min=Dis[j];
newP=j;
}
}
mark[newP]=true;
}
cout<<Dis[T]<<cost[T]<<endl;
}
return 0;
}

动态规划

动态规划最核心的问题是找到动态方程组

简单递推

这里最简单,最典型的案例是:
1.上楼梯问题:

1
F[n]=F[n-1]+F[n-2]

2.错排公式(即n样东西,全都不在自己该在位置的情况有多少)

1
F[n]=(n-1)*F[n-1]+(n-1)*F[n-2]

最长递增子序列(LIS)

算法就是给每个点设置一个dp[i],记录这个点前面满足条件的值
最后遍历dp[]即可得到其中的最大值

导弹拦截问题

思路即给每一次导弹高度设置一个dp[i]记录前面满足条件的导弹个数
最后遍历dp[],获取最大的一个即为答案
代码如下

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>
#include <algorithm>
using namespace std;
int list[26];
int dp[26];

int main()
{
int n;
while(cin>>n)
{
for(int i=1;i<=n;i++) cin>>list[i];
for(int i=1;i<=n;i++)
{
int tmax=1;
for(int j=1;j<i;j++)
{
if(list[j]>=list[i]) tmax=max(tmax,dp[j]+1);
}
dp[i] = tmax;
}
int ans=1;
for(int i=1;i<=n;i++) ans=max(ans,dp[i]);
cout<<ans<<endl;
}
}

最长上升子序列和

代码如下

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>
#include <algorithm>
using namespace std;

int arr[1010];
int dp[1010];

int main()
{
int n;
while(cin>>n)
{
for(int i=0;i<n;i++)
{
cin>>arr[i];
dp[i]=arr[i];
}
for(int i=1;i<n;i++)
{
for(int j=0;j<i;j++)
{
if(arr[j]<arr[i]) dp[i]=max(dp[i],dp[j]+arr[i]);
}
}
int mmax= dp[0];
for(int i=1;i<n;i++) mmax = max(mmax,dp[i]);
cout<<mmax<<endl;
}
}

最长公共子序列(LCS)

代码如下

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
#include<algorithm>  
#include<iostream>
#include<string>
using namespace std;
static int c[2000][2000] = { 0 };
int main()
{
string a, b;
cin >> a >> b;
for (int i = 1; i <= a.length(); i++)
{
for (int j = 1; j <= b.length(); j++)
{
if (a[i - 1] == b[j - 1])
{
c[i][j] = c[i - 1][j - 1] + 1;
}
else
{
c[i][j] = max(c[i][j - 1], c[i - 1][j]);
}
}
}
cout << c[a.length()][b.length()] << endl;
}

背包问题

太坑爹了,这个我一直很菜逼
大概算法为,定义一个数组dp[n]
其中n为面值容量
dp[n]中存放达到这个容量,所需要物品的最小个数
所以最后输出dp[n]即是结果
我认为如果要最小个数,应该需要物品面值从大到小排序,优先尝试面值大的物品

最小邮票数

AC代码如下

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>
#include <algorithm>
using namespace std;
#define mmax 0x7ffffff
int dp[1000];
int thing[1000];

int main()
{
int n;
while(cin>>n)
{
int num;
cin>>num;
for(int i=0;i<num;i++) cin>>thing[i];
for(int i=0;i<=n;i++) dp[i]=mmax;
dp[0]=0;
for(int i=0;i<num;i++)
{
for(int j=n;j>=0;j--)
{
if(j-thing[i]>=0 && dp[j-thing[i]]!=mmax) dp[j]=min(dp[j],dp[j-thing[i]]+1);
}
}
if(dp[n]==mmax) cout<<0<<endl;
else cout<<dp[n]<<endl;
}
}

采草药

同样背包问题,轻松解决,代码如下

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 <algorithm>
using namespace std;
#define mmin -1000
int dp[1000];

typedef struct Grass
{
int cost;
int vaule;
}Grass;
Grass grass[1000];

bool cmp(Grass a,Grass b)
{
if(a.vaule==b.vaule) return a.cost<b.cost;
else return a.vaule>b.vaule;
}

int main()
{
int time,num;
while(cin>>time>>num)
{
for(int i=0;i<num;i++) cin>>grass[i].cost>>grass[i].vaule;
for(int i=0;i<=time;i++) dp[i]=0;
for(int i=0;i<num;i++)
{
for(int j=time;j>=grass[i].cost;j--)
{
dp[j]=max(dp[j],dp[j-grass[i].cost]+grass[i].vaule);
}
}
cout<<dp[time]<<endl;
}
}

CATALOG
  1. 1. 前言
  2. 2.
    1. 2.1. 哈夫曼树
  3. 3. 二叉排序树
    1. 3.1. 根据前序+空值结果生成二叉树
    2. 3.2. 根据前序和中序生成二叉树
    3. 3.3. 前序遍历
    4. 3.4. 中序遍历
    5. 3.5. 后序遍历
    6. 3.6. 处理结尾空格的问题
    7. 3.7. 一些伪二叉树
  4. 4. 大数运算
    1. 4.1. 大数运算之加法
    2. 4.2. 大数运算之乘法
    3. 4.3. 大数运算之除法(大数/小数)
      1. 4.3.1. 大整数的因子
      2. 4.3.2. 进制转换
      3. 4.3.3. 10进制 VS 2进制
    4. 4.4. 大数的任意进制转换
  5. 5. BFS广度优先搜索
    1. 5.1. 胜利大逃亡
  6. 6. DFS深度优先搜索
    1. 6.1. Temple of the bone
  7. 7. 递归搜索
    1. 7.1. 10个烧饼问题
    2. 7.2. 全排列
  8. 8. 并查集
    1. 8.1. 畅通工程
    2. 8.2. 连通图
    3. 8.3. More is better
    4. 8.4. How many tables
  9. 9. 最小生成树(MST)
    1. 9.1. Kruskal算法
    2. 9.2. 还是畅通工程
    3. 9.3. 畅通工程(带不存在MST情况)
    4. 9.4. 继续畅通工程
  10. 10. 最短路径算法
    1. 10.1. Floyd算法(全源最短路问题)
    2. 10.2. Dijkstra算法(单源最短路算法)
  11. 11. 动态规划
    1. 11.1. 简单递推
    2. 11.2. 最长递增子序列(LIS)
      1. 11.2.1. 导弹拦截问题
      2. 11.2.2. 最长上升子序列和
    3. 11.3. 最长公共子序列(LCS)
    4. 11.4. 背包问题
    5. 11.5. 最小邮票数
    6. 11.6. 采草药