首页 > 其他分享 >散列（哈希）及其练习题（基础）

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

时间：2024-05-25 18:33:14浏览次数：23  
标签：练习题 26 int scanf char 哈希 c1 include 散列

散列

导入：

有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;}

 

标签：练习题,26,int,scanf,char,哈希,c1,include,散列
From： https://blog.csdn.net/m0_68339197/article/details/139183886

相关文章

  • （十）统计学基础练习题四（50道选择题）
    本文整理了统计学基础知识相关的练习题，共50道，适用于想巩固统计学基础或备考的同学。来源：如荷学数据科学题库（技术专项-统计学一）。序号之前的题请看往期文章。151） 152） 153） 154） 155） 156） 157） 158） 159） 160） 161） 162） 163） 164） ......
  • （九）统计学基础练习题三（50道选择题）
    本文整理了统计学基础知识相关的练习题，共50道，适用于想巩固统计学基础或备考的同学。来源：如荷学数据科学题库（技术专项-统计学一）。序号之前的题请看往期文章。101）102）103）104）105）106）107）108）109）110）111）112）113）114）115）116）117）118）119）120）121）122）......
  • 47.C语言函数练习题整理
    题目来自练习册和牛客网的一些编程题目整理函数都有返回值且只有一个返回值声明类型为void可以返回空值若调用一个函数中没有return语句返回一个不确定的值形参是动态变量实参和形参之间的数据传递方式为实参到形参的单向值传递形参的值发生改变不会影响主调函数中的......
  • windows如何获取文件的哈希值
    在Windows系统中,可以使用以下几种方法来获取文件的哈希值:使用PowerShell在PowerShell中运行以下命令即可计算文件的SHA256哈希值:Get-FileHash-Path<文件路径>-AlgorithmSHA256其中<文件路径>是待计算哈希值的文件的完整路径。使用certutil命令Window......
  • redis之哈希类型
    在Redis中，哈希（Hash）类型是一种将多个键值对存储在单个键中的数据结构。哈希类型被用来表示对象，其中每个键都是对象的属性，并且每个属性都与一个值相关联。哈希类型在Redis中通常用于存储对象的属性集合。哈希类型和python中的字典类型很像哈希类型常用方法【1】hset#用于设置......
  • 查找 - 线性表 & 散列表 & 树
    线性表的查找顺序查找技巧：设置哨兵，放在下标为0的位置。intSearch_Seq(SSTableST,KeyTypekey){ST.R[0].key=key;for(inti=ST.length;ST.R[i].key!=key;i--);returni;}算法分析适用于顺序结构和链式结构，不要求记录按关键字有序。平均查找长度......
  • Python-有序字典OrderedDict练习题
    问题：读取键盘输入结果，创建n个键值对，将其排序后放入有序字典并输出。详细描述：根据提示，实现函数功能：读取n(n>0)行输入，以每一行的数据为key，行号（从0开始）为value，建立n对键值对，然后将他们按照key排序后，放入一个有序字典，最后输出这个有序字典。importcollectionsdefFunc():pairs......
  • 标准IO练习题
    目录标准IO练习题题目：分析：代码展示结果展示总结知识扩展time()函数localtime()函数标准IO练习题题目：设计程序，获取当前系统时间，把时间转换为特定格式”yy年mm月dd日星期xtt:mm:ss”，并每隔1s写入到本地磁盘中一个叫做log.txt的文本中，如果文本不存在则创建。分析：本题目需要利......
  • 文件IO练习题1
    利用标准IO函数接口实现文件拷贝，把本地磁盘的文件A中的数据完整的拷贝到另一个文本B中，如果文本B不存在则创建，要求文本A的名称和文本B的名称通过命令行传递，并进行验证是否正确。/***************************************************filename:Pro_StuInfo.c*author......
  • 哈希
    哈希字符串哈希原理核心思想：将字符串看成P进制数，P的经验值是131或13331，取这两个值的冲突概率低小技巧：取模的数用2^64，这样直接用unsignedlonglong存储，溢出的结果就是取模的结果typedefunsignedlonglongULL;constintN=1e5+10,P=131;ULLh[N],p[N];//h[k]......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99