当前位置:网站首页>PTA 天梯赛练习题集 L2-002 链表去重
PTA 天梯赛练习题集 L2-002 链表去重
2022-07-07 00:27:00 【qascetic】
链表去重
给定一个带整数键值的链表 L,你需要把其中绝对值重复的键值结点删掉。即对每个键值 K,只有第一个绝对值等于 K 的结点被保留。同时,所有被删除的结点须被保存在另一个链表上。例如给定 L 为 21→-15→-15→-7→15,你需要输出去重后的链表 21→-15→-7,还有被删除的链表 -15→15。
输入格式:
输入在第一行给出 L 的第一个结点的地址和一个正整数 N(≤105,为结点总数)。一个结点的地址是非负的 5 位整数,空地址 NULL 用 -1 来表示。
随后 N 行,每行按以下格式描述一个结点:
地址 键值 下一个结点
其中地址是该结点的地址,键值是绝对值不超过104的整数,下一个结点是下个结点的地址。
输出格式:
首先输出去重后的链表,然后输出被删除的链表。每个结点占一行,按输入的格式输出。
输入样例:
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
大概思路:用结构体当作链表节点,保存当前节点地址,值,和下一个节点的地址。用键值对容器模拟地址和链表节点的映射关系。地址为键,链表节点为值用键找到值。在一个map1中存入地址和链表节点的映射关系。用另一个map2标记当前值也没有出现过。链表节点的值为键,值为true或者false,当前键也就是当前链表节点值出现了那么就把这个键对应的值赋为true.下次又出现这个值的时候map2中用这个值当作键就可以找到true。达到去重目的。值为新的链表节点被保存在列表1,然后把已经出现的值存入另一个列表2.就能分离链表了。
AC代码(C++)
#include <iostream>
#include <map>
#include <vector>
#include <cmath>
using namespace std;
struct listNode
{
string idAddress; // 当前节点地址
int variable; // 值
string nextIdAddress; // 下一个节点地址
};
map<string, listNode> isList; // 用于管理链表地址和链表节点
map<unsigned int, bool> auditListNode; // 审核标记链表节点是否有重复
int main()
{
string head;
cin >> head; // 链表头
int n;
cin >> n; // 链表节点数量也就是链表长度
for (int i = 0; i < n; i++)
{
string thisNowIdAddress; // 当前节点地址
string nextNowIdAddress; // 下一个节点地址
int value; // 当当前节点值
cin >> thisNowIdAddress >> value >> nextNowIdAddress;
// 地址和链表节点进行关联
isList[thisNowIdAddress] = {
thisNowIdAddress, value, nextNowIdAddress };
}
vector<listNode> ansList1; // 生成的链表1
vector<listNode> ansList2; // 生成的链表2
for (int i = 0; i < n; i++)
{
// 用地址获取当前节点
auto& tempListNode = isList[head];
// 判断当前值是否出现过
if (!auditListNode[abs(tempListNode.variable)])
{
// 发现未出现的新值那么标记已出现
auditListNode[abs(tempListNode.variable)] = true;
// 如果链表不为空也就是有上一个节点
// 那么把当前节点的地址付给上一个节点的nextIdAddress
if (0 != ansList1.size())
ansList1[ansList1.size() - 1].nextIdAddress = tempListNode.idAddress;
// 把当前节点存进列表
ansList1.push_back(tempListNode);
}
else
{
// 当前值已出现过那么就不能放到ansList1了
// 把已出现过的值放到ansList2
// 如果链表不为空也就是有上一个节点
// 那么把当前节点的地址付给上一个节点的nextIdAddress
if (0 != ansList2.size())
ansList2[ansList2.size() - 1].nextIdAddress = tempListNode.idAddress;
// 把当前节点存进列表
ansList2.push_back(tempListNode);
}
// 当前节点后已经是空了也就是nextIdAddress了 那么循环结束链表已经没了剩下的忽略掉
if ("-1" == tempListNode.nextIdAddress)
break;
// 当前节点的下一个节点地址付给head,下一轮用head里的地址找到对应节点
head = tempListNode.nextIdAddress;
}
// 整理完的链表可能在尾节点的nextIdAddress是错误地址,所以需要修正
ansList1[ansList1.size() - 1].nextIdAddress = "-1";
// ansList2 内有元素那么就是也有链表成立,也是有尾节点nextIdAddress出错可能性,所以也修正
if (0 != ansList2.size())
ansList2[ansList2.size() - 1].nextIdAddress = "-1";
// 根据题目要求遍历输出即可
for (auto& i : ansList1)
cout << i.idAddress << " " << i.variable << " " << i.nextIdAddress << endl;
for (auto& i : ansList2)
cout << i.idAddress << " " << i.variable << " " << i.nextIdAddress << endl;
return 0;
}
测试点不通过的朋友可以试试下面的测试数据。
测试数据1:
输入:
00001 4
00001 1 00002
00002 1 00003
00003 3 -1
00004 1 00002
输出:
00001 1 00003
00003 3 -1
00002 1 -1
测试数据2
输入:
00001 3
00001 1 00002
00002 2 -1
00003 3 00004
输出:
00001 1 00002
00002 2 -1
测试数据3:
输入:
00001 3
00003 1 00004
00001 2 00002
00002 1 -1
输出:
00001 2 00002
00002 1 -1
边栏推荐
- Mapbox Chinese map address
- 原生小程序 之 input切换 text与password类型
- Win configuration PM2 boot auto start node project
- The 2022 China low / no code Market Research and model selection evaluation report was released
- How does mapbox switch markup languages?
- How to get free traffic in pinduoduo new store and what links need to be optimized in order to effectively improve the free traffic in the store
- Getting started with DES encryption
- [paper reading] semi supervised left atrium segmentation with mutual consistency training
- Hcip seventh operation
- Flinksql 读写pgsql
猜你喜欢
CVE-2021-3156 漏洞复现笔记
nVisual网络可视化
AI face editor makes Lena smile
Opensergo is about to release v1alpha1, which will enrich the service governance capabilities of the full link heterogeneous architecture
bat 批示处理详解
Simple case of SSM framework
Determine whether the file is a DICOM file
架构设计的五个核心要素
404 not found service cannot be reached in SAP WebService test
得物客服一站式工作台卡顿优化之路
随机推荐
nVisual网络可视化
【已解决】记一次EasyExcel的报错【读取xls文件时全表读不报错,指定sheet名读取报错】
Hcip eighth operation
sql查询:将下一行减去上一行,并做相应的计算
AI face editor makes Lena smile
随机生成session_id
Nodejs get client IP
Differences and introduction of cluster, distributed and microservice
线性回归
What EDA companies are there in China?
不同网段之间实现GDB远程调试功能
Cve-2021-3156 vulnerability recurrence notes
Type de texte de commutation d'entrée et de mot de passe de l'applet natif
WEB架构设计过程
zabbix_get测试数据库失败
MySQL-CentOS7通过YUM安装MySQL
数据中心为什么需要一套基础设施可视化管理系统
如何提高网站权重
往图片添加椒盐噪声或高斯噪声
分布式事务介绍