L2_002链表去重（未解决）
- 啊难受我今天晚上就写了这么一道题还只通过了两个测试点，其他就答案错误和运行超时，但我又找不出代码哪错了，而且我也不觉得哪里会使他超时，循环只在读数据，处理数据，输出数据的时候各执行了一次，难道是有数据让程序陷入死循环了吗？
emmm我的思路就是普通的链表，先读进去，然后先处理第一个结点，再让pos指向（下标）上一个结点，tp指向要处理的结点，若tp结点的key已存在，则删除tp这个结点，pos的next变成tp的next，pos不变，tp变为原tp的下一个结点（即pos的下一个结点）。若被删除链表此时还是空的（用一个flag来指示），那就把tp付给delete_head（表示被删除链表的头）和delete_last（被删除链表的尾），若非空则把tp付给delete_last的next，并更新delete_last。若tp的key还不存在则使该key存在，pos变成tp，tp变成pos的下一个结点。当tp为-1时退出循环，并将delete_last的next变为-1，然后再分别已head，delete_head位开头输出链表
- 超时的那两个测试点，我把cin，cout改成scanf，printf就通过了，竟然啊啊啊啊啊啊，好吧以后要注意了！！
但第三个测试点错误还是没解决
- 啊越改越错了，错过回寝室时间了啊啊啊啊啊啊啊今天晚上三个小时啊，就这一道题还没解决，心态崩了啊啊啊啊啊权当给比赛攒运气好了T_T
https://www.cnblogs.com/yinzm/p/5499231.html
#include
#include
#include
#define N 100000
using namespace std;
struct node{
int key;
int next;
};
node arr[N];
int have[10001]={0};
int main()
{
int head,delete_head,delete_last;
int n;
cin>>head>>n;
int flag=0;
for(int i=1;
i<=n;
++i){
int xadd,xkey,xnext;
cin>>xadd>>xkey>>xnext;
node no;
no.key=xkey;
no.next=xnext;
arr[xadd]=no;
}
int a=abs(arr[head].key);
have[a]=1;
int pos=head;
int tp=arr[pos].next;
while(tp!=-1){
//int tp=arr[pos].next;
//注意审题是绝对值！！
int a=abs(arr[tp].key);
if(have[a]){
if(!flag){
delete_head=tp;
delete_last=tp;
flag=1;
}else{
arr[delete_last].next=tp;
delete_last=tp;
}
arr[pos].next=arr[tp].next;
}else{
//这里也是绝对值之前忘改了
have[a]=1;
pos=tp;
}
tp=arr[pos].next;
//pos=tp;
//此处tp可能已经被删掉了不能这样写！！
//pos=arr[pos].next;
//tp=arr[tp].next;
注意这部多余啦！！
}
arr[delete_last].next=-1;
pos=head;
int flag2=0;
while(pos!=-1){
if(flag2)
cout<
之前的问题倒是还没有解决
然后参考了这位的代码
https://www.liuchuo.net/archives/2125
思路：
结构体中有address，key，next，num。num是等下用来排序的，将bum初始值为2maxn（数组最大长度）
一开始放的时候要根据address把数据放到数组中，因为之后要遍历
对于留下链表，删除链表，其中的元素的顺序都是与原链表中相同的
所以元素的顺序就是遍历他们时遇到的顺序，并不用更改结点的next，只需利用num标记它们的先后顺序即可
用cnt1，cnt2来标记留下链表，删除链表的元素个数
当遇到key存在的点时，将其num赋为maxn+cnt2
否则赋为cnt1
然后利用num进行sort排序，由于不存在的点的num都是2maxn所以排完序后前cnt1是留下链表，cnt1后面cnt2个就是删除链表
#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include
#include
#include
#define N 100000
#define K 10001
using namespace std;
struct node
{
int addr;
int key;
int next;
int num;
};
bool comp(node &n1, node &n2)
{
return n1.num < n2.num;
}
node nums[N];
int have[K] = { 0 };
int main()
{
int start, n;
scanf("%d%d", &start, &n);
for (int i = 0;
i < N;
++i) {
nums[i].num = 2 * N;
//注意是全部都要初始化成2N而不只是读到的数据
}
for (int i = 0;
i < n;
++i) {
int taddr;
scanf("%d", &taddr);
nums[taddr].addr = taddr;
scanf("%d", &nums[taddr].key);
scanf("%d", &nums[taddr].next);
//nums[taddr].num = 2 * N;
}
int cnt1 = 0, cnt2 = 0;
int t = start;
while (t != -1) {
if (have[abs(nums[t].key)]) {
nums[t].num = N + cnt2;
++cnt2;
}
else {
have[abs(nums[t].key)] = 1;
nums[t].num = cnt1;
++cnt1;
}
t = nums[t].next;
}
sort(nums, nums + N,comp);
int cnt = cnt1 + cnt2;
for (int i = 0;
i < cnt;
++i)
{
if (i)
cout << endl;
printf("%05d %d ", nums[i].addr, nums[i].key);
if (i == cnt - 1 || i == cnt1 - 1)
cout << -1;
else
printf("%05d", nums[i+1].addr);
}
system("pause");
return 0;
}
推荐阅读
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- leetcode|leetcode 92. 反转链表 II
- 学员+3组杨子涓+202002RIA训练营W3D2+苏格拉底提问法
- 【刘哥乱谈?002】啖啖荔枝
- 游族网络|游族网络 002 -
- 超帅的js数组去重
- LeetCode|LeetCode 876. 链表的中间结点
- 学员+12组+谢翀+【202002训练营-W3D4-GROW模型】
- 学员+27组+颍儿+【202002训练营-W3D2-|学员+27组+颍儿+【202002训练营-W3D2- 用提问面对孩子的“上万个为什么”? 】
- redis|redis 链表
- C语言数据结构之二叉链表创建二叉树