哈希(数字+字符串)

模拟散列表 

维护一个集合,支持如下几种操作:

  1. I x,插入一个整数 x;
  2. Q x,询问整数 x 是否在集合中出现过;

现在要进行 N 次操作,对于每个询问操作输出对应的结果。

输入格式

第一行包含整数 N,表示操作数量。

接下来 N 行,每行包含一个操作指令,操作指令为 I xQ x 中的一种。

输出格式

对于每个询问指令 Q x,输出一个询问结果,如果 x 在集合中出现过,则输出 Yes,否则输出 No

每个结果占一行。

数据范围

1≤N≤10^5
−10^9≤x≤10^9

输入样例:

5
I 1
I 2
I 3
Q 2
Q 5

输出样例:

Yes
No

拉链法

 

开放寻址法

 

拉链法 

#include<iostream>
#include<cstring>
using namespace std;
const int N=1e5+3;// 取大于1e5的第一个质数,取质数冲突的概率最小
int h[N],e[N],ne[N],idx; //邻接表
void insert(int x)
{// c++中如果是负数 那他取模也是负的 所以 加N 再 %N 就一定是一个正数int k=(x%N+N)%N;e[idx]=x;ne[idx]=h[k];h[k]=idx;idx++;
}
bool find(int x)
{//用上面同样的 Hash函数 讲x映射到 从 0-1e5 之间的数int k=(x%N+N)%N;for(int i=h[k];i!=-1;i=ne[i]){if(e[i]==x) return true;}return false;
}int main()
{memset(h,-1,sizeof h);  //将槽先清空 空指针一般用 -1 来表示int n;cin>>n;while(n--){char op;cin>>op;int x;cin>>x;if(op=='I') insert(x);else {if(find(x)) cout<<"Yes"<<endl;else cout<<"No"<<endl;}}return 0;
}

 开放寻址法

#include<iostream>
#include<cstring>
using namespace std;
//开放寻址法一般开 数据范围的 2~3倍, 这样大概率就没有冲突了//大于数据范围的第一个质数 规定空指针为 null 0x3f3f3f3f
const int N=2e5+3,null=0x3f3f3f3f;
int h[N];
int find(int x)
{int k=(x%N+N)%N;while(h[k]!=null&&h[k]!=x){k++;if(k==N) k=0;}return k;//如果这个位置是空的, 则返回的是他应该存储的位置
}
int main()
{memset(h,0x3f,sizeof h); //规定空指针为 0x3f3f3f3fint n;cin>>n;while(n--){char op;cin>>op;int x;cin>>x;int k=find(x);if(op=='I') h[k]=x;else{if(h[k]==x) cout<<"Yes"<<endl;else cout<<"No"<<endl;}}return 0;
}

字符串哈希

给定一个长度为 n 的字符串,再给定 m 个询问,每个询问包含四个整数 l1,r1,l2,r2,请你判断 [l1,r1] 和 [l2,r2]这两个区间所包含的字符串子串是否完全相同。

字符串中只包含大小写英文字母和数字。

输入格式

第一行包含整数 n 和 m,表示字符串长度和询问次数。

第二行包含一个长度为 n 的字符串,字符串中只包含大小写英文字母和数字。

接下来 m 行,每行包含四个整数 l1,r1,l2,r2,表示一次询问所涉及的两个区间。

注意,字符串的位置从 11 开始编号。

输出格式

对于每个询问输出一个结果,如果两个字符串子串完全相同则输出 Yes,否则输出 No

每个结果占一行。

数据范围

1≤n,m≤10^5

输入样例:

8 3
aabbaabb
1 3 5 7
1 3 6 8
1 2 1 2

输出样例:

Yes
No
Yes

 

#include<iostream>
#include<cstring>
using namespace std;
const int N=1000010,P=131;
typedef unsigned long long ULL;char str[N];
ULL p[N],h[N];
// h[i]前i个字符的hash值
// 字符串变成一个p进制数字,体现了字符+顺序,需要确保不同的字符串对应不同的数字
// P = 131 或  13331 Q=2^64,在99%的情况下不会出现冲突
// 使用场景: 两个字符串的子串是否相同
ULL get(int l,int r)
{return h[r]-h[l-1]*p[r-l+1];
}
int main()
{int n,m;cin>>n>>m>>str+1;p[0]=1;//字符串从1开始编号,h[1]为前一个字符的哈希值for(int i=1;i<=n;i++){p[i]=p[i-1]*P;h[i]=h[i-1]*P+str[i];  //前缀和求整个字符串的哈希值}while(m--){int l1,r1,l2,r2;cin>>l1>>r1>>l2>>r2;if(get(l1,r1)==get(l2,r2)) puts("Yes");else puts("No");}return 0;
}

 

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

测开——Java、python、SQL、数据结构面试题整理

一、Java 1.Java中finally、final、finalize的区别 1.性质不同 &#xff08;1&#xff09;final为关键字; &#xff08;2&#xff09;finalize()为方法; &#xff08;3&#xff09;finally为为区块标志,用于try语句中; 2. 作用 &#xff08;1&#xff09;final为用于标识…

每日面经分享(Git经典题目,Git入门)

1. GitHub是什么 a. Git是一个分布式版本控制系统&#xff0c;作用是跟踪、管理和协调软件开发项目中的代码更改。 b. 提供了一种有效的方式来管理代码的版本历史&#xff0c;以及多人协作开发的能力。 2. Git的作用有哪些 a. 版本控制&#xff1a;Git可以记录每次代码更改的…

【机器学习】机器学习创建算法第4篇:K-近邻算法,学习目标【附代码文档】

机器学习&#xff08;算法篇&#xff09;完整教程&#xff08;附代码资料&#xff09;主要内容讲述&#xff1a;机器学习算法课程定位、目标&#xff0c;K-近邻算法定位,目标,学习目标,1 什么是K-近邻算法,1 Scikit-learn工具介绍,2 K-近邻算法API。K-近邻算法&#xff0c;1.4 …

EasyCVR视频汇聚平台海康Ehome2.0与5.0设备接入时的配置区别

安防视频监控/视频集中存储/云存储/磁盘阵列EasyCVR平台可拓展性强、视频能力灵活、部署轻快&#xff0c;可支持的主流标准协议有国标GB28181、RTSP/Onvif、RTMP等&#xff0c;以及支持厂家私有协议与SDK接入&#xff0c;包括海康Ehome、海大宇等设备的SDK等。平台既具备传统安…

Vue3学习笔记+报错记录

文章目录 1.创建Vue3.0工程1.1使用vue-cli创建1.2 使用vite创建工程1.3.分析Vue3工程结构 2.常用Composition2.1 拉开序幕的setup2.2 ref函数_处理基本类型2.3 ref函数_处理对象类型2.4 ref函数使用总结 1.创建Vue3.0工程 1.1使用vue-cli创建 查看vue/cli版本&#xff0c;确保…

小程序如何设置余额充值和消费功能

小程序中设置余额充值和消费功能非常重要的&#xff0c;通过让客户在小程序中进行余额充值&#xff0c;不仅可以提高用户粘性&#xff0c;还可以促进消费&#xff0c;增加用户忠诚度。以下是如何在小程序中设置余额充值和消费功能的步骤&#xff1a; 1. **设计充值入口**&…

全国航空机场分布矢量数据/旅游景点poi/全国港口码头分布/地铁站分布/火车站分布/POI矢量数据

民用航空机场是指针对包括跑道型机场、表面直升机场、高架直升机场、船上直升机场、直升机水上平台、滑翔机场、水上机场、有人操纵气球施放场以及其他专供民用航空器起降的划定区域。民用航空机场分为通用航空机场和公共运输机场&#xff1b;不包括临时机场和专用机场。 根据中…

src挖掘技巧总结分享

src挖洞技术分享 src推荐刚入门的新手首选公益src如漏洞盒子、补天src&#xff0c;因为漏洞盒子收录范围广&#xff0c;只要是国内的站点都收入&#xff0c;相比其它src平台挖掘难度非常适合新手。后续可以尝试先从一些小的src厂商入手。 首先是熟能生巧&#xff0c;我一开始挖…

10-用PySpark建立第一个Spark RDD

目录 RDD概念RDD特点建立RDD的方式不同工具建立RDD的方式使用PySpark Shell(交互环境)建立RDD使用VSCode编程建立RDD使用Jupyter Notebook建立RDD 总结 PySpark实战笔记系列第一篇 RDD概念 Apache Spark的核心组件的基础是RDD。所谓的RDD&#xff0c;即弹性分布式数据集&#…

C++读取.bin二进制文件

C读取.bin二进制文件 在C中&#xff0c;可以使用文件输入/输出流来进行二进制文件的读写操作&#xff0c;方便数据的保存和读写。 //C读取bin二进制文件 int read_bin() {std::ifstream file("data_100.bin", std::ios::in | std::ios::binary);if (file) {// 按照…

【美团笔试题汇总】2023-08-26-美团春秋招笔试题-三语言题解(CPP/Python/Java)

&#x1f36d; 大家好这里是KK爱Coding &#xff0c;一枚热爱算法的程序员 ✨ 本系列打算持续跟新小米近期的春秋招笔试题汇总&#xff5e; &#x1f4bb; ACM银牌&#x1f948;| 多次AK大厂笔试 &#xff5c; 编程一对一辅导 &#x1f44f; 感谢大家的订阅➕ 和 喜欢&#x1f…

[蓝桥杯 2017 国 C] 合根植物

[蓝桥杯 2017 国 C] 合根植物 题目描述 w 星球的一个种植园&#xff0c;被分成 m n m \times n mn 个小格子&#xff08;东西方向 m m m 行&#xff0c;南北方向 n n n 列&#xff09;。每个格子里种了一株合根植物。 这种植物有个特点&#xff0c;它的根可能会沿着南北…

docker安装Nexus,maven私服

文章目录 前言安装创建文件夹设置文件夹权限docker创建指令制作docker-compose.yaml文件 查看网站访问网页查看密码 前言 nexus作为私服的maven仓库&#xff0c;在企业级应用中&#xff0c;提供了依赖来源的稳定性&#xff0c;为构建庞大的微服务体系&#xff0c;打下基础 安…

【随笔】Git -- 高级命令(上篇)(六)

&#x1f48c; 所属专栏&#xff1a;【Git】 &#x1f600; 作  者&#xff1a;我是夜阑的狗&#x1f436; &#x1f680; 个人简介&#xff1a;一个正在努力学技术的CV工程师&#xff0c;专注基础和实战分享 &#xff0c;欢迎咨询&#xff01; &#x1f496; 欢迎大…

《QT实用小工具·十四》面板容器控件和图形字体示例

1、概述 源码放在文章末尾 面板容器控件包含如下功能&#xff1a; 支持所有widget子类对象&#xff0c;自动产生滚动条。 支持自动拉伸自动填充。 提供接口获取容器内的所有对象的指针。 可设置是否自动拉伸宽度高度。 可设置设备面板之间的间距和边距。 超级图形字体类…

蓝桥杯单片机真题实践篇

这里就不完全写思路过程代码什么的&#xff0c;这一篇文章就写我在训练真题中遇到的过程。 &#xff08;呜呜呜&#xff0c;时间不够辣&#xff0c;能做多少算多少吧....&#xff09; 十三届省赛题 问题1&#xff1a;数码管的数字消影不明显 &#xff08;参考&#xff1a;蓝…

LeetCode-热题100:21. 合并两个有序链表

题目描述 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 1&#xff1a; 输入&#xff1a; l1 [1,2,4], l2 [1,3,4] 输出&#xff1a; [1,1,2,3,4,4] 示例 2&#xff1a; 输入&#xff1a; l1 [], l2 [] 输出…

大数据基础设施搭建 - Spark

文章目录 一、解压压缩包二、修改配置文件conf/spark-env.sh三、测试提交Spark任务四、Spark on Hive配置4.1 创建hive-site.xml&#xff08;spark/conf目录&#xff09;4.2 查看hive的hive-site.xml配置与3.1配置的是否一致4.3 测试SparkSQL4.3.1 启动SparkSQL客户端&#xff…

android APP monkey 测试

monkey 测试 一、电脑ADB安装及使用详解1、什么是 Monkey 测试2、什么是ADB3、ADB的作用4、安装前提条件5、ADB下载6、ADB安装与配置 二、连接安卓手机检查是否连接上安卓手机windows端安装ADB驱动 三、 monkey测试操作指令演示指令APP包名查看方式测试效果 一、电脑ADB安装及使…

MATLAB绘制堆叠填充图--巧用句柄

MATLAB绘制堆叠填充图–巧用句柄 目录 MATLAB绘制堆叠填充图--巧用句柄1. 主要原理讲解1.1 主要函数1.2 句柄原理 2. 绘图示例2.1 准备数据2.2 绘制堆叠填充图-使用句柄控制图形属性2.3 设置填充颜色和样式2.4 添加标题和标签2.5 绘图效果 3. 结语 堆叠填充图是一种常见的数据可…