数据结构之哈希——学习笔记

今天看网课学习了哈希的数据结构,写下这一篇博客记录自己的学习过程。

1.哈希简介:

 

我们发现某些时候映射到小集合的时候会同时有多个值映射到一个下标里面,所以接下来是这种情况的解决方案1: 

 我们考虑当两个数字映射之后的结果是在同一个下标的时候,那么不妨可以将第二个映射到这个下标的数字往后移动到第一个空白的下标里面。

实际上上面这一种解决问题的方式存在较大的问题,当冲突之后后移的话会导致对应下标里面的值不再是本身应该映射到这个下标里面的值了。

所以考虑到第一种值冲突解决问题在有些情况的不适用,那么接下来介绍第二种值冲突的解决方案:

接下来详细介绍vector(可以理解为动态数组): 

这样的方法可以理解为开设了多个链表,每个下标都相当于是一条链表,实际上虽然这种方法已经解决了绝大多数的问题但是当遇见特殊的样例,也就是样例映射之后全部都在一个下标的时候,一样是存在问题的。

接下来看一下哈希函数的设计:

 接下来看一下字符串如何进行哈希操作:

另外请思考: 

令base为11会导致值冲突加剧,另外发生值冲突我们考虑双哈希甚至三哈希等多次哈希操作来解决,也就是设置多个base以及p的值,这样的话只有当多组的base和p计算出来的值都相同的时候我们才会认为两个字符串相同。

 接下来看一下c++中自带的hash:

接下来来看一些例题:

 代码如下:

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int P=9999971;//要模的素数
int a[200001],b[200001];
vector<int>c[P]; 
int main(){
	cin>>n>>m;//存下两篇论文的长度
	for(int i=0;i<P;i++)//将所有的链表数组清空
	c[i].clear();
	for(int i=1;i<=n;i++){
		cin>>a[i];
		c[a[i]%P].push_back(a[i]);//存下第一篇论文中所有的数字
	}
	int x=0;
	for(int i=1;i<=m;i++){
		cin>>b[i];
		bool ok=false;//假设这个数字不是抄袭的
		int v=b[i]%P;
		int l=c[v].size();
		//判断假设是否成立
		for(int j=0;j<l && !ok;j++)
			if(c[v][j]==b[i]) ok=true;
		if(ok) ++x;//如果成立 抄袭的部分加一
	}
	//判断被标记的抄袭的论文部分是否大于了一半
	if(2*x>=m) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	return 0;
}
	

这里还有一种使用map的方法:

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int P=9999973;
int a[200001],b[200001];
unordered_map<int,int>c;
int main(){
	cin>>n>>m;
	c.clear();
	for(int i=1;i<=n;i++){
		cin>>a[i];
		c[a[i]]=1;
	}
	int x;
	for(int i=1;i<=m;i++){
		cin>>b[i];
		if(c.find(b[i]) != c.end()) ++x;
	}
	if(x*2>=m) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	return 0;
}

接下来再看第二个题:

 很明显这里是使用map,这是我的代码:

#include<bits/stdc++.h>
using namespace std;
int n,m;
unordered_map<string,int>a;
unordered_map<string,int>b;
unordered_map<string,int>c;
int main(){
	cin>>n>>m;
	a.clear();
	b.clear();
	c.clear();
	for(int i=1;i<=n;i++){
		string s;
		cin>>s;
		int x,y,z;
		cin>>x>>y>>z;
		a[s]=x;
		b[s]=y;
		c[s]=z;
	}
	for(int i=1;i<=m;i++){
		string s;
		cin>>s;
		if(a.find(s)==a.end()) cout<<"-1"<<' '<<"-1"<<" "<<"-1"<<endl;
		else cout<<a[s]<<' '<<b[s]<<' '<<c[s];
	}
	return 0;
}

但是会发现上面的代码使用了三个map来分别存身高年龄专业编码,实际上这三个都可以通过一个结构体来存储:

#include<bits/stdc++.h>
using namespace std;
int n,m;
struct Info{
	int x,y,z;
};
unordered_map<string,Info>a;
int main(){
	cin>>n>>m;
	a.clear();
	for(int i=1;i<=n;i++){
		string s;
		cin>>s;
		Info temp;
		cin>>temp.x>>temp.y>>temp.z;
		a[s]=temp;
	}
	for(int i=1;i<=m;i++){
		string s;
		cin>>s;
		if(a.find(s) != a.end()) cout<<a[s].x<<' '<<a[s].y<<' '<<a[s].z<<endl;
		else cout<<"-1"<<' '<<"-1"<<' '<<"-1"<<endl;
	}
	return 0;
}

ok,接下来看下一道题目:

#include<bits/stdc++.h>
using namespace std;
int n;
unordered_map<int,int>c;
int a[200001];
int main(){
	scanf("%d",&n);
	c.clear();
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		++c[x];
	}
	int x=0,l=0;
	for(auto temp : c){
		if(temp.second>x){
		x=temp.second;
		l=0;
		}
		if(temp.second==x) a[++l]=temp.first;
	}
	sort(a+1,a+l+1);
	for(int i=1;i<=l;i++)
	cout<<a[i]<<' ';
	return 0;
}

 这道题目看似很简单实则还是有一定难度的。正常人思路肯定一开始都是利用数组来存储每个数字出现的次数然后最后遍历数组容量,更新出现次数最多的数字,如果遇上多个相同大的,那就利用一个数组和一个判断长度l的变量来进行不断更新和便于之后的输出。

接下来看第四题:

 代码如下:

#include<bits/stdc++.h>
using namespace std;
int n;
unordered_map<int,int>c;
int main(){
	cin>>n;
	c.clear();
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		++c[x];
	}
	int x=0;
	bool add=false;
	for(auto temp : c){
		if(temp.second & 1) add=true;
		x+=temp.second/2*2;
	}
	if(add) ++x;
	cout<<x<<endl;
	return 0;
}

最后一个题目了:

 代码如下:

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int p=9999973,base=101;
int ha[200010],hb[200010],c[200010];
char a[200010],b[200010];
int main(){
	scanf("%d%d",&n,&m);
	scanf("%s%s",a+1,b+1);
	c[0]=1;
	for(int i=1;i<=200000;i++)
	c[i]=c[i-1]*base%p;
	for(int i=1;i<=n;i++)
	ha[i]=(ha[i-1]*base+(a[i]-'a'))%p;
	for(int i=1;i<=m;i++)
	hb[i]=(hb[i-1]*base+(b[i]-'a'))%p;
	int ans=0;
	for(int i=1;i+m-1<=n;i++)
	if((ha[i+m-1]-1LL*ha[i-1]*c[m]%p+p)%p==hb[m])
	++ans;
	printf("%d\n",ans);
	return 0;
}

以上是一个单哈希的写法,c数组代表了base的i次方的值,而ha和hb分别包含了长度为i子串的哈希值最后一个for循环进行遍历计算有b子串在a子串出现了多少次。然后输出答案,接下来介绍一个双哈希的写法:

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int p=9999973,base=101;
const int p2=9999973,base2=137;
int ha[200010],hb[200010],c[200010],c2[200011],ha2[200011],hb2[200011];
char a[200010],b[200010];
int main(){
	scanf("%d%d",&n,&m);
	scanf("%s%s",a+1,b+1);
	c[0]=1;c2[0]=1;
	for(int i=1;i<=200000;i++){
	c[i]=c[i-1]*base%p;
	c2[i]=c2[i-1]*base2%p2;
	}
	for(int i=1;i<=n;i++){
	ha[i]=(ha[i-1]*base+(a[i]-'a'))%p;
	ha2[i]=(ha2[i-1]*base2+(a[i]-'a'))%p2;
	}
	for(int i=1;i<=m;i++){
	hb[i]=(hb[i-1]*base+(b[i]-'a'))%p;
	hb2[i]=(hb2[i-1]*base2+(b[i]-'a'))%p2;
	}
	int ans=0;
	for(int i=1;i+m-1<=n;i++)
	if((ha[i+m-1]-1LL*ha[i-1]*c[m]%p+p)%p==hb[m] && (ha2[i+m-1]-1LL*ha2[i-1]*c2[m]%p2+p2)%p2==hb2[m])
	++ans;
	printf("%d\n",ans);
	return 0;
}

希望今天的学习记录笔记同样对读者有所帮助。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/294676.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Python startswith()和endswith()方法及 index()方法:检测字符串中是否包含某子串

Python startswith()和endswith()方法 Python 字符串变量还可以使用 startswith() 和endswith() 方法。 startswith()方法 startswith() 方法用于检索字符串是否以指定字符串开头&#xff0c;如果是返回 True&#xff1b;反之返回 False。此方法的语法格式如下&#xff1a; …

向日葵远程工具的使用Mysql5.7的安装与配置

目录 一、向日葵远程安装与使用 二、Mysql 5.7 安装与配置 2.1 安装 2.2 Navicat Premium 12 测试连接 本机测试连接 外部访问MySQL测试连接 三、思维导图 一、向日葵远程安装与使用 简介&#xff1a; 向日葵远程控制是一款用于对远程PC进行管理和服务的软件,拥有5秒快速…

isEmpty 和 isBlank 的用法区别,居然一半的人答不上来.....

isEmpty 和 isBlank 的用法区别 isEmpty系列isBank系列 hi&#xff01;我是沁禹&#xff5e; 也许你两个都不知道,也许你除了isEmpty/isNotEmpty/isNotBlank/isBlank外,并不知道还有isAnyEmpty/isNoneEmpty/isAnyBlank/isNoneBlank的存在, come on ,让我们一起来探索org.apache…

网络调试 TCP,开发板用静态地址-入门4

用两台电脑&#xff08;无线网络&#xff09;做实验 1.1, 在电脑A上设置为Server如下&#xff1a; 选择TCP Server后&#xff0c;直接跳出用本机IP做为“本地主机地址” 1.2在 电脑B上设置为Client, 远程主机地址设置为Server的 IP 1.3, 在A, B两台电脑上能够互相发送数据 用…

[C语言]程序设计(四)

大家好&#xff0c;这里是争做图书馆扫地僧的小白。非常感谢各位的支持&#xff0c;也期待着您的关注。 目前博主有着C语言、C、linux以及数据结构的专栏&#xff0c;内容正在逐步的更新。 希望对各位朋友有所帮助同时也期望可以得到各位的支持&#xff0c;有任何问题欢迎私信与…

架构(1)

目录 1.如何理解架构的演进&#xff1f; 2.如何理解架构的服务化趋势&#xff1f; 3.架构中有哪些技术点&#xff1f; 4.谈谈架构中的缓存应用&#xff1f; 5.在开发中缓存具体如何实现&#xff1f; 1.如何理解架构的演进&#xff1f; 初始阶段的网站架构应用服务和数据服…

OpenAI ChatGPT-4开发笔记2024-02:Chat之text completion

API而已 大模型封装在库里&#xff0c;库放在服务器上&#xff0c;服务器放在微软的云上。我们能做的&#xff0c;仅仅是通过API这个小小的缝隙&#xff0c;窥探ai的奥妙。从程序员的角度而言&#xff0c;水平的高低&#xff0c;就体现在对openai的这几个api的理解程度上。 申…

自存react crash course(1)

1.创建一个react 项目 确保有node.js 创建名为react-task-tracker的react项目 npx create-react-app react-task-tracker 启动项目 npm start2.项目结构 所有组件都是放在src下面的 3. jsx // jsx语法 和html很像&#xff0c;class用的是className来使用css的样式<div…

vue3 实现关于 el-table 表格组件的封装以及调用

一、示例图&#xff1a; 二、组件 <template><div class"sn-table" :class"props.colorType 1 ? : bg-scroll"><el-table :data"tableData" :row-class-name"tableRowClassName" height"500" style"…

Ubuntu20 编译 Android 12源码

1.安装基础库 推荐使用 Ubuntu 20.04 及以上版本编译&#xff0c;会少不少麻烦&#xff0c;以下是我的虚拟机配置 执行命令安装依赖库 // 第一步执行 update sudo apt-get update//安装相关依赖sudo apt-get install -y libx11-dev:i386 libreadline6-dev:i386 libgl1-mesa-de…

海思SD3403/SS928V100开发(12)OSD显示开发

1.前言 由于需要显示一些硬件状态,暂时还没开发GUI; 所以可以使用海思平台的OSD硬件叠层来做, 下面是做的一些调试记录 2. 翻阅MPP文档 有几个地方需要注意的地方 建议使用OVERLAYER类型,支持模块多很多,还可以直接叠VO模块 3. sample测试 3.1 sample region samp…

阿贝云免费云服务器

最近体验了一下阿贝云的免费云服务器&#xff0c;总体感受是简单易上手。感兴趣的小伙伴们可以赶紧注册体验一下。 阿贝云官网&#xff1a; https://www.abeiyun.com 下图是我亲测的免费云服务器管理界面&#xff0c;免费云服务器的配置信是1核1GB&#xff0c;硬盘10GB&#x…

森林火灾图像数据集

目标是使用该数据集开发一个可以识别火焰图像的模型。收集数据是为了训练模型来区分包含火灾的图像&#xff08;火灾图像&#xff09;和常规图像&#xff08;非火灾图像&#xff09;&#xff0c;因此整个问题是二元分类。数据分为2个文件夹&#xff0c;fire_images文件夹包含75…

DASS最新论文整理@2023.12

CVPR 2023 论文来源&#xff1a;https://openaccess.thecvf.com/CVPR2023?dayall 1 Planning-oriented Autonomous Driving 面向规划的自动驾驶 (Best papper) 项目地址&#xff1a;https://opendrivelab.github.io/UniAD/ 现代自动驾驶系统的特点是按顺序执行模块化任务…

如何培养用户思维

产品开发是根据用户要求建造出系统的过程&#xff0c;产品开发是一项包括需求捕捉、需求分析、设计、实现和测试的系统工程&#xff0c;一般通过某种程序设计语言来实现。然而用户思维能够帮助企业更好地理解市场需求&#xff0c;进行产品的开发和完善&#xff0c;用户是企业产…

【项目实战】Cadence工具的使用1

需要 Candece Jasper文档的朋友可以和我联系@tommi.wei@qq.com Vmanager 自动化仿真管理工具 对于这款工具,笔者用到最多的地方就是写testplan! 没错,根据设计文档(Target Specication),细分feature list. 对于验证工程师要做的事情,就是验证设计功能的完备性,需要逐一…

LLM对齐方案再升级

Microsoft&#xff1a;WizardLM WizardLM: Empowering Large Language Models to Follow Complex Instructions GitHub - nlpxucan/WizardLM: LLMs build upon Evol Insturct: WizardLM, WizardCoder, WizardMath 要点&#xff1a;使用prompt对种子指令样本进行多样化&#x…

vue无法获取dom

处理过程 watch监听值变化 index.js:33 [Vue warn]: Error in callback for watcher "$store.state.modelsStorageUrl": "TypeError: Cannot set properties of undefined (setting modelScene)"watch: {"$store.state.modelsStorageUrl":{ha…

网页爬虫在数据分析中的作用,代理IP知识科普

在当今信息爆炸的时代&#xff0c;数据分析成为洞察信息和制定决策的不可或缺的工具。而网页爬虫&#xff0c;作为数据收集的得力助手&#xff0c;在数据分析中扮演着举足轻重的角色。今天&#xff0c;我们将一同探讨网页爬虫在数据分析中的作用。 1. 数据收集的先锋 网页爬虫…

Java爬虫之Jsoup

1.Jsoup相关概念 Jsoup很多概念和js类似&#xff0c;可参照对比理解 Document &#xff1a;文档对象。每份HTML页面都是一个文档对象&#xff0c;Document 是 jsoup 体系中最顶层的结构。 Element&#xff1a;元素对象。一个 Document 中可以着包含着多个 Element 对象&#…