当前位置:网站首页>PTA ladder game exercise set l2-002 linked list de duplication
PTA ladder game exercise set l2-002 linked list de duplication
2022-07-07 05:52:00 【qascetic】
The chain watch is weightless
Given a linked list with integer keys L, You need to delete the key node where the absolute value is repeated . For each key value K, Only the first absolute value is equal to K The nodes of are reserved . meanwhile , All deleted nodes must be saved in another linked list . For example, given L by 21→-15→-15→-7→15, You need to output the list after de duplication 21→-15→-7, And the deleted list -15→15.
Input format :
Enter... On the first line L The address of the first node and a positive integer N(≤105, Is the total number of nodes ). The address of a node is nonnegative 5 An integer , Empty address NULL use -1 To express .
And then N That's ok , Each line describes a node in the following format :
Address Key value Next node
Where the address is the address of the node , The key value is an absolute value that does not exceed 104 The integer of , The next node is the address of the next node .
Output format :
First output the list after de duplication , Then output the deleted list . Each node occupies a row , Output... In input format .
sample input :
00100 5
99999 -7 87654
23854 -15 00000
87654 15 -1
00000 -15 99999
00100 21 23854
sample output :
00100 21 23854
23854 -15 99999
99999 -7 -1
00000 -15 87654
87654 15 -1
General idea : Use structure as linked list node , Save the current node address , value , And the address of the next node . Simulate the mapping relationship between the address and the linked list node of the container with the key value . Address as key , The linked list node uses the key to find the value for the value . In a map1 The mapping relationship between the stored address and the linked list node . With another map2 The current value of the tag has not appeared . The value of the linked list node is the key , The value is true perhaps false, If the current key, that is, the current linked list node value, appears, assign the value corresponding to this key to true. The next time this value appears map2 Use this value as a key in to find true. Achieve the goal of de duplication . The value of the new linked list node is saved in the list 1, Then save the existing values into another list 2. You can separate the linked list .
AC Code (C++)
#include <iostream>
#include <map>
#include <vector>
#include <cmath>
using namespace std;
struct listNode
{
string idAddress; // Current node address
int variable; // value
string nextIdAddress; // Next node address
};
map<string, listNode> isList; // Used to manage linked list addresses and linked list nodes
map<unsigned int, bool> auditListNode; // Check whether there are duplicates in the marked linked list nodes
int main()
{
string head;
cin >> head; // Chain head
int n;
cin >> n; // The number of linked list nodes is the length of the linked list
for (int i = 0; i < n; i++)
{
string thisNowIdAddress; // Current node address
string nextNowIdAddress; // Next node address
int value; // When the current node value
cin >> thisNowIdAddress >> value >> nextNowIdAddress;
// The address is associated with the linked list node
isList[thisNowIdAddress] = {
thisNowIdAddress, value, nextNowIdAddress };
}
vector<listNode> ansList1; // Generated linked list 1
vector<listNode> ansList2; // Generated linked list 2
for (int i = 0; i < n; i++)
{
// Get the current node with the address
auto& tempListNode = isList[head];
// Judge whether the current value has appeared
if (!auditListNode[abs(tempListNode.variable)])
{
// If a new value is found that does not appear, then the tag has appeared
auditListNode[abs(tempListNode.variable)] = true;
// If the linked list is not empty, there is a previous node
// Then pay the address of the current node to the address of the previous node nextIdAddress
if (0 != ansList1.size())
ansList1[ansList1.size() - 1].nextIdAddress = tempListNode.idAddress;
// Save the current node into the list
ansList1.push_back(tempListNode);
}
else
{
// If the current value has already appeared, it cannot be put into ansList1 了
// Put the existing value into ansList2
// If the linked list is not empty, there is a previous node
// Then pay the address of the current node to the address of the previous node nextIdAddress
if (0 != ansList2.size())
ansList2[ansList2.size() - 1].nextIdAddress = tempListNode.idAddress;
// Save the current node into the list
ansList2.push_back(tempListNode);
}
// The current node is empty, that is nextIdAddress 了 Then the cycle ends and the linked list is gone. The rest is ignored
if ("-1" == tempListNode.nextIdAddress)
break;
// The next node address of the current node is paid to head, For the next round head Find the corresponding node from the address in
head = tempListNode.nextIdAddress;
}
// The sorted list may be in the end node nextIdAddress Is the wrong address , So it needs to be fixed
ansList1[ansList1.size() - 1].nextIdAddress = "-1";
// ansList2 If there are elements in it, then there is also a linked list , There are also tail nodes nextIdAddress Possibility of error , So also correct
if (0 != ansList2.size())
ansList2[ansList2.size() - 1].nextIdAddress = "-1";
// Traverse the output according to the requirements of the topic
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;
}
Friends who fail the test can try the following test data .
Test data 1:
Input :
00001 4
00001 1 00002
00002 1 00003
00003 3 -1
00004 1 00002
Output :
00001 1 00003
00003 3 -1
00002 1 -1
Test data 2
Input :
00001 3
00001 1 00002
00002 2 -1
00003 3 00004
Output :
00001 1 00002
00002 2 -1
Test data 3:
Input :
00001 3
00003 1 00004
00001 2 00002
00002 1 -1
Output :
00001 2 00002
00002 1 -1
边栏推荐
- JVM the truth you need to know
- Three level menu data implementation, nested three-level menu data
- 拼多多新店如何获取免费流量,需要从哪些环节去优化,才能有效提升店内免费流量
- Go language context explanation
- Things about data storage 2
- ForkJoin最全详解(从原理设计到使用图解)
- Différenciation et introduction des services groupés, distribués et microservices
- 4. Object mapping Mapster
- 分布式事务解决方案之2PC
- PTA 天梯赛练习题集 L2-002 链表去重
猜你喜欢
Determine whether the file is a DICOM file
Why does the data center need a set of infrastructure visual management system
SQL query: subtract the previous row from the next row and make corresponding calculations
How to improve website weight
Dynamic memory management
数字IC面试总结(大厂面试经验分享)
I didn't know it until I graduated -- the principle of HowNet duplication check and examples of weight reduction
C#可空类型
集群、分布式、微服務的區別和介紹
An example of multi module collaboration based on NCF
随机推荐
980. 不同路径 III DFS
Wechat applet Bluetooth connects hardware devices and communicates. Applet Bluetooth automatically reconnects due to abnormal distance. JS realizes CRC check bit
C nullable type
TCC of distributed transaction solutions
【日常训练--腾讯精选50】235. 二叉搜索树的最近公共祖先
PTA 天梯赛练习题集 L2-004 搜索树判断
【已解决】记一次EasyExcel的报错【读取xls文件时全表读不报错,指定sheet名读取报错】
Interview questions and salary and welfare of Shanghai byte
分布式事务解决方案之2PC
pytorch_ 01 automatic derivation mechanism
高级程序员必知必会,一文详解MySQL主从同步原理,推荐收藏
SAP ABAP BDC (batch data communication) -018
[daily training -- Tencent selected 50] 292 Nim games
Paper reading [semantic tag enlarged xlnv model for video captioning]
上海字节面试问题及薪资福利
淘寶商品詳情頁API接口、淘寶商品列錶API接口,淘寶商品銷量API接口,淘寶APP詳情API接口,淘寶詳情API接口
AI人脸编辑让Lena微笑
【日常训练--腾讯精选50】292. Nim 游戏
zabbix_get测试数据库失败
[云原生]微服务架构是什么?