首页 > 代码库 > PAT-1032

PAT-1032

2024-08-01 00:39:20   212人阅读

这道题最先开始时用栈和map来做的，首先将两个链表压入栈中，然后从栈顶开始比较两个元素，发现最后一个数据超时了。

然后用一种比较巧的方法，计算每个节点的反向链接节点数目，只要是交点，反向链接节点数目就会是2,由此计算出交集点。发现最后一个测试用例还是超时，于是网上搜罗了一下，发现网上有人用第一种方法就过了，奇怪，难道是我把整数都处理成字符串的原因？输入输出换成了cin>>,cout原因？这些细节都要注意。第一种方法写出来代码

// 1032.cpp : 定义控制台应用程序的入口点。//#include "stdafx.h"#include<string>#include<iostream>#include<map>#include<stack>using namespace std;struct Node{    char data;    string next;};stack<string> s1;stack<string> s2;int main(){    string start,end;    string a;    int n;    map<string,Node> list;    freopen("1032-in.txt","r",stdin);    //freopen("1032-out.txt","w",stdout);    while(cin>>start>>end>>n)    {        for(int i=0;i<n;i++)        {            Node node;            cin>>a>>node.data>>node.next;            list.insert(make_pair(a,node));//map-insert        }    }    string next=start;    while(true)    {        s1.push(next);        map<string,Node>::iterator it=list.find(next); //map-find        if(it!=list.end())            next=it->second.next;        else            break;        if(next=="-1")            break;    }    next=end;    while(true)    {        s2.push(next);        map<string,Node>::iterator it=list.find(next);//map-find        if(it!=list.end())          next=it->second.next;        else            break;        if(next=="-1")            break;    }    string t1,t2;    string pos="";    while(true)    {        t1=s1.top();        t2=s2.top();        s1.pop();        s2.pop();        if(t1!=t2||s1.empty()||s2.empty())            break;        pos=t1;    }    if(!pos.empty())        cout<<pos<<endl;    else        cout<<"-1"<<endl;    return 0;}

map.find返回迭代器，map.erase输入迭代器的位置，或者输入关键字的值。map要熟练使用

最后用的是网上比较多人使用做标记的方法，第一次访问过的元素全部坐上标记。

从start2开始访问，只要是交集节点，再次访问时候，标志位就为1，如此交集节点算出来了。这题目是2012年研究生入学考试题目，为嘛我一点印象都没有了。。。。。。

// 1032.cpp : 定义控制台应用程序的入口点。//#include "stdafx.h"#include<stdio.h>#include<string>#include<iostream>#include<map>#include<stack>using namespace std;struct Node{    char data;    int next;}node[100010];bool flag[100010];int main(){    int a,b,n;    int s1,s2;    char data;    freopen("1032-in.txt","r",stdin);    while(scanf("%d%d%d",&a,&b,&n)!=EOF)    {        int pos=-1;        for(int i=0;i<n;i++)        {            scanf("%d %c %d",&s1,&data,&s2);            node[s1].next=s2;        }        int next=a;        while(next!=-1)        {            flag[next]=true;            next=node[next].next;        }        next=b;        while(next!=-1)        {            if(flag[next])            {                pos=next;                break;            }            next=node[next].next;        }        if(a==b)        {            printf("%05d\n",a);            return 0;        }        if(pos!=-1)          printf("%05d\n",pos);        else          printf("-1\n");    }    return 0;}

注意有一个测试用例是，两个起始节点是一样的。

PAT-1032


联系
我们