For each case, the first line contains two addresses of nodes and a positive N (<= 10^5), where the two addresses are the addresses of the first nodes of the two words, and N is the total number of nodes. The address of a node is a 5-digit positive integer, and NULL is represented by -1. Then N lines follow, each describes a node in the format: Address Data Next where Address is the position of the node, Data is the letter contained by this node which is an English letter chosen from {a-z, A-Z}, and Next is the position of the next node.
For each case, simply output the 5-digit starting position of the common suffix. If the two words have no common suffix, output "-1" instead.
11111 22222 9 67890 i 00002 00010 a 12345 00003 g -1 12345 D 67890 00002 n 00003 22222 B 23456 11111 L 00001 23456 e 67890 00001 o 00010 00001 00002 4 00001 a 10001 10001 s -1 00002 a 10002 10002 t -1
67890 -1
#include<iostream> #include<vector> using namespace std; typedef struct node{ char data; int Next_Addr; //下一个结点地址 int flag; //访问次数标记 }Node; int Get_Com(vector<Node> &Pre, int h1, int h2){ int i,t1,t2; i = h1; while(i != -1){ Pre[i].flag += 1; i = Pre[i].Next_Addr; //访问串1的下一个结点 } i = h2; while(i != -1){ Pre[i].flag += 1; if(Pre[i].flag == 2) return i; i = Pre[i].Next_Addr; } return -1; //说明所有结点都只有被访问过一次,即无交汇结点,返回-1 } int main(){ int N,Addr1,Addr2,temp_Addr; int Com; vector<Node> Pre; while(cin>>Addr1>>Addr2>>N){ Pre.clear(); Pre.resize(100000); for(int i=0; i<N; i++) Pre[i].flag = 0; for(int i=0; i<N; i++){ cin>>temp_Addr; cin>>Pre[temp_Addr].data>>Pre[temp_Addr].Next_Addr; } Com = Get_Com(Pre,Addr1,Addr2); if(Com != -1){ //-1前面不需要补充0 cout.width(5); cout.fill('0'); } cout<<Com<<endl; } return 0; }
#include<stdio.h> #include<string.h> using namespace std; int list[100000]; int main(){ int a,b,c; while(scanf("%d %d %d",&a,&b,&c)!=EOF){ int temp=0; for(int i=0;i<100000;i++){ list[i]=0; } int addr=-1; while(temp<c){ int begin,next; char ch; scanf("%d %c %d",&begin,&ch,&next); list[next]++; if(list[next]==2){ addr=next; } temp++; } printf("%d\n",addr); } }
#include <iostream> #include <algorithm> using namespace std; const int maxn=100005; struct node { char data; int next; }list[maxn]; int main() { int s1,s2,n; while (cin>>s1>>s2>>n) { int pos,next,len1=0,len2=0; char c; for(int i=0;i<n;++i) { cin>>pos>>c>>next; list[pos].data=c; list[pos].next=next; } for(int i=s1;i!=-1;i=list[i].next) { len1++; } for(int i=s2;i!=-1;i=list[i].next) { len2++; } int d=abs(len1-len2); if(len1>len2) while(d--) s1=list[s1].next; else while(d--) s2=list[s2].next; while (s1!=-1) { if(s1==s2) break; s1=list[s1].next; s2=list[s2].next; } cout<<s1<<endl; } return 0; }
#include <iostream> #include <cstring> using namespace std; int main(){ int firstStart,secondStart,n; while(cin>>firstStart>>secondStart>>n){ int nextPosition[1000000]; memset(nextPosition,0,sizeof(nextPosition)); int count[1000000]; memset(count,0,sizeof(count)); char data[2]; int startPosition=0,secondPosition=0; for(int i=0;i<n;i++){ cin>>startPosition>>data>>secondPosition; nextPosition[startPosition]=secondPosition; } int position=firstStart; while(position!=-1){ count[position]++; position=nextPosition[position]; } int index=-1; position=secondStart; while(position!=-1){ count[position]++; if(count[position]==2){ index=position; break; } position=nextPosition[position]; } cout<<index<<endl; } }
#include <iostream> #include <map> using namespace std; int main(){ int first, start, n; while(cin >> first >> start >> n){ int a, temp; char b; map<int, int> mymap; for(int i=0; i<n; ++i){ cin >> a >> b >> temp; mymap[temp]++; } int taget = 0; for(auto it = mymap.begin(); it != mymap.end(); ++it){ if(it->second == 2) taget = it->first; } if(taget) cout << taget << endl; else cout << "-1" << endl; } }
#include <iostream> #include <string> #include <vector> using namespace std; struct Node { //静态链表结点 string data; //数据 int next; //下一结点指针(地址) }; vector<Node>nodes(1e5); //静态链表存储区 //vector数组下标表示地址 int countNodes(int head) { //统计静态链表结点个数,head为头指针 int count = 0; for (; head != -1; head = nodes[head].next, count++); return count; } int main() { int head1, head2, n; while (cin >> head1 >> head2 >> n) { while (n--) { int address; //地址 cin >> address >> nodes[address].data >> nodes[address].next; } int n1 = countNodes(head1); int n2 = countNodes(head2); //两条链表长度找齐 for (; n1 > n2; head1 = nodes[head1].next, n1--); for (; n2 > n1; head2 = nodes[head2].next, n2--); //两条链表同时向前遍历,地址相同或到达结尾时结束 for (; head1 != -1 && head1 != head2; head1 = nodes[head1].next, head2 = nodes[head2].next); cout << head1 << endl; } return 0; }
#include <cstdio> #include <iostream> #include <map> using namespace std; int main() { int m,n; while(scanf("%d%d%d",&m,&m,&n)!=-1){ int tag; map<int,int> mymap; for(int i=0;i<n;i++){ int adress,next;char data; scanf("%d %c %d",&adress,&data,&next); mymap[next]++; if(mymap[next]==2){ tag=next; } } cout<<tag<<endl; } }
N<=100000不就是来直接寻址的吗?直接数组下标寻址了,不需要用map #include <iostream> using namespace std; struct Node { char c; int next; } node[100001]; int main() { int n, start1, start2, a, b; cin >> start1 >> start2 >> n; while (n--) { cin >> a >> node[a].c >> node[a].next; } int p = start1, q = start2; while (p != q) //如果出现共同节点,那么退出循环 { p = (p == -1) ? start2 : node[p].next; //p到达末尾时,将其重新接到start2上 q = (q == -1) ? start1 : node[q].next; //q到达末尾时,将其重新接到start1上 } //如果没有共同节点,那么两条链的最后一个节点的next都是-1,p=q=-1,也退出循环 cout << p << endl; //直接输出p即可,不需要判断 system("pause"); return 0; }
#include <iostream> #include <list> #include <iterator> #include <string> using namespace std; struct Node { char data; string address,next; Node() { cin>>address>>data>>next; } }; void makeWordUp(string address,list<Node> word,list<Node> &node) { list<Node>::iterator letter=word.begin(); while(letter!=word.end()) { if(letter->address!=address) letter++; else break; } node.push_back(*letter); word.erase(letter); address=letter->next; if(address!="-1") makeWordUp(address, word, node); } string commonSuffix(list<Node> word1,list<Node> word2) { list<Node>::reverse_iterator letter1=word1.rbegin(); list<Node>::reverse_iterator letter2=word2.rbegin(); while(letter1!=word1.rend()&&letter2!=word2.rend()) { if(letter1->data-letter2->data) return letter1->next; else { letter1++; letter2++; } } return "-1"; } int main() { string addr1,addr2; long number; list<Node> word,word1,word2; while(cin>>addr1>>addr2>>number) { for(long i=0;i<number;i++) word.push_back(Node()); makeWordUp(addr1, word, word1); makeWordUp(addr2, word, word2); cout<<commonSuffix(word1, word2)<<endl; word.clear(); word1.clear(); word2.clear(); } return 0; }
#include<iostream> (720)#include<map> using namespace std; struct Node{ char letter; int next; }; int main(){ int address1,address2,n; while(cin>>address1>>address2>>n){ map<int,Node> myMap; //map映射,通过地址直接找到结点 while(n--){ //存入数据 int myaddress,nextaddress; char data; cin>>myaddress>>data>>nextaddress; Node *current=new Node; current->letter=data; current->next=nextaddress; myMap[myaddress]=*current; } int len1=1,len2=1; //统计两个单词长度 int pos=address1; while(myMap[pos].next!=-1){ len1++; pos=myMap[pos].next; } pos=address2; while(myMap[pos].next!=-1){ len2++; pos=myMap[pos].next; } int pos1=address1,pos2=address2; //设置位置标记指向两单词开头 if(len1>len2){ //对齐位置 pos=len1-len2; while(pos>0){ pos1=myMap[pos1].next; pos--; } } else{ pos=len2-len1; while(pos>0){ pos2=myMap[pos2].next; pos--; } } while(pos1!=pos2){ //同时后移,找到地址相同的结点,然后输出 pos1=myMap[pos1].next; //若无相同字母则最后位置都移动到-1,直接输出 pos2=myMap[pos2].next; } cout<<pos1<<endl; } return 0; }
#include <bits/stdc++.h> using namespace std; const int MAX=1e6; int re[MAX]; int main(){ char c; int i, n, ans, t1, t2; while(cin >> t1 >> t2 >> n){ memset(re, 0, sizeof(re)); ans = -1; for(i=0; i<n; i++){ scanf("%d %c %d", &t1, &c, &t2); if(t2 != -1){ re[t2]++; if(re[t2] == 2) ans = t2; //说明两个链表都出现了 } } if(ans == -1) printf("-1\n"); else printf("%5d\n", ans); } return 0; }但显然,上面的代码是存在问题的,因为题目问的是出现的首个字母相同的链表地址,因此还是有必要记录一下地址。遍历链表前,先判断是否出现了两次‘-1’,是则输出‘-1’;否则选一个链表遍历,直到发现出现了两次的链表地址,输出,如下。
#include<cstdio> #include<vector> using namespace std; struct node{ char ch; int next; }; int main(){ int r1,r2,k; int n1,n2,next; char ch; while(scanf("%d %d %d",&r1,&r2,&k)!=EOF){ vector<node> v(100010); for(int i=0;i<k;++i){ scanf("%d %c %d",&n1,&ch,&n2); v[n1].ch=ch; v[n1].next=n2; } int p=r1,len1=0,len2=0; while(p!=-1){ len1++; p=v[p].next; } p=r2; while(p!=-1){ len2++; p=v[p].next; } while(len1!=len2){ if(len1>len2) { r1=v[r1].next; len1--; } else{ r2=v[r2].next; len2--; } } while(r1!=-1){ if(v[r1].ch==v[r2].ch&&r1==r2){ printf("%05d\n",r1); break; } r1=v[r1].next; r2=v[r2].next; } if(r1==-1) printf("-1\n"); } return 0; }
#include<stdio.h> (737)#include<string.h> typedef struct node { char word; int next; }node; int main() { node ret[100000]; int st_1,st_2,n; int a,b; char temp[3]; while(scanf("%d %d %d",&st_1,&st_2,&n)!=EOF) { memset(ret,0,sizeof(ret)); for(int i=0; i<n; i++) { scanf("%d %s %d",&a,temp,&b); ret[a].word=temp[0]; ret[a].next=b; } int p1=st_1,p2=st_2; while(p1 != p2) { p1= (p1==-1) ? st_2 : ret[p1].next; p2= (p2==-1) ? st_1 : ret[p2].next; } if(p1== -1) printf("-1\n"); else printf("%05d",p1); } return 0; }
/*她走丢了 运行时间较长,数据量还是比较大的,但是其他的应该会更长吧*/ #include <stdio.h> #include <map> using namespace std; map<int, int> M; int main() { int begin1, begin2, num; while (scanf("%d%d%d", &begin1, &begin2,&num) != EOF) { bool fag = true; M.clear(); int s1, s2; char c; for (int i = 0; i < num; i++) { scanf("%d %c %d", &s1, &c, &s2); if(s2!=-1) M[s2]++; if (M[s2] == 2){ printf("%d\n", s2); fag = false; } } if(fag) printf("-1\n"); } return 0; }
#include <iostream> #include <stack> using namespace std; const int maxn = 100010; struct Node{ int add,next; char v; }node[maxn]; stack<Node> stk[2]; int s1,s2,n; void get_stk(int index,int arr){ if(index==-1) return; stk[arr].push(node[index]); get_stk(node[index].next,arr); } int main(){ while(scanf("%d%d%d",&s1,&s2,&n)!=EOF){ for(int i=0;i<n;i++){ int add; scanf("%d",&add); getchar(); scanf("%c%d",&node[add].v,&node[add].next); node[add].add = add; } get_stk(s1,0); get_stk(s2,1); int ans = -1; while(!stk[0].empty() && !stk[1].empty()){ if(stk[0].top().v!=stk[1].top().v) break; else { ans = stk[0].top().add; stk[0].pop(); stk[1].pop(); } } cout << ans << endl; } return 0; }