当前位置：首页 > article >正文

PAT甲级 1097 Deduplication on a Linked List（25）

article 2024/11/15 4:21:43

文章目录

题目
题目大意
解题思路
AC代码
总结

题目

原题链接

在这里插入图片描述

题目大意

给定一个单链表 L，链表上的每个节点都存有一个键值，要删掉其中拥有重复键值绝对值的节点。也就是说，对于每个值 K，只保留键值或键值绝对值为 K 的第一个节点。同时，被删掉的节点被保存在另一个单独的链表中。

输入格式
第一行首先包含头节点地址，然后包含节点总数 N 。节点地址用一个 5 位非负整数表示（可能有前导 0），NULL 用 −1 表示。

接下来 N 行，每行描述一个节点的信息，格式如下：
Address Key Next
其中 Address 是节点地址，Key 是一个整数表示键值，Next 是下一个节点的地址。

输出格式
首先按顺序输出结果链表，然后按顺序输出删除链表。
每个节点占一行，格式与输入相同。

数据范围
1≤N≤10^5
节点键值的绝对值不会超过10^4

解题思路

这道题的数据范围不大，我们可以先定义一个节点结构体，里面存放键值key和下一个节点的地址ne，再定义结构体数组slist表示一个单链表。定义一个unordered_map<int, bool> mp 来判断节点的键值以及键值绝对值是否存在，再定义一个vector< int > ans[2] 容器，ans[0]用来存储原链表节点的地址，ans[1]用来存储删除链表节点的地址。

从头节点开始遍历整个链表，如果该节点的键值绝对值没有存在过就将该节点地址存储在容器ans[0]里，再将该节点的键值绝对值标志为存在，否则，就将该节点地址存储在容器ans[1]里。一直遍历到节点地址为空为止。

先输出结果链表，再输出删除链表。因为节点地址输出的格式是五位非负整数，可能还有前导0，我们可以用C语言的printf函数实现：

printf("%05d", node);

该代码的意思就是输出一个整数，占5位，如果不足5位就用0来补齐，默认为向右对齐。

还可以用C++的iomanip头文件中的一些函数来格式化输出，比如：setw(n)，setfill(n)

setw(n)：设置输出字段的宽度，如果输出内容小于字段宽度，就会默认填充空格并且默认为向右对齐。

setfill(n)：设置用于填充输出字段的字符，通常和setw一起使用。

AC代码

使用C语言的printf函数输出

#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;
const int N = 1e5 + 10;
struct node {
	int key;
	int ne;
}slist[N];
int main()
{
	int head, n;
	unordered_map<int, bool> mp;
	cin >> head >> n;
	while (n--)
	{
		int adress, key, next;
		cin >> adress >> key >> next;
		slist[adress].ne = next;
		slist[adress].key = key;
	}
	vector<int> ans[2];
	while (head != -1)
	{
		if (mp[abs(slist[head].key)] == false)
		{
			ans[0].push_back(head);
			mp[abs(slist[head].key)] = true;
		}
		else {
			ans[1].push_back(head);
		}
		head = slist[head].ne;
	}
	int o = 0;
	for (auto it : ans[0])
	{
		if (!o)
		{
			printf("%05d %d ", it, slist[it].key);
			o = 1;
		}
		else {
			printf("%05d\n%05d %d ", it, it, slist[it].key);
		}
	}
	printf("-1\n");
	int p = 0;
	for (auto it : ans[1])
	{
		if (!p)
		{
			printf("%05d %d ", it, slist[it].key);
			p = 1;
		}
		else {
			printf("%05d\n%05d %d ", it, it, slist[it].key);
		}
	}
	//最后这里还需要特判一下，因为当单链表的节点没有重复键值时，删除链表就为空，就不需要打印-1了
	if (p)
	{
		printf("-1\n");
	}
	return 0;
}

在这里插入图片描述

这里还有一个小坑需要注意一下，就是当单链表的节点没有重复的键值时则删除链表就为空了，最后的 -1也不需要打印了。不然还有两分是通过不了的。

在这里插入图片描述

使用C++的格式化输出

#include<iostream>
#include<iomanip>
#include<vector>
#include<unordered_map>
using namespace std;
const int N = 1e5 + 10;
struct node {
	int key;
	int ne;
}slist[N];
void Printf(vector<int>& a)
{
	for (int i = 0; i < a.size(); i++)
	{
		if (i != (a.size() - 1))
		{
			cout << setw(5) << setfill('0') << a[i] << " " << slist[a[i]].key << " " << setw(5) << setfill('0') << a[i + 1] << endl;
		}
		else {
			cout << setw(5) << setfill('0') << a[i] << " " << slist[a[i]].key << " " << "-1" << endl;
		}
	}
}
int main()
{
	int head, n;
	unordered_map<int, bool> mp;
	cin >> head >> n;
	while (n--)
	{
		int adress, key, next;
		cin >> adress >> key >> next;
		slist[adress].ne = next;
		slist[adress].key = key;
	}
	vector<int> ans[2];
	while (head != -1)
	{
		if (mp[abs(slist[head].key)] == false)
		{
			ans[0].push_back(head);
			mp[abs(slist[head].key)] = true;
		}
		else {
			ans[1].push_back(head);
		}
		head = slist[head].ne;
	}
	Printf(ans[0]);
	Printf(ans[1]);
	return 0;
}