PAT 1032 Sharing[hash][链表][一般上]
1032 Sharing (25)(25 分)
To store English words, one method is to use linked lists and store a word letter by letter. To save some space, we may let the words share the same sublist if they share the same suffix. For example, "loading" and "being" are stored as showed in Figure 1.
\ Figure 1
You are supposed to find the starting position of the common suffix (e.g. the position of "i" in Figure 1).
Input Specification:
Each input file contains one test case. For each case, the first line contains two addresses of nodes and a positive N (<= 10^5^), where the two addresses are the addresses of the first nodes of the two words, and N is the total number of nodes. The address of a node is a 5-digit positive integer, and NULL is represented by -1.
Then N lines follow, each describes a node in the format:
Address Data Next
where Address is the position of the node, Data is the letter contained by this node which is an English letter chosen from {a-z, A-Z}, and Next is the position of the next node.
Output Specification:
For each case, simply output the 5-digit starting position of the common suffix. If the two words have no common suffix, output "-1" instead.
Sample Input 1:
11111 22222 9
67890 i 00002
00010 a 12345
00003 g -1
12345 D 67890
00002 n 00003
22222 B 23456
11111 L 00001
23456 e 67890
00001 o 00010
Sample Output 1:
67890
Sample Input 2:
00001 00002 4
00001 a 10001
10001 s -1
00002 a 10002
10002 t -1
Sample Output 2:
-1
//这个代码可以在牛客网上AC,但是在pat上有最后两个测试点通不过,只得了20分,问题在哪里呢?
#include <iostream> #include <vector> #include<stdio.h> #include <algorithm> using namespace std; int node[100000]; int main() { int f,t,no; int addr,next,outs; char ch; bool flag=false; while(scanf("%d%d%d",&f,&t,&no)!=-1) { for(int i=0; i<no; i++) { scanf("%d %c %d",&addr,&ch,&next); if(next!=-1) { if(node[next]==0) node[next]=1; else { outs=next; flag=true; } } } if(!flag) printf("-1\n"); else{ printf("%5d\n",outs); flag=false; } } return 0; }
//这个我甚至都没存储什么信息,因为一个节点如果在next的位置出现了2次,那么肯定就是那个公共的呀,还有什么异议吗?这可能就是我在pat上通不过的原因,找一下。
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include <iostream> #include <vector> #include<stdio.h> #include <algorithm> using namespace std; int node[100000]; int main() { int f,t,no; int addr,next,outs=-1; char ch; bool flag=false; while(scanf("%d%d%d",&f,&t,&no)!=-1){ node[f]=1; node[t]=1; for(int i=0; i<no; i++) { scanf("%d %c %d",&addr,&ch,&next); if(next!=-1) { if(node[next]==0) node[next]=1; else if(outs==-1) { outs=next; flag=true; } } } if(f==t){ printf("%05d",f);continue;//这个是针对测试点4, //当起始地址一样时。 } if(!flag) printf("-1"); else{ printf("%05d",outs); outs=-1; flag=false; } } return 0; }
//应该是不行了,如果用只存next来做,没找到为什么测试点2和测试点5过不去,好绝望。先就这样吧。(有一个博客里是说,如果只判断next就不能判断出干扰点,而我想不出来干扰点是什么。)
大佬们的代码都是hash+模拟链表,先都把所有的点读入, 在第一条链表中出现的进行标记,第二条中出现的如果在第一条中已经出现了,那么就是这个点,
代码来自:https://www.liuchuo.net/archives/2113
#include <cstdio> using namespace std; struct NODE { char key; int next; bool flag; }node[100000]; int main() { int s1, s2, n, a, b; scanf("%d%d%d", &s1, &s2, &n); char data; for(int i = 0; i < n; i++) { scanf("%d %c %d", &a, &data, &b); node[a] = {data, b, false};//结构体居然可以这么初始化。 } for(int i = s1; i != -1; i = node[i].next) node[i].flag = true;//这样就可以模拟单链表的遍历 for(int i = s2; i != -1; i = node[i].next) { if(node[i].flag == true) { printf("%05d", i); return 0; } } printf("-1"); return 0; }
相关文章
- 数据结构与算法(三):双向链表[通俗易懂]
- Hash一致算法_一致性hash是如何做数据迁移
- 链表结构
- 【说站】python双向链表的概念介绍
- Hash一致算法_分布式一致性hash
- 双向链表[js实现] 【1】
- 第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-456 求链表各节点的平均值(C++解法)
- 高频算法题-回文链表
- 【数据结构与算法】链表2W字终极无敌总结
- 【数据结构初阶】复杂链表复制+带头双向循环链表+缓存级知识
- 复杂链表的复制算法详解编程语言
- hash灵活利用Redis嵌套Hash进行性能优化(redis嵌套)
- 值Linux系统快速计算Hash值(linux计算hash)
- joinOracle强制Hash Join优化技术研究.(oracle强制hash)
- Redis实现Hash结构存储技术(redis存hash)
- MySQL中使用Hash索引的优缺点(mysql hash索引)
- 放入Redis中的Hash值实时存取(往redis里放hash)
- 查看Redis中Hash数据类型的实际应用(查看redis hash)
- Redis链表数据存储的新维度(redis链表连载)
- 重置 Redis Hash 槽一步一脚印(redis重置hash槽)
- 轻松实现Redis Hash计算(redis计算hash)
- 从Redis解锁的范围Hash的奥秘(redis 范围hash)
- 表Redis中的Hash表丢失一场惨剧(Redis缺hash)
- 用C++实现单向循环链表的解决方法
- C++模版双向链表的实现详解
- c语言链表基本操作(带有创建链表删除打印插入)