入门篇(2)-算法初步-散列
2021/10/6 22:40:59
本文主要是介绍入门篇(2)-算法初步-散列,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
入门篇(2)-算法初步-散列
(1)散列定义与整数散列
散列(hash)是最常用的算法之一
#include<cstdio> const int maxn =100010; int hashTable[maxn]= {0}; // 数组初始化值为false int main() { int n,m,x; scanf("%d%d",&n,&m); for(int i=0; i<n; i++) { scanf("%d",&x); hashTable[x]++; //数字x出现过 } for(int i=0; i< m; i++) { scanf("%d",&x); printf("%d\n",hashTable[x]); } return 0; }
特点:就是直接把输入的数作为数组的下标来对这个数的性质进行统计。
这是一个利用空间换时间的策略。
问题:如果数组下标太大如111111111,或者一个字符串I love you 就不能直接作为数组下标了。
散列:hash,“将元素通过一个函数转换成整数,使得该整数可以尽量唯一地代表这个元素”。把这个转化函数称之为散列函数H,
如果元素在转换前是key那么转换后就是一个整数H(key)。
(2)字符串hash初步:
字符串hash是指将一个字符串S映射为一个整数,使得整数可以尽可能唯一代表字符串S.
先假设字符串均由大写字母AZ构成,视为025,
按照而二十六进制转换成十进制。
int hashFunc(char S[], int len){ int id =0; for(int i=0;i<len;i++){ id=id*26+(S[i]-'A'); // 将而十六进制转换为十进制 } return id; }
如果字符串出现了小写字母,那么可以把AZ作为0-25,az看作26~51, 这样变成了52进制转换为10进制
int hashFunc(char S[], int len) { int id =0; for(int i=0; i<len; i++) { if(S[i]<='Z'&&S[i]>='A') { id=id*26+(S[i]-'A'); // 将而十六进制转换为十进制 } else if(S[i]<='z'&&S[i]>='a') { id=id*52+(S[i]-'a')+26; } } return id; }
//查询字符串在n个字符串中出现地次数 #include<cstdio> #include<string.h> #include<cstring> using namespace std; const int maxn =100; char S[maxn][maxn],temp[maxn]; int hashTable[26*26*26+10]; int hashFunc(char S[],int len) { //字符数组 ,和字符数组地长度。 int id =0; for(int i=0; i<len-1; i++) { id=id*26+(S[i]-'A'); } return id; } int main() { int n,m; scanf("%d%d",&n,&m); for(int i=0; i<n; i++) { scanf("%s",S[i]); int id=hashFunc(S[i],strlen(S[i])); hashTable[id]++; //该字符串出现地次数+1 } for( int i=0; i<m; i++) { scanf("%s",temp); int id=hashFunc(temp,strlen(temp)); printf("%d -> %d \n",id,hashTable[id]); } return 0; }
这篇关于入门篇(2)-算法初步-散列的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现