[编程题]Deduplication on a Linked List
- 热度指数：5728 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
- 算法知识视频讲解
Given a singly linked list L with integer keys, you are supposed to
remove the nodes with duplicated absolute values of the keys. That is,
for each value K, only the first node of which the value or absolute
value of its key equals K will be kept. At the mean time, all the
removed nodes must be kept in a separate list. For example, given L
being 21→-15→-15→-7→15, you must output 21→-15→-7, and the removed list -15→15.
输入描述:
Each input file contains one test case. For each case, the first line contains the address of the first node, and a positive N (<= 105) which is the total number of nodes. The address of a node is a 5-digit nonnegative integer, and NULL is represented by -1.
Then N lines follow, each describes a node in the format:
Address Key Next
where Address is the position of the node, Key is an integer of which absolute value is no more than 104, and Next is the position of the next node.
输出描述:
For each case, output the resulting linked list first, then the removed list. Each node occupies a line, and is printed in the same format as in the input.
示例1
输入
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
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=100010;
struct Node{
int next,key;
}node[maxn];
int print[maxn],deleted[maxn],dup[maxn]={0}; //定义一个保留一个删除一个已重复（hash)数组
int main(){
int head,n,adress;
cin>>head>>n;
for(int i=0;i<n;i++){
cin>>adress;
cin>>node[adress].key>>node[adress].next;
} int p=0,q=0;
for(adress=head;adress!=-1;adress=node[adress].next){ //按题目给出的首地址遍历链表（排除不在链表上的无效结点）
int key=abs(node[adress].key); //结点绝对值
if(dup[key]==0){ //第一次遍历到这个key的绝对值，入保留数组并修改hash数组标记
dup[key]=1;
print[p++]=adress;
}
else deleted[q++]=adress; //并非第一次遍历到这个key的绝对值，入删除数组
}
for(int i=0;i<p;i++){
printf("%05d %d ",print[i],node[print[i]].key);
if(i!=p-1) printf("%05d\n",print[i+1]);
else printf("-1\n"); //注意链尾输出
}
for(int i=0;i<q;i++){
printf("%05d %d ",deleted[i],node[deleted[i]].key);
if(i!=q-1) printf("%05d\n",deleted[i+1]);
else printf("-1\n");
}
return 0;
}
发表于 2019-01-07 15:45:26
回复(0)
这题最聪明的做法难道不是根本不构建链表吗？
只需要判断当前节点的绝对值有没有出现过，然后
1：出现过，加入list数组里面；
2：没有出现过，加入relist数组里面。
最后只需要打印的时候，变通一下不就好了？
for (int i = 0; i < list.size(); ++i) {
printf("%05d %d ",list[i].add,list[i].values);
if(i==list.size()-1){
printf("-1\n");
}else{
printf("%05d\n",list[i+1].add);
}
} 完整代码如下： //
// Created by 江左 on 2021/2/19.
//
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <math.h>
using namespace std;
class Node{
public:
int add,values,next;
};
vector<Node>v,list,relist;
int isVisited[100001];
int main() {
int first,n;v.resize(100001);
cin>>first>>n;
for (int i = 0; i < n; ++i) {
int address;cin>>address;
v[address].add=address;
cin>>v[address].values>>v[address].next;
}
list.push_back(v[first]);isVisited[abs(v[first].values)]=1;
int nextAdd=v[first].next;
while (nextAdd!=-1){
if(isVisited[abs(v[nextAdd].values)]==0){
list.push_back(v[nextAdd]);
isVisited[abs(v[nextAdd].values)]=1;
}else
relist.push_back(v[nextAdd]);
nextAdd=v[nextAdd].next;
}
for (int i = 0; i < list.size(); ++i) {
printf("%05d %d ",list[i].add,list[i].values);
if(i==list.size()-1) printf("-1\n");
else printf("%05d\n",list[i+1].add);
}
for (int i = 0; i < relist.size(); ++i) {
printf("%05d %d ",relist[i].add,relist[i].values);
if(i==relist.size()-1) printf("-1\n");
else printf("%05d\n",relist[i+1].add);
}
return 0;
}
发表于 2021-02-19 22:11:40
回复(0)
#include <iostream>
#include <iomanip>
#include <cmath>
#include <vector>
using namespace std;
const int maxn = 100001;
const int maxk = 10001;
class Node {
public:
int addr;
int next;
int key;
Node();
};
Node::Node() {
addr = -1;
next = -1;
key = 0;
}
Node list[maxn];
bool check[maxk] = {false};
vector<Node> use, pass;
int main () {
int faddr, n;
cin >> faddr >> n;
for (int i = 0; i < n; i++) {
int addr, key, next;
cin >> addr >> key >> next;
list[addr].addr = addr;
list[addr].key = key;
list[addr].next = next;
}
int index = faddr;
while(index != -1) {
Node n = list[index];
int key = abs(n.key);
if (!check[key]) {
use.push_back(n);
check[key] = true;
} else {
pass.push_back(n);
}
index = n.next;
}
for (size_t i = 0; i < use.size(); i++) {
if (i != use.size() - 1) {
cout << setw(5) << setfill('0') << use[i].addr << " ";
cout << use[i].key << " ";
cout << setw(5) << setfill('0') << use[i + 1].addr << endl;
} else {
cout << setw(5) << setfill('0') << use[i].addr << " ";
cout << use[i].key << " ";
cout << "-1" << endl;
}
}
for (size_t i = 0; i < pass.size(); i++) {
if (i != pass.size() - 1) {
cout << setw(5) << setfill('0') << pass[i].addr << " ";
cout << pass[i].key << " ";
cout << setw(5) << setfill('0') << pass[i + 1].addr << endl;
} else {
cout << setw(5) << setfill('0') << pass[i].addr << " ";
cout << pass[i].key << " ";
cout << "-1" << endl;
}
}
return 0;
}
发表于 2020-09-15 17:13:26
回复(0)
这题主要考察空间换时间，用大数组记录链表以实现乱序链表输入，用mark记录数字是否出现以避开查找。
#include<iostream>
using namespace std;
int link[100001];
int Data[100001];
bool mark[10001];
int main() {
int begin;
int N;
cin >> begin >> N;
int temp1;
for (int i = 0; i < N; i++) {
cin >> temp1;
cin >> Data[temp1] >> link[temp1];
}
int tempAdd = begin;
int advance = -1;
int deleteStart = -1;
int deleteCurrent = -1;
while (tempAdd != -1) {
int value = Data[tempAdd];
if (value < 0) {
value = -value;
}
if (!mark[value]) {
mark[value] = true;
advance = tempAdd;
tempAdd = link[tempAdd];
}
else {
if (deleteStart == -1) {
deleteStart = tempAdd;
deleteCurrent = tempAdd;
}
else {
link[deleteCurrent] = tempAdd;
deleteCurrent = tempAdd;
}
link[advance] = link[tempAdd];
tempAdd = link[tempAdd];
}
}
link[deleteCurrent] = -1;
int coutAdd = begin;
int coutDel = deleteStart;
while (coutAdd != -1) {
printf("%05d %d ", coutAdd, Data[coutAdd]);
if (link[coutAdd] == -1) {
printf("%d\n", link[coutAdd]);
}
else {
printf("%05d\n", link[coutAdd]);
}
coutAdd = link[coutAdd];
}
while (coutDel != -1) {
printf("%05d %d ", coutDel, Data[coutDel]);
if (link[coutDel] == -1) {
printf("%d\n", link[coutDel]);
}
else {
printf("%05d\n", link[coutDel]);
}
coutDel = link[coutDel];
}
//cin >> coutAdd;
}
发表于 2018-02-16 22:38:49
回复(0)
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String headAddress = in.next();
int n = in.nextInt();
Map<String, Node> map = new HashMap<String, Node>();
Set<Integer> set = new HashSet<Integer>();
for(int i = 0;i<n;i++){
String address = in.next();
int val = in.nextInt();
String nextAddress = in.next();
map.put(address, new Node(address,val,nextAddress));
}
Node head = map.get(headAddress);
set.add(Math.abs(head.val));
Node head2 = new Node();
Node cur = head;
Node cur2 = head2;
String nextAddress = head.nextAddress;
while(!nextAddress.equals("-1")){
Node next = map.get(nextAddress);
if(set.add(Math.abs(next.val))){
cur.next = next;
cur = next;
}else{
cur2.next = next;
cur2 = next;
}
nextAddress = next.nextAddress;
}
print(head);
print(head2.next);
}
private static void print(Node head){
while(head!=null){
System.out.print(head.address+" "+head.val+" ");
if(head.next==null){
System.out.println(-1);
break;
}else{
System.out.println(head.next.address);
}
head = head.next;
}
}
private static class Node{
String address;
int val;
String nextAddress;
Node next;
public Node() {}
public Node(String address, int val,String nextAddress) {
this.address = address;
this.val = val;
this.nextAddress = nextAddress;
}
}
}
编辑于 2016-07-17 10:34:25
回复(0)
#include <iostream>
#include <cstring>
#include <string>
using namespace std;
int a[1000000];
int Next[1000000];
bool c[10005];
int main()
{ int n,head; cin>>head>>n; for(int i=0;i<n;i++) { int x; cin>>x; cin>>a[x]>>Next[x]; } int h1=-1,h2=-1,t1=-1,t2=-1; for(;head>=0;head=Next[head]) { int x = (a[head]>=0?a[head]:-a[head]); if(c[x]) { if(t2<0) h2 = t2 = head; else t2 = Next[t2] = head; }else{ c[x] = true; if(t1<0) h1 = t1 = head; else t1 = Next[t1] = head; } } if(t1>=0) { Next[t1] = -1; for(head=h1;head>=0;head=Next[head]) { printf("%05d %d",head,a[head]); if(Next[head]>=0) printf(" %05d\n",Next[head]); else printf(" -1\n"); } } if(t2>=0) { Next[t2] = -1; for(head=h2;head>=0;head=Next[head]) { printf("%05d %d",head,a[head]); if(Next[head]>=0) printf(" %05d\n",Next[head]); else printf(" -1\n"); } } return 0;
}
发表于 2018-02-11 01:30:29
回复(0)
- 讲道理就这么简单的链表删除操作，大家都还得搞半天，我觉得主要是因为这个输出实在是***！！！好我依你的，地址按照5位输出，不足补0，好家伙，-1又变成特例！👍
题目很简单，就普通的静态链表的删除操作。---输出很***
#include<bits/stdc++.h>
#define MaxN 100000
using namespace std;
int head, rm_head = -1; //分别用于存储两个链表的头结点地址
int N;
struct node {
int val;
int next;
node() : val(0), next(-1) {}
} linklist[MaxN];
queue<int> St; //存储被删除结点的地址
bitset<MaxN> check(0); //用于查重
//输入和构建链表
void Input() {
scanf("%d%d", &head, &N);
int c = N;
while (c--) {
int addr, val, next;
scanf("%d%d%d", &addr, &val, &next);
linklist[addr].val = val;
linklist[addr].next = next;
}
}
//处理链表的去重问题
void handle() {
//正常删除链表结点的处理方式
int pre = head;
check[abs(linklist[head].val)] = 1;
for (int i = linklist[pre].next; i != -1; i = linklist[i].next) {
int val = abs(linklist[i].val);
if (!check[val]) {
check[val] = 1;
pre = i;
}//一旦出现重复结点，把这个结点删除就行，删除结点的操作需要双指针辅助
else {
linklist[pre].next = linklist[i].next;
St.push(i);
}
}
if (St.empty())
return;
//根据队列进行正确连接
int num = St.front();
St.pop();
rm_head = num;
while (!St.empty()) {
linklist[num].next = St.front();
num = linklist[num].next;
St.pop();
}
linklist[num].next = -1;
}
//打印链表即可---注意小坑--(地址打印五位数字，少了补0,-1时不能打印五位数)
void print() {
handle();
for (int i = head; i != -1; i = linklist[i].next) {
if (linklist[i].next != -1)
printf("%05d %d %05d\n", i, linklist[i].val, linklist[i].next);
else {
printf("%05d %d %d", i, linklist[i].val, linklist[i].next);
}
}
if (rm_head == -1)
return;
printf("\n");
for (int i = rm_head; i != -1; i = linklist[i].next) {
if (linklist[i].next != -1)
printf("%05d %d %05d\n", i, linklist[i].val, linklist[i].next);
else {
printf("%05d %d %d", i, linklist[i].val, linklist[i].next);
}
}
}
int main() {
Input();
print();
return 0;
}
发表于 2021-09-19 01:40:05
回复(0)
#include<bits/stdc++.h>
using namespace std;
int ne[100000];
int flag[100005];
vector<int>result;
vector<int>mv;
map<int,int>mp;
int main(){
int head,n;
cin>>head>>n;
int a,b,c;
for(int i=0;i<n;i++){
cin>>a>>b>>c;
ne[a]=c;
mp[a]=b;
}
int now=head;
for(int i=0;i<n;i++){
if(flag[int(abs(mp[now]))]){
mv.push_back(now);
}else{
result.push_back(now);
flag[int(abs(mp[now]))]=1;
}
now=ne[now];
}
for(int i=0;i<result.size()-1;i++){
printf("%05d %d %05d\n",result[i],mp[result[i]],result[i+1]);
}
printf("%05d %d %d\n",result[result.size()-1],mp[result[result.size()-1]],-1);
for(int i=0;i<mv.size()-1;i++){
printf("%05d %d %05d\n",mv[i],mp[mv[i]],mv[i+1]);
}
printf("%05d %d %d",mv[mv.size()-1],mp[mv[mv.size()-1]],-1);
}
发表于 2021-06-27 21:17:20
回复(0)
STL用上瘾了
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
vector<string> contain;
vector<string> rp;
map<string, vector<string>> tab;
map<string, string> temp;
string ad;
void DL(){
string fad=ad,tad=ad;
int i=0;
while (tad!="-1") {
if (temp.find(to_string(abs(stoi(tab[tad][0]))))!=temp.end()) {
tab[fad][1]=tab[tad][1];
rp.push_back(tad);
i=1;
}else{
temp[to_string(abs(stoi(tab[tad][0])))]=1;
}
if (i==0) {
fad=tad;
}
i=0;
tad=tab[tad][1];
}
}
int main(int argc, const char * argv[]) {
string fad,contant,nad;
int n;
cin>>ad>>n;
for (int i=0; i<n; i++) {
cin>>fad>>contant>>nad;
contain.push_back(contant);
contain.push_back(nad);
tab[fad]=contain;
contain.clear();
}
DL();
for (int i=0; i<rp.size()-1; i++) {
tab[rp[i]][1]=rp[i+1];
}
tab[*(rp.end()-1)][1]="-1";
while (ad!="-1") {
cout<<ad<<" "<<tab[ad][0]<<" "<<tab[ad][1]<<endl;
ad=tab[ad][1];
}
ad=rp[0];
while (ad!="-1") {
cout<<ad<<" "<<tab[ad][0]<<" "<<tab[ad][1]<<endl;
ad=tab[ad][1];
}
return 0;
}
发表于 2021-01-25 00:09:13
回复(0)
//想要映射关系
#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;
unordered_map<string,int>e;
unordered_map<string,string>ne;
unordered_map<string,string>pre;
unordered_map<int,int>val;
vector<pair<string,string>> str;
vector<int>vt;
int idx=1;
void insert(int x,string addre,string neadd){ //插入
e[addre]=x;
//jec_pos[idx]=addre;
ne[addre]=neadd;
pre[neadd]=addre;
}
int main(){
string ini,s,end,ini2;
cin>>ini;
int n,x;
ini2=ini;
cin>>n;
while(n--){ //排序
cin>>s>>x>>end;
insert(x,s,end);
}
while(ne[ini]!="-1"){ //处理
int t=e[ini];
if(val[abs(t)]>0) {
ne[pre[ini]]=ne[ini]; //双向链表，不要的时候，将前后两个节点连接
pre[ne[ini]]=pre[ini];
vt.push_back(t);
str.push_back({ini,ne[ini]});
}
val[abs(t)]++;
ini=ne[ini];
}
int t=e[ini];
if(val[abs(t)]>0) {
ne[pre[ini]]=ne[ini];
pre[ne[ini]]=pre[ini];
vt.push_back(t);
str.push_back({ini,ne[ini]});
}
ini=ini2; //恢复初始节点
while(ne[ini]!="-1"){
cout<<ini<<" "<<e[ini]<<" "<<ne[ini]<<endl;
ini=ne[ini];
}
cout<<ini<<" "<<e[ini]<<" "<<"-1"<<endl;
for(int i=0;i<str.size();i++){
if(i==str.size()-1){
cout<<str[i].first<<" "<<vt[i]<<" "<<"-1"<<endl;
}
else cout<<str[i].first<<" "<<vt[i]<<" "<<str[i+1].first<<endl;
}
return 0;
}
作者：magpie
链接：https://www.acwing.com/solution/content/27535/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
发表于 2020-12-23 10:34:04
回复(0)
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
const int MAX = 1e5;
unordered_map<string, string> Next;
unordered_map<string, int> value;
vector<pair<string, int>> link, removeLink;
bool vis[MAX];
int main()
{
ios::sync_with_stdio(false);
string start;
int n;
cin >> start >> n;
while (n--)
{
string current, next;
int val;
cin >> current >> val >> next;
Next[current] = next;
value[current] = val;
}
string tmp; //指向上一个没有重复的结点
for (string cur = start; cur != "-1"; cur = Next[cur])
{
if (!vis[abs(value[cur])])
{
link.push_back({cur, value[cur]});
tmp = cur;
}
else
{
removeLink.push_back({cur, value[cur]});
Next[tmp] = Next[cur]; //结点重复删去，并使上一个结点指向该重复结点的下一个结点
}
vis[abs(value[cur])] = true;
}
//cout << "-----------------------" << endl;
for (auto ans : link)
cout << ans.first << " " << ans.second << " " << Next[ans.first] << endl;
for (int i = 0; i < removeLink.size(); i++)
cout << removeLink[i].first << " " << removeLink[i].second << " " << (i + 1 < removeLink.size() ? removeLink[i + 1].first : "-1") << endl;
}
发表于 2020-06-03 12:23:25
回复(0)
使用list的解法
PAT 的测试点1考察**测试点1 考察的是有多余无用的结点，可以考虑下面的测试点，看是否能通过**
87654 3
99999 -7 87654
23854 -15 00000
87654 15 -1
**测试点2 考察没有重复的元素**
下面的代码
#include
(849)#include
using namespace std;
#include
(849)#include
#include
struct node
{
int data;
int pos;
int next;
node():next(-1) {}
};
int sign[100002];
int main()
{
int start,N;
cin>>start>>N;
//使用Map保存结点的信息
unordered_map mapPos;
unordered_map mapData;
for(int i=0; i<N; i++)
{
int a,b,c;
cin>>a>>b>>c;
mapPos[a]=c;
mapData[a]=b;
}
//构建链表
list duo;
for(int i=0; i<N; i++)
{
//start是关键
int data=mapData[start];
int next=mapPos[start];
node *p=new node();
p->pos=start;
p->data=data;
p->next=next;
duo.push_back(p);
start=next;
//测试点1 就是考察你有多余的元素，PAT之前就考察过这样的测试点
if(p->next==-1)
break;
}
list shao;
//去重
for(auto it=duo.begin(); it!=duo.end(); it++)
{
node *p=*it;
int data=p->data;
//判断
if(data<0)
data*=-1;
if(sign[data]==0)
{
//第一次出现
sign[data]=1;
}
else
{
//第二次出现了，需要把这个结点剔除了
shao.push_back(p);
//需要吧迭代器保存到另一个变量中
auto dele=it;
//迭代器-- 否则以erase 迭代器就失效了
it--;
duo.erase(dele);
}
}
//逆遍历链表，设置每个结点的next
for(auto it =duo.rbegin(); it!=duo.rend(); it++)
{
if(it==duo.rbegin())
{
start=(*it)->pos;
(*it)->next=-1;
}
else
{
(*it)->next=start;
start=(*it)->pos;
}
}
for(auto it =shao.rbegin(); it!=shao.rend(); it++)
{
if(it==shao.rbegin())
{
start=(*it)->pos;
(*it)->next=-1;
}
else
{
(*it)->next=start;
start=(*it)->pos;
}
}
for(auto it=duo.begin(); it!=duo.end(); it++)
{
node *p=*it;
//coutposdatanext<<endl;
if(p->next==-1)
printf("%05d %d %d\n",p->pos,p->data,p->next);
else
printf("%05d %d %05d\n",p->pos,p->data,p->next);
}
for(auto it=shao.begin(); it!=shao.end(); it++)
{
node *p=*it;
//coutposdatanext<<endl;
if(p->next==-1)
printf("%05d %d %d\n",p->pos,p->data,p->next);
else
printf("%05d %d %05d\n",p->pos,p->data,p->next);
}
return 0;
}
发表于 2020-05-05 21:47:22
回复(0)
显示答案错误，不知道咋回事呀，PTA那边也显示3个是答案错误，找不出来了。。。。
#include<iostream>
(720)#include<memory.h>
#include<cmath>
using namespace std;
struct list {
int key;
int next;
list():key(-1),next(-1){}
list( int k, int n) : key(k), next(n) {}
};
list* nodes[100000];
int keys[10001];
int main() {
//freopen("C:\\Users\\47\\Desktop\\1.txt", "r", stdin);
memset(keys, 0,sizeof(keys));
int h, n;
cin >> h >> n;
while (n--) {
int address, key, nextnode;
cin >> address >> key >> nextnode;
nodes[address] = new list(key,nextnode);
}
int head = h;
int temp = head;
int pre = temp;
int removed =-1, behind =-1;
while(temp!=-1){
if (keys[abs(nodes[temp]->key)]) {
nodes[pre]->next = nodes[temp]->next;
if (removed!=-1) {
nodes[behind]->next=temp;
}
else {
removed = temp;
}
behind = temp;
}
else {
keys[abs(nodes[temp]->key)]++;
pre = temp;
}
temp = nodes[temp]->next;
}
if(behind!=-1){
nodes[behind]->next = -1;
}
temp = head;
while (temp!=-1) {
if (nodes[temp]->next != -1) {
printf("%05d %d %5d\n", temp, nodes[temp]->key, nodes[temp]->next);
}
else {
printf("%05d %d -1\n", temp, nodes[temp]->key);
}
temp = nodes[temp]->next;
}
temp = removed;
while (temp!=-1) {
if (nodes[temp]->next != -1) {
printf("%05d %d %05d\n", temp, nodes[temp]->key, nodes[temp]->next);
}
else {
printf("%05d %d -1", temp, nodes[temp]->key);
}
temp = nodes[temp]->next;
}
}
发表于 2020-02-24 19:50:28
回复(0)
#include<stdio.h>
#include<string.h>
#include<vector>
#include<math.h>
#include<stdlib.h>
using namespace std;
struct node{
int address;
int val;
int next;
}Node[100005];
int exsit[100005];
int main(){
memset(exsit,0,sizeof(exsit));
int first,N;
scanf("%d%d",&first,&N);
for(int i=0;i<N;i++){
int temp;int value;int next;
scanf("%d%d%d",&temp,&value,&next);
Node[temp].address=temp;
Node[temp].val=value;
Node[temp].next=next;
}
vector<node> v1,v2;
for(int i=first;i!=-1;i=Node[i].next){
int value=abs((int)Node[i].val);
if(exsit[value]){
if(v2.size()==0){
v2.push_back(Node[i]);
}else{
v2[v2.size()-1].next=i;
v2.push_back(Node[i]);
}
}else{
exsit[value]=1;
if(v1.size()==0){
v1.push_back(Node[i]);
}else{
v1[v1.size()-1].next=i;
v1.push_back(Node[i]);
}
}
}
for(int i=0;i<v1.size();i++)
if(i==v1.size()-1) printf("%05d %d -1\n",v1[i].address,v1[i].val);
else printf("%05d %d %05d\n",v1[i].address,v1[i].val,v1[i].next);
for(int i=0;i<v2.size();i++)
if(i==v2.size()-1) printf("%05d %d -1\n",v2[i].address,v2[i].val);
else printf("%05d %d %05d\n",v2[i].address,v2[i].val,v2[i].next);
}
#include<string.h>
#include<vector>
#include<math.h>
#include<stdlib.h>
using namespace std;
struct node{
int address;
int val;
int next;
}Node[100005];
int exsit[100005];
int main(){
memset(exsit,0,sizeof(exsit));
int first,N;
scanf("%d%d",&first,&N);
for(int i=0;i<N;i++){
int temp;int value;int next;
scanf("%d%d%d",&temp,&value,&next);
Node[temp].address=temp;
Node[temp].val=value;
Node[temp].next=next;
}
vector<node> v1,v2;
for(int i=first;i!=-1;i=Node[i].next){
int value=abs((int)Node[i].val);
if(exsit[value]){
if(v2.size()==0){
v2.push_back(Node[i]);
}else{
v2[v2.size()-1].next=i;
v2.push_back(Node[i]);
}
}else{
exsit[value]=1;
if(v1.size()==0){
v1.push_back(Node[i]);
}else{
v1[v1.size()-1].next=i;
v1.push_back(Node[i]);
}
}
}
for(int i=0;i<v1.size();i++)
if(i==v1.size()-1) printf("%05d %d -1\n",v1[i].address,v1[i].val);
else printf("%05d %d %05d\n",v1[i].address,v1[i].val,v1[i].next);
for(int i=0;i<v2.size();i++)
if(i==v2.size()-1) printf("%05d %d -1\n",v2[i].address,v2[i].val);
else printf("%05d %d %05d\n",v2[i].address,v2[i].val,v2[i].next);
}
发表于 2020-01-16 23:05:24
回复(0)
最后一个超时了,不清楚怎么回事,思路挺清晰的
package NiuCode;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class DeduplicationonaLinkedListTest {
public static class Node {
String address;
int val;
String nextaddress;
Node next;
public Node() {
}
public Node(String address, int val, String nextaddress) {
this.address = address;
this.val = val;
this.nextaddress = nextaddress;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String initaddress = sc.next();
int n = sc.nextInt();
Map<String, Node> map = new HashMap<>();
Map<Integer, Integer> visited = new HashMap<>();
List<Node> list1 = new ArrayList<>();
List<Node> list2 = new ArrayList<>();
for (int i = 0; i < n; i++) {
String address = sc.next();
Node node = new Node(address, sc.nextInt(), sc.next());
map.put(address, node);
}
list1.add(map.get(initaddress));
visited.put(Math.abs(map.get(initaddress).val), 1);
String k = initaddress;
int i = 0;
int j = 0;
while (!map.get(k).nextaddress.equals("-1")) {
Node next = map.get(map.get(k).nextaddress);
if (!visited.containsKey(Math.abs(next.val))) {
list1.add(next);
list1.get(i).next = next;
i++;
visited.put(Math.abs(next.val), 1);
} else {
list2.add(next);
if (list2.size()>1) {
list2.get(j).next = next;
j++;
}
}
k = next.address;
}
for (Node node : list1) {
if (node.next == null) {
System.out.println(node.address + " " + node.val + " -1");
} else {
System.out.println(node.address + " " + node.val + " " + node.next.address);
}
}
for (Node node : list2) {
if (node.next == null) {
System.out.println(node.address + " " + node.val + " -1");
} else {
System.out.println(node.address + " " + node.val + " " + node.next.address);
}
}
}
}
发表于 2019-12-04 11:44:12
回复(0)
在PTA段错误的同学注意一下只有一个节点的链表。
使用map和set可能导致超时，改用unordered_map/set即可，再有就是sync_with_stdio关掉。
这种卡时间真的没什么意思。
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <string>
using namespace std;
int main(){
ios::sync_with_stdio(false);
unordered_map<string, int> to_id;
unordered_map<int, string> to_addr;
int N;
string head_addr;
cin >> head_addr >> N;
vector<int> links(N), values(N);
int cnt = 0;
to_id[head_addr] = cnt;
to_addr[cnt] = head_addr;
cnt++;
for(int i = 1; i <= N; i++){
int key;
string addr, next;
cin >> addr >> key >> next;
if(to_id.find(addr) == to_id.end()){
to_id[addr] = cnt;
to_addr[cnt] = addr;
cnt++;
}
if(next == "-1"){
links[to_id[addr]] = -1;
values[to_id[addr]] = key;
continue;
}
if(to_id.find(next) == to_id.end()){
to_id[next] = cnt;
to_addr[cnt] = next;
cnt++;
}
links[to_id[addr]] = to_id[next];
values[to_id[addr]] = key;
}
unordered_set<int> used;
vector<int> keep, discard;
for(int cur = 0; cur != -1;){
int v = std::abs(values[cur]);
if(used.count(v) == 0){
used.insert(v);
keep.push_back(cur);
}
else{
discard.push_back(cur);
}
cur = links[cur];
}
auto print = [&](vector<int>& list){
int len = list.size();
for(int i = 0; i < len - 1; i++){
int p = list[i], q = list[i + 1];
cout << to_addr[p] << " " << values[p] << " ";
cout << to_addr[q] << endl;
}
if(len > 0){
cout << to_addr[list.back()] << " " << values[list.back()] << " ";
cout << -1 << endl;
}
};
print(keep);
print(discard);
}
发表于 2019-08-22 22:51:49
回复(0)
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
public class lianbiao { static String start,a,b; static Map<String,Node> map; static int n,c; static Set<Integer> set; public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); start = sc.next(); n = sc.nextInt(); map = new HashMap<String,Node>(); set = new HashSet<Integer>(); for(int i=0;i<n;i++) { a = sc.next(); c = sc.nextInt(); b = sc.next(); map.put(a, new Node(a,c,b)); } Node head1 = map.get(start); set.add(Math.abs(head1.val)); Node head2 = new Node(); Node now1 = head1; Node now2 = head2; b = head1.nextadd; while(!b.equals("-1")) { Node n = map.get(b); if (set.add(Math.abs(n.val))) { now1.next = n; now1 = n; } else { now2.next = n; now2 = n; } b = n.nextadd; } print(head1); print(head2.next); } private static class Node { String add,nextadd; int val; Node next; public Node() { } public Node(String add,int val,String nextadd){ this.add = add; this.val = val; this.nextadd = nextadd; } } private static void print(Node st) { while(st!=null) { System.out.print(st.add+" "+st.val+" "); if(st.next==null) { System.out.println(-1); break; } else { System.out.println(st.next.add); } st = st.next; } }
}
用python写了超时，就用JAVA写了一个。。。注意的是，引包的时间长短会影响结果是否超时
发表于 2018-12-01 12:54:42
回复(0)
思路：花了一下午的时间认识到了 vector erase的效率是多么低下，只有最后一个不过，不
甘心，然后减枝条然后就 把vector 换成 deque了
vector 是连续的 deque 也是连续的但是存有二级指针。似乎没有人使用 list 改天遇到在研究一下。
#include <iostream>
#include <vector>
#include <math.h>
#include <fstream>
#include <string>
#include <algorithm>
#include <iomanip>
#include <deque>
using namespace std;
#define debug
#ifdef debug
ifstream ifile("case.txt");
#define cin ifile
#endif
int mark[10003] = { 0 };
int list1[100001] = { 0 };
int list2[100001] = { 0 };
struct list
{
int adr;
int number;
int nexAdr;
int count;
bool operator==(const int & l)
{
return abs(this->number) == abs(l);
}
};
void Replace(deque<struct list> & v, int startAdr)
{
int i;
struct list tmp;
for (i = startAdr; list2[i]!= -1 ; i = list2[i])
{
tmp.adr = i;
tmp.number = list1[i];
tmp.nexAdr = list2[i];
v.push_back(tmp);
}
tmp.adr = i;
tmp.number = list1[i];
tmp.nexAdr = list2[i];
v.push_back(tmp);
for (int i = 0; i < v.size(); i++)
{
mark[abs(v[i].number)]++;
v[i].count = mark[abs(v[i].number)];
}
}
void GenRomove(deque<struct list> & v1, vector<struct list> & v2)
{
for (int i = 0; i < v1.size(); )
{
// = find(v1.begin() + j, v1.end(), v1[i].number);
if (v1[i].count < 2)
{
i++;
}
else
{
deque<struct list>::iterator it = v1.begin() + i;
if (it != v1.end())
{
deque<struct list>::iterator pre = --it;
++it;
v2.push_back(*it);
if (v2.size() > 1)
{
v2[v2.size() - 2].nexAdr = v2[v2.size() - 1].adr;
}
if (++it != v1.end())
{
pre->nexAdr = it->adr;
v1.erase(--it);
}
else
{
v1.erase(--it);
}
}
}
}
}
int main()
{
vector<struct list> remove;
deque<struct list> origin;
int startAdr;
int n;
cin >> startAdr >> n;
struct list tmp;
for (int i = 0; i < n; i++)
{
cin >> tmp.adr >> tmp.number >> tmp.nexAdr;
list1[tmp.adr] = tmp.number;
list2[tmp.adr] = tmp.nexAdr;
//origin.push_back(tmp);
}
// 把原始表重新排列
Replace(origin, startAdr);
GenRomove(origin, remove);
int i;
for (i = 0; i < origin.size() - 1; i++)
{
cout << setw(5) << setfill('0') << origin[i].adr << " ";
cout << origin[i].number << " ";
cout << setw(5) << setfill('0') << origin[i].nexAdr << endl;
}
cout << setw(5) << setfill('0') << origin[i].adr << " ";
cout << origin[i].number << " " << -1 << endl;
for (i = 0; i < remove.size() - 1; i++)
{
cout << setw(5) << setfill('0') << remove[i].adr << " ";
cout << remove[i].number << " ";
cout << setw(5) << setfill('0') << remove[i].nexAdr << endl;
}
cout << setw(5) << setfill('0') << remove[i].adr << " ";
cout << remove[i].number << " " << -1 << endl;
system("pause");
}
发表于 2018-08-26 15:14:39
回复(0)
刷过的大佬请指教一下为什么。。。牛客网上的测试用例全部通过。 #include<stdio.h>
#include<math.h>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
struct Node {
int add;
int next;
int value;
int absValue;
bool operator==(const Node &tmp)const {
return absValue == tmp.absValue;
}
}list[100001];
vector<Node>res;
vector<Node>del;
map<int, int>next2id;
int start, n;
int main() {
scanf("%d %d", &start, &n);
int idx;
for (int i = 0;i < n;i++) {
scanf("%d %d %d", &list[i].add, &list[i].value, &list[i].next);
list[i].absValue = abs(list[i].value);
next2id[list[i].add] = i;
if (list[i].add == start)idx = i;
}
int k = 0,k1=0,k2=0;
while (k<n){
auto iter = find(res.begin(), res.end(), list[idx]);
if (iter == res.end()) {
res.push_back(list[idx]);
if (k1 != 0)
res[k1 - 1].next = list[idx].add;
k1++;
}
else {
del.push_back(list[idx]);
if (k2 != 0)
del[k2 - 1].next = list[idx].add;
k2++;
}
idx = next2id[list[idx].next];
k++;
}
del[del.size()-1].next=res[res.size() - 1].next = -1;
for(int i=0;i<res.size()-1;i++)
printf("%05d %d %05d\n", res[i].add, res[i].value, res[i].next);
printf("%05d %d -1\n", res[res.size() - 1].add, res[res.size() - 1].value, res[res.size() - 1].next);
for (int i = 0;i<del.size() - 1;i++)
printf("%05d %d %05d\n", del[i].add, del[i].value, del[i].next);
printf("%05d %d -1\n", del[del.size() - 1].add, del[del.size() - 1].value, del[del.size() - 1].next);
return 0;
}
#include<math.h>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
struct Node {
int add;
int next;
int value;
int absValue;
bool operator==(const Node &tmp)const {
return absValue == tmp.absValue;
}
}list[100001];
vector<Node>res;
vector<Node>del;
map<int, int>next2id;
int start, n;
int main() {
scanf("%d %d", &start, &n);
int idx;
for (int i = 0;i < n;i++) {
scanf("%d %d %d", &list[i].add, &list[i].value, &list[i].next);
list[i].absValue = abs(list[i].value);
next2id[list[i].add] = i;
if (list[i].add == start)idx = i;
}
int k = 0,k1=0,k2=0;
while (k<n){
auto iter = find(res.begin(), res.end(), list[idx]);
if (iter == res.end()) {
res.push_back(list[idx]);
if (k1 != 0)
res[k1 - 1].next = list[idx].add;
k1++;
}
else {
del.push_back(list[idx]);
if (k2 != 0)
del[k2 - 1].next = list[idx].add;
k2++;
}
idx = next2id[list[idx].next];
k++;
}
del[del.size()-1].next=res[res.size() - 1].next = -1;
for(int i=0;i<res.size()-1;i++)
printf("%05d %d %05d\n", res[i].add, res[i].value, res[i].next);
printf("%05d %d -1\n", res[res.size() - 1].add, res[res.size() - 1].value, res[res.size() - 1].next);
for (int i = 0;i<del.size() - 1;i++)
printf("%05d %d %05d\n", del[i].add, del[i].value, del[i].next);
printf("%05d %d -1\n", del[del.size() - 1].add, del[del.size() - 1].value, del[del.size() - 1].next);
return 0;
}
发表于 2018-03-05 15:26:01
回复(2)
问题信息
难度：
27条回答
10收藏
10755浏览
通过挑战的用户
-
2023-03-11 13:45:23
-
2023-03-03 16:51:40 -
2023-02-25 22:08:59
-
2023-02-25 12:05:43
-
2023-02-24 16:15:45
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
#include <cstdio> #include <cstring> #include <string> using namespace std; int Next[1000000]; int a[1000000]; bool mark[10005]; int main() { int n; int head; for (scanf("%d%d",&head,&n);n;--n) { int x; scanf("%d",&x); scanf("%d%d",a + x, Next + x); } int h1 = -1, h2 = -1, t1 = -1, t2 = -1; for (; head >= 0; head = Next[head]) { int x = (a[head] >= 0)?a[head]:(-a[head]); if (mark[x]) { if (t2 < 0) { h2 = t2 = head; } else { t2 = Next[t2] = head; } } else { mark[x] = true; if (t1 < 0) { h1 = t1 = head; } else { t1 = Next[t1] = head; } } } if (t1 >= 0) { Next[t1] = -1; for (head = h1; head >= 0; head = Next[head]) { printf("%05d %d", head, a[head]); if (Next[head] >= 0) { printf(" %05d\n", Next[head]); } else { puts(" -1"); } } } if (t2 >= 0) { Next[t2] = -1; for (head = h2; head >= 0; head = Next[head]) { printf("%05d %d", head, a[head]); if (Next[head] >= 0) { printf(" %05d\n", Next[head]); } else { puts(" -1"); } } } return 0; }