Species Tree 利用HashTable实现实例代码
Species Tree 利用HashTable实现
题目再现
题目内容:
给定一个物种演化图, 关系的表示方式如下: x y : 表示x为y的先祖。 一个物种只会有一个先祖, 一个先祖可以有很多个演化出来的物种, 请你找出每个问题询问物种的祖父物种(先祖的先祖), 每个物种会使用一个不重复的编号来表示, 如果该物种没有祖父物种的话或是不存在, 那么请将他的祖父物种当是0。(凭空而生) 保证所有物种间一定有所关连, 且不会有重复演化的现象发生, 即演化图只会是一棵树。 输入格式: 只有一组测资。 第一行会有两个数字N、Q,代表总共有N个物种及Q个问题。 接下来N-1行,每一行有两个数字x、y, 意义如题目所述。 接下来的Q行,每一行有一个数字Z, 代表要询问的物种编号。 测资范围: 1 < N < 10000 0 < Q < 1000 0 < x, y, z < 1000000 输出格式: 对于每一个询问的物种编号,将他们的祖父物种编号加总后再输出。 输入样例: 6 3 1000 2000 1000 3000 2000 4000 3000 5000 5000 6000 5000 6000 1234 输出样例: 4000 时间限制:100ms内存限制:16000kb
算法实现
1. 简单数组下标查找法
通过题目的要求,这里可以使用最简单的方法,因为输入的x , y中,y的值是确定不变的,所以这里可以定义一个y的取值范围那么大的数组,下标就是y的值,内容就是x的值,这样查找起来十分方便,时间复杂度是O(1),但是空间上就会浪费比较多了。
#include <stdio.h> #include <string.h> int main(){ int arrBucket[1000000]; int N, Q; int x, y, z; long long sum = 0; memset(arrBucket, 0, sizeof(arrBucket)); scanf("%d %d", &N, &Q); while(N -- > 1){ scanf("%d %d", &x, &y); arrBucket[y] = x; } while(Q --){ scanf("%d", &z); if(arrBucket[z] != 0){ if(arrBucket[arrBucket[z]] != 0){ sum += arrBucket[arrBucket[z]]; } } } printf("%lld", sum); return 0; }
2. Hash表实现
因为方法1中,浪费空间严重,所以这里使用Hash表实现。
#include <stdio.h> #include <stdlib.h> #define NULLKEY -1 typedef struct { int *elem; //元素 int *elemP; //父元素 int count; }HashTable; int Hash(HashTable H, int k){ return k % H.count; } void InitHashTable(HashTable *H){ int i; H->elem = (int *)malloc(sizeof(int) * H->count); H->elemP = (int *)malloc(sizeof(int) * H->count); for(i = 0; i < H->count; i ++){ H->elem[i] = NULLKEY; H->elemP[i] = NULLKEY; } } void InsertHash(HashTable *H, int key, int value){ int addr; addr = Hash(*H, key); while(H->elem[addr] != NULLKEY){ addr = (addr + 1) % H->count; } H->elem[addr] = key; H->elemP[addr] = value; } int FindHash(HashTable *H, int key, int *addr){ *addr = Hash(*H, key); while(H->elem[*addr] != key){ *addr = (*addr + 1) % H->count; if(H->elem[*addr] == NULLKEY || *addr == Hash(*H, key)){ return 0; } } return 1; } int main(){ int N, Q; int x, y, z, addr; long long sum = 0; HashTable H; scanf("%d %d", &N, &Q); H.count = N - 1; InitHashTable(&H); while(N -- > 1){ scanf("%d %d", &x, &y); InsertHash(&H, y, x); } while(Q --){ scanf("%d", &z); if(FindHash(&H, z, &addr)){ if(FindHash(&H, H.elemP[addr], &addr)){ sum += H.elemP[addr]; } } } printf("%lld", sum); return 0; }
3. 用C++的map来实现
看着用C实现起来,相对来说实现的各个功能都要自己写,这里看一下用C++的STL里面的map来实现上面的题目,非常简单(不得不说STL真的很好用,但是不如HashTable速度快,空间上也不如HashTable占用的小)
#include <iostream> #include <map> using namespace std; int main() { int n, q; cin >> n >> q; map<int,int> mp; map<int,int>::iterator it; int x, y, z; for (int i=1; i<n; ++i) { cin >> x >> y; mp.insert(pair<int,int>(y,x)); } int sum = 0; for (int i=0; i<q; ++i) { cin >> z; it = mp.find(z); if (it != mp.end()) { it = mp.find(it->second); if (it != mp.end()) sum += it->second; } } cout << sum; return 0; }
感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!
相关文章
关于antd tree和父子组件之间的传值问题(react 总结)
这篇文章主要介绍了关于antd tree 和父子组件之间的传值问题,是小编给大家总结的一些react知识点,本文通过一个项目需求实例代码详解给大家介绍的非常详细,需要的朋友可以参考下...2021-06-02- 这篇文章主要介绍了Bootstrap树形组件jqTree的简单封装,封装一个稍微完整点的树形组件,感兴趣的小伙伴们可以参考一下...2016-01-26
基于element-ui封装可搜索的懒加载tree组件的实现
这篇文章主要介绍了基于element-ui封装可搜索的懒加载tree组件的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-05-23- 在.NET Framework中,Hashtable是System.Collections命名空间提供的一个容器,用于处理和表现类似key/value的键值对...2020-06-25
- 最近使用到了jstree,感觉是一款灵活的、可多项定制的tree插件。下面通过本文给大家详细介绍下jstree的简单实例,需要的朋友可以参考下...2016-12-02
聊聊C# 中HashTable与Dictionary的区别说明
这篇文章主要介绍了聊聊C# 中HashTable与Dictionary的区别说明,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-01-19- 这篇文章主要介绍了jQuery zTree如何改变指定节点文本样式,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下...2020-10-17
C#将HashTable中键列表或值列表复制到一维数组的方法
这篇文章主要介绍了C#将HashTable中键列表或值列表复制到一维数组中方法,涉及C#操作HashTable的相关技巧,需要的朋友可以参考下...2020-06-25- 关于类别树的多级是一个刚接触ajax和多级类别很头痛的问题,针对那种商品种类繁多,级别层次多更是麻烦的问题,去年刚学asp.net,实验室的同学曾经这样做过,递归sql,现在看了惊心动魄...2021-09-22
- 这篇文章主要介绍了vue el-tree 默认展开第一个节点的实现代码,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2020-05-16
- 哈希表效率高,众所周知。应用广泛,php中大部分存储使用的都是hashtable,包括变量,数组…如何使用c语言实现hashtable呢,现提供自己的思路,如有不妥之处,敬请赐教...2020-04-25
C#中哈希表(HashTable)用法实例详解(添加/移除/判断/遍历/排序等)
这篇文章主要介绍了C#中哈希表(HashTable)用法,简单讲述了哈希表的原理并结合实例形式详细分析了C#针对哈希表进行添加、移除、判断、遍历、排序等操作的实现技巧,需要的朋友可以参考下...2020-06-25C#使用Jquery zTree实现树状结构显示 异步数据加载
这篇文章主要为大家详细介绍了C#使用Jquery zTree实现树状结构显示和异步数据加载,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-06-25- 在.NET Framework中,Hashtable是System.Collections命名空间提供的一个容器,用于处理和表现类似keyvalue的键值对,其中key通常可用来快速查找,同时key是区分大小写;value用于存储对应于key的值...2020-06-25
- 根据KEY从hashtable中获取接点,步骤是先根据KEY计算hash值,然后从hashtable中找到指定的接点或者接点链表...2020-04-25
基于BootStrap Metronic开发框架经验小结【二】列表分页处理和插件JSTree的使用
本文给大家介绍基于BootStrap Metronic开发框架经验小结【二】列表分页处理和插件JSTree的使用,介绍页面内容常用到的数据分页处理,以及Bootstrap插件JSTree的使用,非常具有参考借鉴价值,感兴趣的朋友一起学习吧...2016-05-14ThinkPHP+EasyUI之ComboTree中的会计科目树形菜单实现方法
下面小编就为大家带来一篇ThinkPHP+EasyUI之ComboTree中的会计科目树形菜单实现方法。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2017-06-11- 本文通过实例给大家详细介绍了jstree的使用技巧,需要的朋友可以参考下本文...2016-12-02
- Hashtable是System.Collections命名空间提供的一个容器,用于处理和表现类似keyvalue的键值对,所以Hashtable可以支持任何类型的keyvalue键值对...2020-06-25
- 方法一: IDictionaryEnumerator enumerator = thProduct.GetEnumerator(); while (enumerator.MoveNext()) { arrKey.Add("@"+enumerator.Key.ToString());...2020-06-25