您好,欢迎访问代理记账网站
移动应用 微信公众号 联系我们

咨询热线 -

电话 15988168888

联系客服
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

2019天梯赛 L2-1链表去重

补题
做题链接:
https://pintia.cn/problem-sets/994805046380707840/problems/994805072641245184
L2-1 链表去重
分数 25
作者 陈越
单位 浙江大学
给定一个带整数键值的链表 L,你需要把其中绝对值重复的键值结点删掉。即对每个键值 K,只有第一个绝对值等于 K 的结点被保留。同时,所有被删除的结点须被保存在另一个链表上。例如给定 L 为 21→-15→-15→-7→15,你需要输出去重后的链表 21→-15→-7,还有被删除的链表 -15→15。

输入格式:
输入在第一行给出 L 的第一个结点的地址和一个正整数 N(≤10
5
,为结点总数)。一个结点的地址是非负的 5 位整数,空地址 NULL 用 -1 来表示。

随后 N 行,每行按以下格式描述一个结点:

地址 键值 下一个结点
其中地址是该结点的地址,键值是绝对值不超过10
4
的整数,下一个结点是下个结点的地址。

输出格式:
首先输出去重后的链表,然后输出被删除的链表。每个结点占一行,按输入的格式输出。

输入样例:
00100 5
99999 -7 87654
23854 -15 00000
87654 15 -1
00000 -15 99999
00100 21 23854
输出样例:
00100 21 23854
23854 -15 99999
99999 -7 -1
00000 -15 87654
87654 15 -1
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB

当时训练赛急忙写题忽略了一个点,写出来wa了一个点
后来闲时又翻开代码发现自己有点犯病在这里插入图片描述

当时想法:对于一个结点,开一个数组存储它对应的键值,一个数组存储该点的下一个结点,一个数组存储上一个结点 ,用set来判断是否key的绝对值是否已经出现过 直接模拟整个过程,开一个ans1数组存储剩下的链表,一个ans2来存储已经删除的链表,emm 听起来还不错 然后我就写下了这份代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+50;

int fa[N],key[N],ans1[N],ans2[N],son[N];

int main()
{
    int beg,n;
    cin>>beg>>n;
    int x,y,z;
    while(n--)
    {
        cin>>x>>y>>z;
        fa[x]=z;
        if(z!=-1)son[z]=x;
        key[x]=y;
    }
    set<int> q;
    int i=beg;
    int a1=0,a2=0;
    while(i!=-1)
    {
        int a=fabs(key[i]);
        if(q.count(a)==0)
        {
            ans1[++a1]=i;
            q.insert(a);
            i=fa[i];
        }
        else//删除结点
        {
            int c=fa[i];//记录遍历路径
            int t=son[i];
            fa[t]=fa[i];
            if(fa[i]!=-1)son[fa[i]]=t;
            if(a2!=0)//将链表前后结点连接起来
            {
                fa[ans2[a2]]=i;
                son[i]=ans2[a2];
            }
            ans2[++a2]=i;
            i=c;
        }
    }
    for(int i=1; i<=a1; i++)
    {
        if(i==a1)printf("%05d %d -1\n",ans1[i],key[ans1[i]]);
        else printf("%05d %d %05d\n",ans1[i],key[ans1[i]],fa[ans1[i]]);
    }
    for(int i=1; i<=a2; i++)
    {
        if(i==a2) printf("%05d %d -1\n",ans2[i],key[ans2[i]]);
        else printf("%05d %d %05d\n",ans2[i],key[ans2[i]],fa[ans2[i]]);
    }
    return 0;
}

这是结果 目前还不知道哪里错了
在这里插入图片描述

然后,然后!一个和谐的下午,当我再次拿起这段代码,我突然发现:为啥我要这么麻烦地去弄它的前一个节点,还要修改每个节点的连接方式呢??! 我这是顺序表啊 存好答案以后ans[i+1]不就是ans[i]的next吗,何必修改呢
于是就有这段代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+50;
int fa[N],key[N],ans1[N],ans2[N];

int main()
{
    int beg,n;
    cin>>beg>>n;
    int x,y,z;
    while(n--)
    {
        cin>>x>>y>>z;
        fa[x]=z;
        key[x]=y;
    }
    set<int> q;
    int i=beg;
    int a1=0,a2=0;
    while(i!=-1)
    {
        int a=fabs(key[i]);
        if(q.count(a)==0)
        {
            ans1[++a1]=i;
            q.insert(a);
        }
        else ans2[++a2]=i;
        i=fa[i];
    }
    for(int i=1; i<=a1; i++)
    {
        if(i==a1)printf("%05d %d -1\n",ans1[i],key[ans1[i]]);
        else printf("%05d %d %05d\n",ans1[i],key[ans1[i]],ans1[i+1]);
    }
    for(int i=1; i<=a2; i++)
    {
        if(i==a2) printf("%05d %d -1\n",ans2[i],key[ans2[i]]);
        else printf("%05d %d %05d\n",ans2[i],key[ans2[i]],ans2[i+1]);
    }
    return 0;
}

比刚刚那个简单多了! (虽然代码量差别不大,但是要考虑的点少了很多)
然后过了
在这里插入图片描述
虽然我现在还是不知道上一份代码错在哪里啊哈哈 有大佬看出来望指出


分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进