心之所向,素履以往;生如逆旅,一苇以航

3月15日接到16、17两天连续选拔赛的消息的时候整个人是慌的,因为从开学到现在都没有怎么写过代码。那晚连散人直播《最强大~脑》都不看了,在宿舍里焦躁地徘徊,一直跟小姐姐说我不行的。最后熬夜又刷了PAT上几道题试图平复心情。

3月16日上午我整理了《All Things About STL》这篇博文,来复习STL基础的操作类型。时间有限,也没能好好看完。

和学姐一起走到科技楼的时候,我一遍又一遍想不要害怕,得之我幸,失之我命,水平决定一切。但比赛开始的时候我还是手忙脚乱,不断出错,而且浏览器似乎有些奇奇怪怪的问题,动不动就崩。等我写完第一题的时候,已经排到了三四十名的位置。换在平时训练赛,这是完全不可能的事情。好在PAT机制下不算错误率和时间,所以一开始的失利并没有太影响到我。之后每写完一题就前进一些,到第八题写完,已经回到第五差不多的位置了。

最后的成绩:

接下来带来题解,前十题我会用自己的方法(+大佬做法)讲,后五题我用大佬做法讲(+教泥萌怎么蒙)。

天梯赛选拔Day1

7-1 到底有多二 (15 分)

一个整数“犯二的程度”定义为该数字中包含2的个数与其位数的比值。如果这个数是负数,则程度增加0.5倍;如果还是个偶数,则再增加1倍。例如数字-13142223336是个11位数,其中有3个2,并且是负数,也是偶数,则它的犯二程度计算为:3/11×1.5×2×100%,约为81.82%。本题就请你计算一个给定整数到底有多二。

输入格式:

输入第一行给出一个不超过50位的整数N。

输出格式:

在一行中输出N犯二的程度,保留小数点后两位。

输入样例:

-13142223336

输出样例:

81.82%

时间限制: 400 ms

内存限制: 64 MB

代码长度限制: 16 KB

先阐明一个小学数学老师经常强调的点:x增加0.5倍 == x 1.5;x增加1倍 == x 2(well,这里应该也不会有人错)。

单纯找2的话只需要把数据当成字符串读入,寻找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
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
//ios::sync_with_stdio(false);
string s;
cin>>s;
int ans=0,flag1=0,flag2=0;
int n=s.size();
for(int i=0;i<s.size();i++)
{
if(s[i]=='-')
{
flag1=1;
n--;
continue;
}
if(s[i]=='2')
ans++;
if(i==s.size()-1&&(s[i]-'0')%2==0)
flag2=1;
}
//cout<<ans<<" "<<n<<endl;
double m=ans*100.0/n;
//cout<<m<<endl;
if(flag1==1)
m*=1.5;
if(flag2==1)
m*=2;
printf("%.2f",m);
cout<<"%"<<endl;
return 0;
}

有一点需要额外注意,如果取消流同步(ios::sync_with_stdio(false))了以后输出千万不能cout和printf混用,不然……答案全部错误。刚开始吓傻窝了,还好从前遇到过,还请教过学长萌QWQ

7-2 大笨钟 (10 分)

微博上有个自称“大笨钟V”的家伙,每天敲钟催促码农们爱惜身体早点睡觉。不过由于笨钟自己作息也不是很规律,所以敲钟并不定时。一般敲钟的点数是根据敲钟时间而定的,如果正好在某个整点敲,那么“当”数就等于那个整点数;如果过了整点,就敲下一个整点数。另外,虽然一天有24小时,钟却是只在后半天敲1~12下。例如在23:00敲钟,就是“当当当当当当当当当当当”,而到了23:01就会是“当当当当当当当当当当当当”。在午夜00:00到中午12:00期间(端点时间包括在内),笨钟是不敲的。

下面就请你写个程序,根据当前时间替大笨钟敲钟。

输入格式:

输入第一行按照hh:mm的格式给出当前时间。其中hh是小时,在00到23之间;mm是分钟,在00到59之间。

输出格式:

根据当前时间替大笨钟敲钟,即在一行中输出相应数量个Dang。如果不是敲钟期,则输出:

Only hh:mm. Too early to Dang.

其中hh:mm是输入的时间。

输入样例1:

19:05

输出样例1:

DangDangDangDangDangDangDangDang

输入样例2:

07:05

输出样例2:

Only 07:05. Too early to Dang.

时间限制: 400 ms

内存限制: 64 MB

代码长度限制: 16 KB

水题~分类讨论就行

代码:

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<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
ios::sync_with_stdio(false);
string s;
cin>>s;
int h=(s[0]-'0')*10+(s[1]-'0');
int m=(s[3]-'0')*10+(s[4]-'0');
if(h<12)
cout<<"Only "<<s<<". Too early to Dang."<<endl;
else if(h==12&&m==0)
cout<<"Only "<<s<<". Too early to Dang."<<endl;
else
{
if(m==0)
{
for(int i=0;i<h-12;i++)
cout<<"Dang";
}
else
{
for(int i=0;i<=h-12;i++)
cout<<"Dang";
}
}
return 0;
}

7-3 谁先倒 (15 分)

划拳是古老中国酒文化的一个有趣的组成部分。酒桌上两人划拳的方法为:每人口中喊出一个数字,同时用手比划出一个数字。如果谁比划出的数字正好等于两人喊出的数字之和,谁就输了,输家罚一杯酒。两人同赢或两人同输则继续下一轮,直到唯一的赢家出现。

下面给出甲、乙两人的酒量(最多能喝多少杯不倒)和划拳记录,请你判断两个人谁先倒。

输入格式:

输入第一行先后给出甲、乙两人的酒量(不超过100的非负整数),以空格分隔。下一行给出一个正整数N(≤100),随后N行,每行给出一轮划拳的记录,格式为:

甲喊 甲划 乙喊 乙划

其中喊是喊出的数字,划是划出的数字,均为不超过100的正整数(两只手一起划)。

输出格式:

在第一行中输出先倒下的那个人:A代表甲,B代表乙。第二行中输出没倒的那个人喝了多少杯。题目保证有一个人倒下。注意程序处理到有人倒下就终止,后面的数据不必处理。

输入样例:

1
2
3
4
5
6
7
8
1 1
6
8 10 9 12
5 10 5 10
3 8 5 12
12 18 1 13
4 16 12 15
15 1 1 16

输出样例:

1
2
A
1

时间限制: 400 ms

内存限制: 64 MB

代码长度限制: 16 KB

我先提供一份最开始只得了4分的错误代码,泥萌找找哪里有问题

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<bits/stdc++.h>
#define ll long long
using namespace std;
int a1[105],a2[105],b1[105],b2[105];
int main()
{
ios::sync_with_stdio(false);
int a,b,n,ans1=0,ans2=0;
cin>>a>>b>>n;
for(int i=0;i<n;i++)
{
if(ans1==a||ans2==b)
break;
cin>>a1[i]>>a2[i]>>b1[i]>>b2[i];
int m=a1[i]+b1[i];
if(a2[i]==m)
ans1++;
if(b2[i]==m)
ans2++;
}
if(ans1==a)
cout<<'A'<<endl<<ans2<<endl;
else
cout<<'B'<<endl<<ans1<<endl;
return 0;
}


相信(jia she)泥萌已经发现了,理解题意的重要性。

问题出在下面这几行

1
2
3
4
if(a2[i]==m)
ans1++;
if(b2[i]==m)
ans2++;

而题目中说:谁就输了,输家罚一杯酒。两人同赢或两人同输则继续下一轮

也就是说,不仅需要满足一人输,还需要满足另一个人嬴。

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
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int a1[105],a2[105],b1[105],b2[105];
int main()
{
ios::sync_with_stdio(false);
int a,b,n,ans1=0,ans2=0;
cin>>a>>b>>n;
for(int i=0;i<n;i++)
{
cin>>a1[i]>>a2[i]>>b1[i]>>b2[i];
}
for(int i=0;i<n;i++)
{
if(ans1>a||ans2>b)
break;
int m=a1[i]+b1[i];
if(a2[i]==m&&b2[i]!=m)
ans1++;
if(b2[i]==m&&a2[i]!=m)
ans2++;
}
if(ans1>a)
cout<<'A'<<endl<<ans2<<endl;
else
cout<<'B'<<endl<<ans1<<endl;
return 0;
}

7-4 帅到没朋友 (20 分)

当芸芸众生忙着在朋友圈中发照片的时候,总有一些人因为太帅而没有朋友。本题就要求你找出那些帅到没有朋友的人。

输入格式:

输入第一行给出一个正整数N(≤100),是已知朋友圈的个数;随后N行,每行首先给出一个正整数K(≤1000),为朋友圈中的人数,然后列出一个朋友圈内的所有人——为方便起见,每人对应一个ID号,为5位数字(从00000到99999),ID间以空格分隔;之后给出一个正整数M(≤10000),为待查询的人数;随后一行中列出M个待查询的ID,以空格分隔。

注意:没有朋友的人可以是根本没安装“朋友圈”,也可以是只有自己一个人在朋友圈的人。虽然有个别自恋狂会自己把自己反复加进朋友圈,但题目保证所有K超过1的朋友圈里都至少有2个不同的人。

输出格式:

按输入的顺序输出那些帅到没朋友的人。ID间用1个空格分隔,行的首尾不得有多余空格。如果没有人太帅,则输出No one is handsome。

注意:同一个人可以被查询多次,但只输出一次。

输入样例1:

1
2
3
4
5
6
3
3 11111 22222 55555
2 33333 44444
4 55555 66666 99999 77777
8
55555 44444 10000 88888 22222 11111 23333 88888

输出样例1:

10000 88888 23333

输入样例2:

1
2
3
4
5
6
3
3 11111 22222 55555
2 33333 44444
4 55555 66666 99999 77777
4
55555 44444 22222 11111

输出样例2:

No one is handsome

时间限制: 250 ms

内存限制: 64 MB

代码长度限制: 16 KB

照例先放错误代码:

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
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
ios::sync_with_stdio(false);
map<string,int>mp,mp2;
queue<string>q;
int n;
cin>>n;
while(n--)
{
int m;
cin>>m;
while(m--)
{
string s;
cin>>s;
mp[s]++;
}
}
int p;
cin>>p;
while(p--)
{
string s;
cin>>s;
if(mp2[s]==0)
{
if(mp[s]==0)
q.push(s);
}
mp2[s]++;
}
if(q.empty())
cout<<"No one is handsome"<<endl;
else
{
while(!q.empty())
{
if(q.size()==1)
cout<<q.front()<<endl;
else
cout<<q.front()<<" ";
q.pop();
}
}
return 0;
}

又是没好好读题的锅~

没有朋友的人可以是根本没安装“朋友圈”,也可以是只有自己一个人在朋友圈的人。也就是说,k=1的时候和没有k的时候没区别啊。wsl~

这道题我用了queue+map(其实可以不用queue,直接在线查询就行)。map的思路就是:当k>1时,把后面所有编号纳入map,之后查询的时候只要看看map的值是否为0就行。还要注意:同一个人可以被查询多次,但只输出一次。所以要再用一个map记录是否已经被查询过。当然这道题的编号并不大,用数组也ok,就是注意输出要把前导0补全。

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
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
ios::sync_with_stdio(false);
map<string,int>mp,mp2;
queue<string>q;
int n;
cin>>n;
while(n--)
{
int m;
cin>>m;
for(int i=0;i<m;i++)
{
string s;
cin>>s;
if(m>1)
mp[s]++;
}
}
int p;
cin>>p;
while(p--)
{
string s;
cin>>s;
if(mp2[s]==0)
{
if(mp[s]==0)
q.push(s);
}
mp2[s]++;
}
if(q.empty())
cout<<"No one is handsome"<<endl;
else
{
while(!q.empty())
{
if(q.size()==1)
cout<<q.front()<<endl;
else
cout<<q.front()<<" ";
q.pop();
}
}
return 0;
}

7-5 重要的话说三遍 (5 分)

7-6 奇偶分家 (10 分)

//5、6两道zz题窝就直接跳了= =

7-7 输出GPLT (20 分)

给定一个长度不超过10000的、仅由英文字母构成的字符串。请将字符重新调整顺序,按GPLTGPLT….这样的顺序输出,并忽略其它字符。当然,四种字符(不区分大小写)的个数不一定是一样多的,若某种字符已经输出完,则余下的字符仍按GPLT的顺序打印,直到所有字符都被输出。

输入格式:

输入在一行中给出一个长度不超过10000的、仅由英文字母构成的非空字符串。

输出格式:

在一行中按题目要求输出排序后的字符串。题目保证输出非空。

输入样例:

pcTclnGloRgLrtLhgljkLhGFauPewSKgt

输出样例:

GPLTGPLTGLTGLGLL

时间限制: 200 ms

内存限制: 64 MB

代码长度限制: 16 KB

这道题纯暴力。本来想看看网上有没有什么大佬的巧妙解法,发现只能模拟。这道题题意可以转换到分别统计GPLT个数,然后依次输出。

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
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
ios::sync_with_stdio(false);
string s;
cin>>s;
int ans1=0,ans2=0,ans3=0,ans4=0;
for(int i=0;i<s.size();i++)
{
if(s[i]=='G'||s[i]=='g')
ans1++;
if(s[i]=='P'||s[i]=='p')
ans2++;
if(s[i]=='L'||s[i]=='l')
ans3++;
if(s[i]=='T'||s[i]=='t')
ans4++;
}
int m=max(max(ans1,ans2),max(ans3,ans4));
while(m--)
{
if(ans1>0)
{
cout<<'G';
ans1--;
}
if(ans2>0)
{
cout<<'P';
ans2--;
}
if(ans3>0)
{
cout<<'L';
ans3--;
}
if(ans4>0)
{
cout<<'T';
ans4--;
}
}
return 0;
}

7-8 后天 (5 分)

//又是水题~跳鸭

7-9 抢红包 (25 分)

没有人没抢过红包吧…… 这里给出N个人之间互相发红包、抢红包的记录,请你统计一下他们抢红包的收获。

输入格式:

输入第一行给出一个正整数N(≤10^​4),即参与发红包和抢红包的总人数,则这些人从1到N编号。随后N行,第i行给出编号为i的人发红包的记录,格式如下:

K N1 P​1 ⋯NK P​K

其中K(0≤K≤20)是发出去的红包个数,Ni是抢到红包的人的编号,Pi(>0)是其抢到的红包金额(以分为单位)。注意:对于同一个人发出的红包,每人最多只能抢1次,不能重复抢。

输出格式:

按照收入金额从高到低的递减顺序输出每个人的编号和收入金额(以元为单位,输出小数点后2位)。每个人的信息占一行,两数字间有1个空格。如果收入金额有并列,则按抢到红包的个数递减输出;如果还有并列,则按个人编号递增输出。

输入样例:

1
2
3
4
5
6
7
8
9
10
11
10
3 2 22 10 58 8 125
5 1 345 3 211 5 233 7 13 8 101
1 7 8800
2 1 1000 2 1000
2 4 250 10 320
6 5 11 9 22 8 33 7 44 10 55 4 2
1 3 8800
2 1 23 2 123
1 8 250
4 2 121 4 516 7 112 9 10

输出样例:

1
2
3
4
5
6
7
8
9
10
1 11.63
2 3.63
8 3.63
3 2.11
7 1.69
6 -1.67
9 -2.18
10 -3.26
5 -3.26
4 -12.32

时间限制: 400 ms

内存限制: 64 MB

代码长度限制: 16 KB

用个结构体排序就好惹,不多说,直接上代码:

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
#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct p
{
int num,money,n;
}s[100005];
bool cmp(p a,p b)
{
if(a.money==b.money)
{
if(a.n==b.n)
return a.num<b.num;
return a.n>b.n;
}
return a.money>b.money;
}
int main()
{
//ios::sync_with_stdio(false);
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
s[i].num=i;
int m,sum=0;
cin>>m;
while(m--)
{
int c,d;
cin>>c>>d;
s[c].n++;
s[c].money+=d;
sum+=d;
}
s[i].money-=sum;
}
sort(s+1,s+n+1,cmp);
for(int i=1;i<=n;i++)
{
cout<<s[i].num<<" ";
printf("%.2f\n",s[i].money/100.0);
}
return 0;
}

7-10 排座位 (25 分)

布置宴席最微妙的事情,就是给前来参宴的各位宾客安排座位。无论如何,总不能把两个死对头排到同一张宴会桌旁!这个艰巨任务现在就交给你,对任何一对客人,请编写程序告诉主人他们是否能被安排同席。

输入格式:

输入第一行给出3个正整数:N(≤100),即前来参宴的宾客总人数,则这些人从1到N编号;M为已知两两宾客之间的关系数;K为查询的条数。随后M行,每行给出一对宾客之间的关系,格式为:宾客1 宾客2 关系,其中关系为1表示是朋友,-1表示是死对头。注意两个人不可能既是朋友又是敌人。最后K行,每行给出一对需要查询的宾客编号。

这里假设朋友的朋友也是朋友。但敌人的敌人并不一定就是朋友,朋友的敌人也不一定是敌人。只有单纯直接的敌对关系才是绝对不能同席的。

输出格式:

对每个查询输出一行结果:如果两位宾客之间是朋友,且没有敌对关系,则输出No problem;如果他们之间并不是朋友,但也不敌对,则输出OK;如果他们之间有敌对,然而也有共同的朋友,则输出OK but…;如果他们之间只有敌对关系,则输出No way。

输入样例:

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

输出样例:

1
2
3
4
No problem
OK
OK but...
No way

时间限制: 150 ms

内存限制: 64 MB

代码长度限制: 16 KB

其实我拿到这题的第一反应是并——查——集——!!!???!!!

寒假虽然练过并查集的题目,但是没有板子的话就不知道能不能写了。但是并查集的算法原理我是知道的,所以抱着那一丝丝希望,而且如果我写不出来必然会从排行榜跌下去,窝就果断开始写。

首先我们可以把判读敌人和朋友的方法区别开。朋友我采用的是并查集(因为涉及朋友的朋友也是朋友);敌人我采用的是结构体内部嵌套数组,标记是否直接敌对(只有单纯直接的敌对关系才是绝对不能同席的)。

我的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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int father[105];


struct diren
{
int s[105];
}q[105];

void init(int n)
{
for(int i=1;i<=n;i++)
{
father[i]=i;
}
}

int find_father(int n)
{
if(father[n]==n)
return n;
else
{
return find_father(father[n]);
}
}

void Union(int a,int b)
{
if(a>b)
swap(a,b);
father[b]=a;
}

int main()
{
ios::sync_with_stdio(false);
int n,m,k;
cin>>n>>m>>k;
init(n);
while(m--)
{
int a,b,c;
cin>>a>>b>>c;
if(c==1)
{
Union(a,b);
}
else
{
q[a].s[b]=1;
q[b].s[a]=1;
}
}
while(k--)
{
int a,b;
cin>>a>>b;
if(q[a].s[b]==1 && find_father(a)!=find_father(b))
cout<<"No way"<<endl;
else if(q[a].s[b]==1)
cout<<"OK but..."<<endl;
else if(find_father(a)==find_father(b))
cout<<"No problem"<<endl;
else
cout<<"OK"<<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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<iostream>
#include<cstdio>
using namespace std;
int pre[101];
int map[101][101]; //邻接矩阵存储两者的直接关系,1朋友 -1敌对


int find(int x){ //寻找
int r = x;
while(pre[r]!=r){
r = pre[r];
}
int i=x ,j;
while(pre[i]!=r){ //路径压缩
j = pre[i];
pre[i] = r;
i = j;
}
return r;
}



void join(int x,int y){ //将两个集合合并
int fx = find(x);
int fy = find(y);
if(fx!=fy){
pre[fx] = fy;
}
}

bool same(int x,int y){ //判断两个元素是否在同一个集合中
if(find(x)==find(y)){
return true;
}else{
return false;
}
}
int main(){
int n,m,a,b,c,t;
cin>>n>>m>>t;
for(int i=1 ;i<=n ;i++){
pre[i] = i;
}

for(int i=1 ;i<=m ;i++){
scanf("%d%d%d",&a,&b,&c);
map[a][b] = c; //记录直接的对应关系
map[b][a] = c;
if(c==1){
join(a,b); //间接的朋友关系
}
}

for(int i=1 ;i<=t; i++){
scanf("%d%d",&a,&b);
if(map[a][b]==1){
printf("No problem\n");
}
else if(map[a][b]==-1&&find(a)==find(b)){
printf("OK but...\n");
}
else if(map[a][b]==-1&&find(a)!=find(b)){
printf("No way\n");
}
else if(map[a][b]!=-1&&map[a][b]!=1&&find(a)!=find(b)){
printf("OK\n");
}
}


return 0;
}

7-11 玩转二叉树 (25 分)

给定一棵二叉树的中序遍历和前序遍历,请你先将树做个镜面反转,再输出反转后的层序遍历的序列。所谓镜面反转,是指将所有非叶结点的左右孩子对换。这里假设键值都是互不相等的正整数。

输入格式:

输入第一行给出一个正整数N(≤30),是二叉树中结点的个数。第二行给出其中序遍历序列。第三行给出其前序遍历序列。数字间以空格分隔。

输出格式:

在一行中输出该树反转后的层序遍历的序列。数字间以1个空格分隔,行首尾不得有多余空格。

输入样例:

1
2
3
7
1 2 3 4 5 6 7
4 1 3 2 6 5 7

输出样例:

1
4 6 1 7 5 3 2

时间限制: 400 ms

内存限制: 64 MB

代码长度限制: 16 KB

作为一个二叉树盲,大致扫了一下网上题解发现非常不适合入门级别选手。所以额外找了二叉树的知识点整理一下。(转自指点的专栏)

二叉树结构模型

这棵二叉树一共有7个节点,其中,0号节点叫做根节点,下面的1号节点和2号节点是0号节点的子节点,同时1号节点和2号节点又是3号节点、4号节点和5号节点、6号节点的双亲节点,0号节点有分别以1号节点和2号节点作为根节点的左右子树。5号节点和6号节点没有子节点(子树),那么它们被称为叶子节点

一般来说,二叉树常用的遍历方式有:前序遍历、中序遍历、后序遍历、层序遍历 四种遍历方式:

1、前序遍历二叉树顺序:根节点 –> 左子树 –> 右子树,即先访问根节点,然后是左子树,最后是右子树。
上图中二叉树的前序遍历结果为:0 -> 1 -> 3 -> 4 -> 2 -> 5 -> 6

2、中序遍历二叉树顺序:左子树 –> 根节点 –> 右子树,即先访问左子树,然后是根节点,最后是右子树。
上图中二叉树的中序遍历结果为:3 -> 1 -> 4 -> 0 -> 5 -> 2 -> 6

3、后续遍历二叉树顺序:左子树 –> 右子树 –> 根节点,即先访问左子树,然后是右子树,最后是根节点。
上图中二叉树的后序遍历结果为:3 -> 4 -> 1 -> 5 -> 6 -> 2 -> 0

4、层序遍历二叉树顺序:从最顶层的节点开始,从左往右依次遍历,之后转到第二层,继续从左往右遍历,持续循环,直到所有节点都遍历完成
上图中二叉树的层序遍历结果为:0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6

下面给出这四种算法思想的伪代码:

前序遍历:

1
2
3
4
5
6
7
8
9
preOrderParse(int n)
{
if(tree[n] == NULL)
return ; // 如果这个节点不存在,那么结束

cout << tree[n].w ; // 输出当前节点内容
preOrderParse(tree[n].leftChild); // 递归输出左子树
preOrderParse(tree[n].rightChild); // 递归输出右子树
}

中序遍历:

1
2
3
4
5
6
7
8
9
inOrderParse(int n) 
{
if(tree[n] == NULL)
return ; // 如果这个节点不存在,那么结束

inOrderParse(tree[n].leftChild); // 递归输出左子树
cout << tree[n].w ; // 输出当前节点内容
inOrderParse(tree[n].rightChild); // 递归输出右子树
}

后续遍历:

1
2
3
4
5
6
7
8
9
pastOrderParse(int n) 
{
if(tree[n] == NULL)
return ; // 如果这个节点不存在,那么结束

pastOrderParse(tree[n].leftChild); // 递归输出左子树
pastOrderParse(tree[n].rightChild); // 递归输出右子树
cout << tree[n].w ; // 输出当前节点内容
}

可以看到前三种遍历都是直接通过递归来完成,用递归遍历二叉树简答方便而且好理解,接下来层序遍历就需要动点脑筋了,我们如何将二叉树一层一层的遍历输出?其实在这里我们要借助一种数据结构来完成:队列。

我们都知道,队列是一种先进先出的数据结构,我们可以先将整颗二叉树的根节点加入队尾,然后循环出队,每次读取队头元素输出并且将队头元素出队,然后将这个输出的元素节点的的左右子树分别依次加入队尾,重复这个循环,知道队列为空的时候结束输出。那么整个二叉树就被我们采用层序遍历的思想输出来了。下面我们看一下上图的二叉树用层序遍历思想的遍历步骤:

1
2
3
4
5
6
7
8
9
10
11
12
while(!que.empty())  
{
int n = que.front(); // 得到队头元素
que.pop(); // 队头元素出队列
// 如果当前节点不为空,那么输出节点的数值,并且在队尾插入左右子节点
if(tree[n] != NULL)
{
cout << tree[n].w;
que.push(tree[n].leftChild);
que.push(tree[n].rightChild);
}
}

Ok,下面来看一下这几个遍历算法的最终代码:

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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
/*
* 二叉树的四种遍历方式,这里没有采用真实的指针去做,
* 而是采用数组下标去模拟指针,是一种更加方便快速的方法
*/
#include <iostream>
#include <queue>
using namespace std;
const int N = 10010;
const int INF = -1; //我们用一个常数来表示当前二叉树节点为空的情况

struct Node
{
int w; // 当前树节点的值
int p; // 当前树节点的双亲所在数组下标
int l; // 当前树节点的左子节点所在数组下标
int r; // 当前树节点的右子节点所在数组下标
};
Node node[N];

// 按照前序遍历二叉树的顺序输入树节点
void input(int n)
{
cin >> node[n].w;
if(node[n].w == INF) //输入-1代表当前节点所在子二叉树停止输入
{
return ;
}
node[n].p = n / 2;
node[n].l = n * 2;
node[n].r = n * 2 + 1;

input(n*2);
input(n*2+1);
}

// 前序遍历二叉树
void preOrderParse(int n)
{
if(node[n].w == INF)
{
return ;
}

cout << node[n].w << " ";
preOrderParse(node[n].l);
preOrderParse(node[n].r);
}

// 中序遍历二叉树
void inOrderParse(int n)
{
if(node[n].w == INF)
{
return ;
}

inOrderParse(n*2);
cout << node[n].w << " ";
inOrderParse(n*2+1);
}

// 后续遍历二叉树
void postOrderParse(int n)
{
if(node[n].w == INF)
{
return ;
}

postOrderParse(n*2);
postOrderParse(n*2+1);
cout << node[n].w << " ";
}

/*
* 层序遍历二叉树,这里采用的是 C++ STL 模板的提供的队列(queue),
* 并没有自己去实现一个队列
*/
void sequenceParse()
{
queue<int> que;
int n = 1;
que.push(1); // 插入根节点所在数组下标
while(!que.empty())
{
n = que.front();
que.pop(); // 得到队头元素并且将队头元素出队列
// 如果当前节点不为空,那么输出该节点,并且将该节点的左右子节点插入队尾
if(node[n].w != INF)
{
cout << node[n].w << " ";
que.push(node[n].l);
que.push(node[n].r);
}
}
}

int main()
{
cout << "请以前序遍历的顺序输入二叉树,空节点输入 -1 :" << endl;
input(1); // 从下标为 1 开始前序输入二叉树

cout << "前序遍历:" << endl;
preOrderParse(1);
cout << endl << "中序遍历:" << endl;
inOrderParse(1);
cout << endl << "后序遍历:" << endl;
postOrderParse(1);
cout << endl << "层序遍历:" << endl;
sequenceParse();

return 0;
}

然后回到原题,大体思路就是根据前序、中序序列还原建树,然后镜面反转,就是将非叶子节点的左右孩子互换,最后层序遍历输出这棵树。

最后更新: 2019年08月05日 09:47

原始链接: http://yisin.top/2019/03/18/天梯赛选拔Day1/

× 请我吃糖~
打赏二维码