我的解法：想复杂了！！！
解题思路：使用静态链表，先遍历第一个单词，然后遍历过的标志位flag设为1，并判断第一个是否含有环，有环的话就为-1，没有环就遍历第二个字符串，如果遇到flag为1，就输出结果，同时也要判断是否有环，但是我的解法有两个测试点答案错误，只有22分，所以还需要完善！
我觉得可能的错误就是两个链中间有公共部分！解决办法是从第一个相同的位置，再遍历两个字符串，如果标志位不相同，还要进行判断，是跳过该字符继续判断后面的，直到-1，还是直接输出-1.
**注意：scanf使用%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
| #include <cstdio>
#include <iostream>
using namespace std;
const int maxn=100010;
struct Node{
char data;
int next;
int flag;
}node[maxn];
int main(){
int a1,a2,n,x;
scanf("%d%d%d",&a1,&a2,&n);
for(int i=0;i<n;i++){
cin>>x;
cin>>node[x].data>>node[x].next;
}
Node n1=node[a1];
int k=0;
while(k!=n){
node[n1.next].flag=1;
if(n1.next==-1) break;
n1=node[n1.next];
k++;
}
Node n2=node[a2];
if(k==n) cout<<"-1";
else{
k=0;
while(k!=n){
if(node[n2.next].flag==1) break;
if(n2.next==-1) break;
n2=node[n2.next];
k++;
}
if(k==n) cout<<"-1";
else printf("%05d",n2.next);
}
return 0;
}
|
算法笔记解法
解题思路：不需要判断是否有环，只要将两个字符串都遍历一遍就完成了。不要想太复杂。。。PAT这题目是真的恶心，测试用例该复杂的时候不复杂，不该复杂的时候0001也能当做1来输入，真tm恶心！！！
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
| #include <cstdio>
const int maxn=100010;
struct Node{
char data;
int next;
int flag;
}node[maxn];
int main(){
int a1,a2,n,x,next;
char c;
scanf("%d%d%d",&a1,&a2,&n);
for(int i=0;i<n;i++){
scanf("%d %c %d",&x,&c,&next);
node[x].data=c;
node[x].next=next;
}
int n1=a1;
while(n1!=-1){
node[n1].flag=1;
n1=node[n1].next;
}
int n2=a2;
while(n2!=-1){
if(node[n2].flag==1) break;
n2=node[n2].next;
}
if(n2!=-1){
printf("%05d",n2);
}else{
printf("-1");
}
return 0;
}
|