Sharing (25)

#include <iostream>
using namespace std;
const int maxn=100010;
struct Node{
    int next,order;                    //本题跟数据域无关，以结点地址为唯一标识，可不设data
}node[maxn];
int main(){
    int head1,head2,n,adress;char c;
    cin>>head1>>head2>>n;
    for(int i=0;i<n;i++){    
        cin>>adress;
        cin>>c>>node[adress].next;
    }
    adress=head1;
    for(int i=1;adress!=-1;i++){      //对第一个链表标记顺序（结构体int型缺省为0），实际上是对第一个链表结点作标记
        node[adress].order=i;
        adress=node[adress].next;
    }
    adress=head2;
    int first=-1;
    while(adress!=-1){
        if(node[adress].order>0){     //类似hash，枚举第二个链表结点，若此结点在第一个链表中出现过，必为共用结点
            first=adress;
            break;                    //找到第一个共用结点就break
        }
        adress=node[adress].next;
    }
    if(first!=-1) printf("%05d",first);
    else printf("-1");
    return 0;
} 

Sharing (25) 2018-12-20
 General mean: give you tow list, requst the first command node in both list.
 Result: Cost about 18 minues, A very funny and easy problem. To to that better
 you should skillfuly use set and map in STL. And it is very easy to come up
 with a solution.
 #include<iostream>
 #include<set>
 #include<map>
 using namespace std;
 map<int, int> adr;  // record the adress and next adress of a node;
 int start1, start2, n;
 set<int> set1;         //the adress of node in list1
 int main(){
 cin >> start1 >> start2 >> n;
 for (int i = 0; i < n; i++){
//I were expect that i can use interger-type to receive a char-type, but it turn to be worng... char t2; 
 int t1, t3;
 cin >> t1 >> t2 >> t3; 
 adr.insert(pair<int, int>(t1, t3));
 }
 while (start1 > 0 ){
 start1 = adr[start1];
 set1.insert(start1);
 }
 while (start2 > 0 ){
 start2 = adr[start2];
 if (set1.find(start2) != set1.end()){
 cout << start2 << endl;
 return 0;
 }
 }
 return 0;
 }

import java.util.*;
public class Main{
    public static void main(String[] args){
        HashMap<String,String> hashMap=new HashMap<String,String>();
        Scanner sc=new Scanner(System.in);
        String start1=sc.next();
        String start2=sc.next();
        int n=sc.nextInt();
        for(int i=0;i<n;i++){
            String start=sc.next();
            String value=sc.next();
            String end=sc.next();
            hashMap.put(start,end);
        }
        LinkedList<String> list1=new LinkedList<String>();
        LinkedList<String> list2=new LinkedList<String>();
        list1.add(start1);
        String addr1=hashMap.get(start1);
        while(addr1!=null){
            list1.add(addr1);
            addr1=hashMap.get(addr1);
        }
        list2.add(start2);
        String addr2=hashMap.get(start2);
        while(addr2!=null){
            list2.add(addr2);
            addr2=hashMap.get(addr2);
        }
        int index1=list1.size()-1;
        int index2=list2.size()-1;
        while(list1.get(index1).equals(list2.get(index2))){
            index1--;
            index2--;
        }
        if(index1==list1.size()-1){
            System.out.println("-1");
        }else{
            System.out.println(list1.get(++index1));
        }
    }
}

#include <iostream>
#include <stdio.h>

using namespace std;

int data[100000];

int main()
{
    // 读入数据
    int addr1, addr2, N, addr, next; char val;
    scanf("%d %d %d", &addr1, &addr2, &N);
    for(int i=0; i<N; i++) {
        scanf("%d %c %d", &addr, &val, &next);
        data[addr] = next;
    }

    // 找出两个链表的第一个节点
    int len1=0, len2=0; addr = addr1;
    while(addr != -1) {
        len1++; addr = data[addr];
    }
    addr = addr2;
    while(addr != -1) {
        len2++; addr = data[addr];
    }
    if(len1 > len2) {
        int len = len1 - len2;
        while(len--) {
            addr1 = data[addr1];
        }
    } else {
        int len = len2 - len1;
        while(len--) {
            addr2 = data[addr2];
        }
    }
    while(addr1>=0 && addr2>=0 &&addr1 != addr2) {
        addr1 = data[addr1];
        addr2 = data[addr2];
    }
    if(addr1>=0) {
        printf("%05d", addr1);
    } else {
        printf("-1");
    }
    return 0;
} 

a = input().split()
d = {}
for i in range(int(a[2])):
    b = input().split()
    d[b[0]] = b[2]

b = [[a[0]],[a[1]]]
for i in range(2):
    while a[i] != '-1':
        b[i].append(d[a[i]])
        a[i] = d[a[i]]

for i in range(-1,-min((len(b[0]),len(b[1]))) - 1,-1):
    if b[0][i] != b[1][i]:
        print(b[0][i + 1])
        break
else:
    print(b[0][i])

#include<iostream>
#include<map>
using namespace std;
int main(void){     map<int, vector<int> > pre;     int ad1, ad2, n;     char c;     cin >> ad1 >> ad2 >> n;     for (int i = 0; i < n; i++){         cin >> ad1 >> c >> ad2;         pre[ad2].push_back(i);         if (pre[ad2].size() == 2 && ad2 != -1){             printf("%05d", ad2);             return 0;         }     }     cout << "-1";     return 0;
} 

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()) {
            String s1 = sc.next();
            String s2 = sc.next();
            String tempS1 = s1;
            String tempS2 = s2;
            int n = sc.nextInt();
            Map<String,String> map = new HashMap<>();

            for (int i = 0;i<n;i++){
                String a = sc.next();
                String b = sc.next();
                String c = sc.next();
                map.put(a,c);

            }
            int len1 = 1;
            int len2 = 1;
            while (!tempS1.equals("-1")){
                tempS1 = map.get(tempS1);
                len1++;
            }
            while (!tempS2.equals("-1")){
                tempS2 = map.get(tempS2);
                len2++;
            }
            if (len1>len2){
                int t = len1-len2;
                while (t>0){
                    s1 = map.get(s1);
                    t--;
                }
            }
            if (len2>len1){
                int t = len2-len1;
                while (t>0){
                    s2 = map.get(s2);
                    t--;
                }
            }
            while (!s1.equals(s2)){
                s1 = map.get(s1);
                s2 = map.get(s2);
            }
            System.out.println(s1);
        }
    }
}

w1,w2,n=input().split()
D,S={},set([])
for i in range(int(n)):
    a,b,c=input().split()
    D[a]=c
while w1!='-1':
    S.add(w1)
    w1=D[w1]
while w2!='-1':
    if w2 in S:
        print(w2)
        break
    w2=D[w2]
else:
    print(-1)

思路：建立两个vector数组记录链的下标，然后从后面往前看第一个不同的地址然后就输出前一个
相同的。
#include <iostream>
#include <list>
#include <fstream>
#include <iomanip>
#include <vector>
// 求公共后缀的开始

using namespace std;

struct ilist
{
    int adr;
    char data;
    int nAdr;
};

#ifndef debug
ifstream ifile("case.txt");
#define cin ifile
#endif

int main()
{
    int sta1, sta2, n;
    cin >> sta1 >> sta2 >> n;
    vector<int> mlist1;
    vector<int> mlist2;
    int mark[100000][2];// 0 存储data 1 存储nAdr
    int tmp;
    char cTmp;
    for (int i = 0; i < n; i++)
    {
        cin >> tmp;
        cin >> cTmp >> mark[tmp][1];
        mark[tmp][0] = cTmp;
    }
    int index;
    for (index = sta1; mark[index][1] != -1;)
    {
        mlist1.push_back(index);
        index = mark[index][1];
    }
    mlist1.push_back(index);// 存储-1的节点
    for (index = sta2; mark[index][1] != -1;)
    {
        mlist2.push_back(index);
        index = mark[index][1];
    }
    mlist2.push_back(index);// 存储-1的节点
    // 开始比较
    int sameAdr = -1;
    for (int i = mlist1.size() - 1, j = mlist2.size() - 1; i >= 0 && j >= 0; i--, j--)
    {
        if (mlist1[i] != mlist2[j])
        {
            break;
        }
        else
        {
            sameAdr = mlist1[i];
        }
    }
    if (sameAdr != -1)
        cout << setfill('0') << setw(5) << sameAdr << endl;
    else
        cout << sameAdr << endl;
    system("pasue");
}

#include "iostream"
#include "vector"
#include "string"
#include "cstring"
#include "queue"
#include "stack"
#include "map"
#include "ctime"
#include <limits.h>
#include <algorithm>
using namespace std;

struct Data
{
	int index;
	int next;
	char ch;
};

vector<Data> Input(100001);
int main()
{
	int startAdd, finalAdd;
	int N;
	cin >> startAdd >> finalAdd >> N;
	vector<int> end;
	for (int i = 0; i < N; i++)
	{
		int s, f;
		char k;
		cin >> s >> k >> f;
		Input[s].index = s;
		Input[s].ch = k;
		Input[s].next = f;
		if (f == -1)
			end.push_back(s);
	}
	int count = 0, pos = 0;
	stack<Data> s1, s2;
	while (startAdd != -1)
	{
		s1.push(Input[startAdd]);
		startAdd = Input[startAdd].next;
	}
	while (finalAdd != -1)
	{
		s2.push(Input[finalAdd]);
		finalAdd = Input[finalAdd].next;
	}
	while (s1.size() != 0 && s2.size() != 0)
	{
		if (s1.top().ch == s2.top().ch)
		{
			pos = s1.top().index;
			s1.pop(), s2.pop();
			
			count++;
		}
		else
			break;
	}
	if (count == 0)
		cout << -1;
	else
		printf("%5d", pos);
}