散列（哈希）及其练习题（基础）

2024-05-26 01:44
文章标签 基础 练习题 哈希 散列

本文主要是介绍散列（哈希）及其练习题（基础），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

散列

字符出现次数

 力扣经典题：两数之和

 集合运算

交

并 

差 

 字符串的出现次数

散列

导入：

有N个数和M个数，如何判断M个数中每个数是否在N中出现？

思想：空间换时间

创建hashtable，以N个数本身为索引（数组下标）构建 bool hashtable

输入x的过程中，hashtable[x]=True（若要计算出现次数，换成++）

但终归是有局限性！数字只能是整数，还不能太大，等等。

散列函数：平房区中法、取余数……

可能会冲突：（即：不是单射了）

 字符串哈希：借鉴26进制的推广：62进制

字符是否出现

 如何判断输完了？

本地devc++我可以说：c1!='\n',c1!=' ','a'<=c1<='z'都能跑，如

#include<stdio.h>
#include<string>
using namespace std;
int main()
{printf("%d",'\n'>='a');
//    char c1[27];
char c1;char c2[27]={0};
int i=0;
scanf("%c",&c1);
while(c1>='a'&&c1<='z')
{c2[c1-'a']++;scanf("%c",&c1);
}
for(int j=0;j<26;j++)
if(c2[j]>0) printf("%c %d\n",'a'+j,c2[j]);
}

然而网站上不行，得用while(scanf("%c",&c1)!=EOF)
 

#include<stdio.h>
#include<string>
using namespace std;
int main()
{
//    char c1[27];
char c1;char c2[27]={0};
int i=0;
// scanf("%c",&c1);
while(scanf("%c",&c1)!=EOF)
{c2[c1-'a']++;// scanf("%c",&c1);
}
for(int j=0;j<26;j++)
if(c2[j]>0) printf("%c %d\n",'a'+j,c2[j]);
}

 这个本地不能跑了。。

行吧，得改头换面用cstring

字符出现次数

 这里我忘了这个：

就算你定义char a[1000]，如果赋值“avx”，仍然可以使用长度strlen，仍为3

我的代码

#include<stdio.h>
#include<cstring>
using namespace std;
int main()
{char s1[1001],s2[1001];int s[26]={0};scanf("%s",&s1);scanf("%s",&s2);for(int i=0;s1[i]>='a'&&s1[i]<='z'&&i<1001;i++)s[s1[i]-'a']=1;for(int i=0;s2[i]>='a'&&s2[i]<='z'&&i<1001;i++)
{if(i==0)		printf("%d",s[s2[i]-'a']);else	printf(" %d",s[s2[i]-'a']);
}}

 答案

#include <cstdio>
#include <cstring>const int MAXN = 26;
const int MAXL = 1001;
char str1[MAXL], str2[MAXL];
bool hashTable[MAXN] = {false};int getHashKey(char c) {return c - 'a';
}int main () {scanf("%s%s", str1, str2);int len1 = strlen(str1);int len2 = strlen(str2);for (int i = 0; i < len1; i++) {hashTable[getHashKey(str1[i])] = true;}for (int i = 0; i < len2; i++) {printf("%d", hashTable[getHashKey(str2[i])]);printf(i < len2 - 1 ? " " : "\n");}return 0;
}

 力扣经典题：两数之和

简单版

 我的代码（devc++int数组长度设为1000000报错，但是网上通过了）

 #include<stdio.h>
#include<cstring>
using namespace std;
int main()
{
int n,k;
scanf("%d %d",&n,&k);
int A[n];
int h[1000000]={0};
int ans=0;
int a0=0;
for(int i=0;i<n;i++)
{scanf("%d",&a0);A[i]=a0;h[A[i]]++;	 
}for(int i=0;i<n;i++)
{
if(k>=A[i])
{
if(A[i]<=k-A[i])
{if(A[i]==k-A[i]){if(h[A[i]]>1)ans++;//printf("-%d-",A[i]);	}else if(h[k-A[i]]>0) ans++;//printf("-%d-",A[i]);
}
else break;
}
}
printf("%d",ans);}

答案（他是遍历整个，再除以二） 

#include <cstdio>const int MAXN = 100000;
const int MAXK = 1000001;
int a[MAXN], hashTable[MAXK] = {false};int main () {int n, k;scanf("%d%d", &n, &k);for (int i = 0; i < n; i++) {scanf("%d", &a[i]);hashTable[a[i]] = true;}int ans = 0;for (int i = 0; i < n; i++) {if (k - a[i] >= 0 && hashTable[k - a[i]]) {ans++;}}printf("%d", ans / 2);return 0;
}

 集合运算

交

思路：第一个数组构造哈希表，然后遍历第二个，输出值为1者

数组长度10001错误，数组长度20000，通过。。

#include<stdio.h>
#include<cstring>
using namespace std;
int main()
{
int n1,n2;
scanf("%d %d",&n1,&n2);
int A[n1],B[n2],h1[20010],h2[20010];
int a0=0;
for(int i=0;i<n1;i++)
{scanf("%d",&a0);A[i]=a0;h1[A[i]]++;	 
}
bool flag=0;
for(int i=0;i<n2;i++)
{scanf("%d",&a0);B[i]=a0;//求交集：if(h1[a0]) {if(flag) printf(" %d",a0);else printf("%d",a0);flag=1;} 
//	h2[B[i]]++;	 
}}

并 

 思路：遍历第一个数组构造哈希表，然后遍历第二个，把第一个为0的但第二个出现的数字的哈希值改为1，最后遍历整个表，输出值为1的

#include<stdio.h>
#include<cstring>
using namespace std;
int main()
{
int n1,n2;
scanf("%d %d",&n1,&n2);
int A[n1],B[n2],h1[20000]={0},h2[20000]={0};
int a0=0;
for(int i=0;i<n1;i++)
{scanf("%d",&a0);A[i]=a0;h1[A[i]]++;	 
}
bool flag=0;
for(int i=0;i<n2;i++)
{scanf("%d",&a0);B[i]=a0;//求交集：
//	if(h1[a0]) 
//	{
//		if(flag) printf(" %d",a0);
//		else printf("%d",a0);
//		flag=1;
//	} 
//并集if(!h1[a0]) h1[a0]++;
}
//并集：整个儿遍历10000？for(int i=0;i<20000;i++)
if (h1[i])
{if(flag) printf(" %d",i);else printf("%d",i);flag=1;}		}

差 

 思路：遍历第一个造出哈希表，遍历第二个，每找一个，哈希表对应值-1；最后遍历第一个集合，每输出一次，哈希值-1，直至为0

#include<stdio.h>
#include<cstring>
using namespace std;
int main()
{
int n1,n2;
scanf("%d %d",&n1,&n2);
int A[n1],B[n2],h1[20000]={0},h2[20000]={0};
int a0=0;
for(int i=0;i<n1;i++)
{scanf("%d",&a0);A[i]=a0;h1[A[i]]++;	 
}
bool flag=0;
for(int i=0;i<n2;i++)
{scanf("%d",&a0);B[i]=a0;
//求差集 if(h1[a0]) h1[a0]--;
}
for(int i=0;i<n1;i++)	
{while(h1[A[i]]){if(flag) printf(" %d",A[i]);else printf("%d",A[i]);flag=1;h1[A[i]]--;}} 
}//求交集：
//	if(h1[a0]) 
//	{
//		if(flag) printf(" %d",a0);
//		else printf("%d",a0);
//		flag=1;
//	} 
//并集
// 	if(!h1[a0]) h1[a0]++;
//}
//并集：整个儿遍历10000？
//for(int i=0;i<20000;i++)
//if (h1[i])
//{if(flag) printf(" %d",i);
//		else printf("%d",i);
//		flag=1;
//		}

 字符串的出现次数

我：

#include<stdio.h>
#include<cstring>
using namespace std;
int abc(char str[4])
{return (str[0]-'A')*26*26+(str[1]-'A')*26+(str[2]-'A');
}int main()
{int n1,n2;scanf("%d",&n1);
char s1[n1+1][5];
int si1[20000]={0};
for(int i=0;i<n1;i++)
{scanf("%s",s1[i]);
//	printf("%d",abc(s1[i]));si1[abc(s1[i])]++;
//	printf("%s&%d",s1[i],si1[abc(s1[i])]);}
scanf("%d",&n2);
char s2[n2+1][5];
for(int i=0;i<n2;i++)
{scanf("%s",s2[i]);if (si1[abc(s2[i])]) printf("%d",si1[abc(s2[i])]);else printf("0");if (i<n2-1) printf(" ");}//COD
//ABA}

 答案

#include <cstdio>const int MAXN = 26 * 26 * 26;
const int MAXL = 1001;
char str[MAXL];
int hashTable[MAXN] = {0};int getHashKey(char s[]) {return (s[0] - 'A') * 26 * 26 + (s[1] - 'A') * 26 + (s[2] - 'A');
}int main () {int n, m;scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%s", str);hashTable[getHashKey(str)]++;}scanf("%d", &m);for (int i = 0; i < m; i++) {scanf("%s", str);printf("%d", hashTable[getHashKey(str)]);printf(i < m - 1 ? " " : "\n");}return 0;}

这篇关于散列（哈希）及其练习题（基础）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1003208。

相关文章

哈希leetcode-1

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素（O(1)） 当我们要频繁的查找某个元素，第一哈希表O(1)，第二，二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储，只要开26个c
阅读更多...
usaco 1.3 Prime Cryptarithm(简单哈希表暴搜剪枝)

usaco 1.3 Prime Cryptarithm(简单哈希表暴搜剪枝)

思路： 1. 用一个 hash[ ] 数组存放输入的数字，令 hash[ tmp ]=1 。 2. 一个自定义函数 check( ) ，检查各位是否为输入的数字。 3. 暴搜。第一行数从 100到999，第二行数从 10到99。 4. 剪枝。 代码： /*ID: who jayLANG: C++TASK: crypt1*/#include<stdio.h>bool h
阅读更多...
零基础学习Redis(10) -- zset类型命令使用

零基础学习Redis(10) -- zset类型命令使用

zset是有序集合，内部除了存储元素外，还会存储一个score，存储在zset中的元素会按照score的大小升序排列，不同元素的score可以重复，score相同的元素会按照元素的字典序排列。 1. zset常用命令 1.1 zadd  zadd key [NX | XX] [GT | LT]   [CH] [INCR] score member [score member ...]
阅读更多...
dp算法练习题【8】

dp算法练习题【8】

不同二叉搜索树 96. 不同的二叉搜索树 给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。 示例 1： 输入：n = 3输出：5 示例 2： 输入：n = 1输出：1 class Solution {public int numTrees(int n) {int[] dp = new int
阅读更多...
【Linux 从基础到进阶】Ansible自动化运维工具使用

【Linux 从基础到进阶】Ansible自动化运维工具使用

Ansible自动化运维工具使用 Ansible 是一款开源的自动化运维工具，采用无代理架构（agentless），基于 SSH 连接进行管理，具有简单易用、灵活强大、可扩展性高等特点。它广泛用于服务器管理、应用部署、配置管理等任务。本文将介绍 Ansible 的安装、基本使用方法及一些实际运维场景中的应用，旨在帮助运维人员快速上手并熟练运用 Ansible。 1. Ansible的核心概念
阅读更多...
整数Hash散列总结

整数Hash散列总结

方法：    step1  :线性探测  step2 散列   当 h(k)位置已经存储有元素的时候，依次探查(h(k)+i) mod S, i=1,2,3…，直到找到空的存储单元为止。其中，S为 数组长度。 HDU 1496   a*x1^2+b*x2^2+c*x3^2+d*x4^2=0 。 x在 [-100,100] 解的个数  const int MaxN = 3000
阅读更多...
AI基础 L9 Local Search II 局部搜索

AI基础 L9 Local Search II 局部搜索

Local Beam search 对于当前的所有k个状态，生成它们的所有可能后继状态。 检查生成的后继状态中是否有任何状态是解决方案。 如果所有后继状态都不是解决方案，则从所有后继状态中选择k个最佳状态。 当达到预设的迭代次数或满足某个终止条件时，算法停止。 — Choose k successors randomly, biased towards good ones — Close
阅读更多...
哈希表的底层实现(1)---C++版

哈希表的底层实现(1)---C++版

目录 哈希表的基本原理 哈希表的优点 哈希表的缺点 应用场景 闭散列法 开散列法 开放定值法Open Addressing——线性探测的模拟实现 超大重点部分评析 链地址法Separate Chaining——哈希桶的模拟实现 哈希表（Hash Table）是一种数据结构，它通过将键（Key）映射到值（Value）的方式来实现快速的数据存储与查找。哈希表的核心概念是哈希
阅读更多...
音视频入门基础：WAV专题（10）——FFmpeg源码中计算WAV音频文件每个packet的pts、dts的实现

音视频入门基础：WAV专题（10）——FFmpeg源码中计算WAV音频文件每个packet的pts、dts的实现

一、引言 从文章《音视频入门基础：WAV专题（6）——通过FFprobe显示WAV音频文件每个数据包的信息》中我们可以知道，通过FFprobe命令可以打印WAV音频文件每个packet（也称为数据包或多媒体包）的信息，这些信息包含该packet的pts、dts： 打印出来的“pts”实际是AVPacket结构体中的成员变量pts，是以AVStream->time_base为单位的显
阅读更多...
C 语言基础之数组

C 语言基础之数组

文章目录 什么是数组数组变量的声明多维数组 什么是数组 数组，顾名思义，就是一组数。 假如班上有 30 个同学，让你编程统计每个人的分数，求最高分、最低分、平均分等。如果不知道数组，你只能这样写代码： int ZhangSan_score = 95;int LiSi_score = 90;......int LiuDong_score = 100;int Zhou
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2