当前位置: 首页 > news >正文

【蓝桥杯集训8】哈希表专题(3 / 3)

目录

手写哈希表

1、开放寻址法

2、拉链法

字符串前缀哈希表法

2058. 笨拙的手指 - 哈希表 + 秦九韶算法(进制转换)+ 枚举

秦九韶算法——将x进制数转化为十进制数


手写哈希表

活动 - AcWing

1、开放寻址法

设 h(x)=k,也就是 x 的哈希值为 k

如果在 hash[k]的位置已经有元素,持续往后遍历直到找到 >x(询问)或为空(插入)为止

注意开放寻址法一般会把数组开到数据范围的 2−3 倍,能提高效率

import java.util.*;class Main
{static int N=200003,nul=0x3f3f3f3f; //质数static int[] h=new int[N];public static int find(int x){int k=(x%N+N)%N;while(h[k]!=nul&&h[k]!=x) //如果该坑位不为空且该坑位不为x(如果x已经存过就不存了){k++;if(k==N) k=0;}return k; //如果找到x,则返回x所在的位置//如果没有找到x,则返回x应该存放的位置}public static void main(String[] args){Scanner sc=new Scanner(System.in);int n=sc.nextInt();Arrays.fill(h,nul);while(n-->0){String s=sc.next();int x=sc.nextInt();int k=find(x);if(s.equals("I")) h[k]=x;else if(s.equals("Q")){if(h[k]!=nul) System.out.println("Yes");else System.out.println("No");}}}
}

2、拉链法

设 h(11)=3,h(23)=3 ,这就是一种冲突

我们可以设一个数组h,也就是哈希的结果

对于每一个结果k,建立一个链表

把映射为 k 的所有数 x 都放在 h[k] 这个链表里

import java.util.*;class Main
{static int N=100003; //质数static int[] h=new int[N],e=new int[N],ne=new int[N];static int idx;public static void insert(int x){int k=(x%N+N)%N; //+N%N是为了让负数变成正数e[idx]=x;ne[idx]=h[k];h[k]=idx++;}public static boolean find(int x){int k=(x%N+N)%N;for(int i=h[k];i!=-1;i=ne[i])if(e[i]==x) return true;return false;}public static void main(String[] args){Scanner sc=new Scanner(System.in);int n=sc.nextInt();Arrays.fill(h,-1);while(n-->0){String s=sc.next();int x=sc.nextInt();if(s.equals("I")) insert(x);else if(s.equals("Q")){if(find(x)) System.out.println("Yes");else System.out.println("No");}}}
}

 

字符串前缀哈希表法

把字符串变成一个p进制数字(哈希值),实现不同的字符串映射到不同的数字

对形如 X_{1}X_{2}X_{3}......X_{n-1}X_{n} 的字符串,采用字符的ascii 码乘上 P 的次方来计算哈希值

映射公式 (X_{1}\times P^{n-1}+X_{2}\times P^{n-2}+......+X_{n-1}\times P^{1}+X_{n}\times P^{0})mod\ Q

注意:

  • 任意字符不可以映射成0,否则会出现不同的字符串都映射成0的情况,比如A,AA,AAA皆为0
  • 通过巧妙设置P (13113331) , Q (2^{64})的值,一般可以理解为不产生冲突

比较不同区间的子串是否相同,就转化为对应的哈希值是否相同

求一个字符串的哈希值就相当于求前缀和,求一个字符串的子串哈希值就相当于求部分和

字符串前缀和公式:

h[i] = h[i-1]*P + s[i];

区间和公式:h[l,r]=h[r]-h[l]*P^{r-l+1}

区间和公式的理解: ABCDE 与 ABC 的前三个字符值是一样,只差两位,
乘上 P^{2} 把 ABC 变为 ABC00,再用 ABCDE - ABC00 得到 DE 的哈希值

活动 - AcWing

题目:

import java.util.*;class Main
{static int N=100010;static long[] h=new long[N],p=new long[N];static int P=131;public static void main(String[] args){Scanner sc=new Scanner(System.in);int n=sc.nextInt(),m=sc.nextInt();String s="/"+sc.next();//下标从1开始p[0]=1;for(int i=1;i<=n;i++){p[i]=p[i-1]*P;h[i]=h[i-1]*P+s.charAt(i);}while(m-->0){int l1=sc.nextInt(),r1=sc.nextInt();int l2=sc.nextInt(),r2=sc.nextInt();long h1=h[r1]-h[l1-1]*p[r1-l1+1];long h2=h[r2]-h[l2-1]*p[r2-l2+1];System.out.println(h1==h2?"Yes":"No");}}
}

2058. 笨拙的手指 - 哈希表 + 秦九韶算法(进制转换)+ 枚举

2058. 笨拙的手指 - AcWing题库

题目:

第一行给你一个N的二进制表示,其中有一位是错误的

第二行给你一个N的三进制表示,其中有一位是错误的

输出N的正确十进制值(题目保证一定有唯一解)

思路:

枚举二进制数a的所有换1位的情况,转化为十进制值存入哈希表

枚举三进制数b的所有换1位情况,转化为十进制后在哈希表中查询是否存在 

因为题目保证一定有唯一解,所以两者交集即为答案

因此如果查询到,则输出

秦九韶算法——将x进制数转化为十进制数

public static int get(String s,int x)
{int res=0;for(int i=0;i<s.length();i++){char t=s.charAt(i);res=res*x + t-'0';}return res;
}
import java.util.*;class Main
{static int N=100010;public static int get(char[] s,int x)//将x进制数s转化为十进制数{//秦九韶算法int res=0;for(int i=0;i<s.length;i++){res=res*x+s[i]-'0';}return res;}public static void main(String[] args){Scanner sc=new Scanner(System.in);char[] a=sc.next().toCharArray();char[] b=sc.next().toCharArray();Set<Integer> st=new HashSet<>();for(int i=0;i<a.length;i++){a[i]^=1;st.add(get(a,2));a[i]^=1;}for(int i=0;i<b.length;i++){char t=b[i];for(int j=0;j<3;j++) //将这一位换成除了本身的其他数if(t-'0'!=j){b[i]=(char)(j+'0');int tp=get(b,3);if(st.contains(tp)){System.out.print(tp);return;}}b[i]=t; //换完该位要恢复现场 继续换下一位}}
}

相关文章:

【蓝桥杯集训8】哈希表专题(3 / 3)

目录 手写哈希表 1、开放寻址法 2、拉链法 字符串前缀哈希表法 2058. 笨拙的手指 - 哈希表 秦九韶算法&#xff08;进制转换&#xff09; 枚举 秦九韶算法——将x进制数转化为十进制数 手写哈希表 活动 - AcWing 1、开放寻址法 设 h(x)k&#xff0c;也就是 x 的哈希值…...

Java Scanner 类,超详细整理,适合新手入门

目录 一、什么是 Java Scanner 类&#xff1f; 二、引用数据类型 1、引用数据类型的定义 三、Scanner 类有哪些常用方法&#xff1f; hasNext()用法 四、next() 与 nextLine() 区别 next(): nextLine()&#xff1a; 五、使用 next 方法 五、使用 nextLine方法 一、什…...

干货 | 中小企业选型 Elasticsearch 避坑指南

1、线上常见问题在我线下对接企业或线上交流的时候&#xff0c;经常会遇到各种业务场景不同的问题。比如&#xff0c;常见问题归类如下&#xff1a;常见问题1&#xff1a;ES 适合场景及架构选型问题。公司的核心业务是做企业员工健康管理&#xff0c;数据来自电子化后的员工体检…...

全局组件和局部组件

全局组件第一种定义方法&#xff1a;A、创建自己的组件&#xff1a;Loading.vueB、在main.js文件中引入组件并注册import Vue from vue import App from ./App.vue import * as filters from ./filterimport quanjuzujian from ./components/quanjuzujian.vueVue.component(qua…...

提取括号中的内容

正则能解决不嵌套的括号内容提取问题遇到一个问题&#xff0c;就是需要提取字符串中每一个中括号里的内容&#xff0c;在网上搜了一下&#xff0c;发现用正则表达式(\[[^\]]*\])可以提取中括号中的内容&#xff0c;以下面文本为匹配对象&#xff1a;PerformanceManager[第1个中…...

数据结构-算法的空间复杂度(1.2)

目录 1.空间复杂度 1.1 例子 1.2 空间的特殊性质 写在最后&#xff1a; 1.空间复杂度 空间复杂度也是一个数学表达式&#xff0c; 是对一个算法在运行过程中临时占用存储空间大小的量度。 他也是用大O渐进表示法。 1.1 例子 例1&#xff1a; 冒泡排序&#xff1a; v…...

【总结】python3启动web服务引发的一系列问题

背景 在某行的实施项目&#xff0c;需要使用python3环境运行某些py脚本。 由于行内交付的机器已自带python3 &#xff0c;没有采取自行安装python3&#xff0c;但是运行python脚本时报没有tornado module。 错误信息 ModuleNotFoundError&#xff1a;No module named ‘torn…...

Linux:基于libevent读写管道代码,改进一下上一篇变成可以接收键盘输入

对上一篇进行改进&#xff0c;变成可以接收键盘输入&#xff0c;然后写入管道&#xff1a; 读端代码&#xff1a; #include <stdlib.h> #include <stdio.h> #include <unistd.h> #include <sys/types.h> #include <sys/stat.h> #include <s…...

C语言格式化输出总结:%d,%c,%s,%f, %lf,%m.nd,%m.nf,%m.ns 以及sprintf函数

凡事发生必将有益于我&#xff0c;高手&#xff0c;从来都不仅仅是具备某种思维的人&#xff0c;而是那些具备良好学习习惯的人&#xff0c;成为高手&#xff0c;无他&#xff0c;手熟尔&#xff01;加油在最近的学习之中&#xff0c;对于格式化输出这个知识点&#xff0c;这里…...

Nginx之反向代理、负载均衡、动静分离。

Nginx之反向代理、负载均衡、动静分离。 1、Nginx是啥&#xff1f; 轻量级Web服务器、反向代理服务器、电子邮件&#xff08;IMAP/POP3&#xff09;代理服务器 在 BSD-like 协议下发行、占内存少、并发高&#xff08;同时处理请求能力&#xff09;。 2、安装 官网&#xf…...

0401不定积分的概念和性质-不定积分

文章目录1 原函数与不定积分的概念1.1 原函数1.2 原函数存在定理1.3 不定积分2 不定积分的性质3 基本积分表4 例题后记1 原函数与不定积分的概念 1.1 原函数 定义1 如果在区间I上&#xff0c;可导函数F(x)的导航为f(x)&#xff0c;即对任一x∈Ix\in Ix∈I&#xff0c;都有 F′…...

数组中的各种迭代API方法手写

js的数组上有很多实用的方法&#xff0c;不论是在遍历数组上&#xff0c;还是在操作数组内元素上&#xff0c;它有许多不同的遍历数组的方法&#xff0c;同时它还有着可以直接操作数组中间元素的方法。 接下来&#xff0c;我来带大家手写数组里的 遍历方法 。 Array.forEach(…...

详解量子计算:相位反冲与相位反转

前言 本文需要对量子计算有一定的了解。需要的请翻阅我的量子专栏&#xff0c;这里不再涉及基础知识的科普。 量子相位反冲是什么&#xff1f; 相位反转&#xff08;phase kickback&#xff09;是量子计算中的一种现象&#xff0c;通常在量子算法中使用&#xff0c;例如量子…...

C++——C++11第三篇

目录 包装器 function包装器 bind 包装器 function包装器 function包装器 也叫作适配器。C中的function本质是一个类模板&#xff0c;也是一个包装器。 上面的程序验证&#xff0c;我们会发现useF函数模板实例化了三份。 包装器可以很好的解决上面的问题 &#xff0c;让它只实…...

180 2 22222

选择题(共180题,合计180.0分) 1. 在项目开工会议期间&#xff0c;项目发起人告诉产品负责人和团队项目章程即将完成。然而&#xff0c;由于存在在紧迫的期限内满足政府监管要求的压力&#xff0c;发起人希望立即开始工作。产品负责人下一步应该做什么&#xff1f; A 告诉发起人…...

成人高考初中毕业能报名吗 需要什么条件

初中学历的人员不能直接报名成人高考&#xff0c;考生需要有普通高中&#xff0c;职业高中&#xff0c;中专毕业证等高中同等学力就可以进行报名&#xff0c;在报名期间登陆所在省的教育考试院的成人高考报名入口进行报考。成人高考报名条件是什么1、遵守宪法和法律。2、国家承…...

ChatGPT初体验

ChatGPT初体验 前言 嘿嘿&#xff0c;最近啊AI ChatGPT刷新各大网站&#xff0c;对于我们国人而将很不友好&#xff0c;真的太不友好了。我呢在去年open AI发布的时候就有所关注&#xff0c;那个时候还没有像现在这样火热。谁知道短短几个月便传遍大街小巷。 一、什么是chatG…...

ChatGPT概念狂飙!究竟魅力何在?

原文&#xff1a;http://www.btcwbo.com/6988.html 近期&#xff0c;ChatGPT引领的人工智能概念在资本市场一路狂飙&#xff0c;AIGC题材持续发酵。截至2月7日&#xff0c;Wind ChatGPT指数今年以来累计上涨超50%&#xff0c;汉王科技、海天瑞声、云从科技等概念股股价已经翻倍…...

如何下载阅读Spring源码-全过程详解

这篇文章记录了下载spring源码和在IDEA中打开运行的全过程&#xff0c;并且记录了过程中遇到的问题和解决方案&#xff0c;适合需要学习spring源码的同学阅读。 1.spring源码下载地址 通过Git下载spring-framework项目源码&#xff1a; git clone https://github.com/spring…...

学了两个月的Java,最后自己什么也不会,该怎么办?

学着学着你会发现每天的知识都在更新&#xff0c;也都在遗忘&#xff0c;可能就放弃了。但是只要自己肯练&#xff0c;肯敲代码&#xff0c;学过的知识是很容易就被捡起来的。等你学透了用不了一年也可以学好 Java的运行原理&#xff1a;Java是一门编译解释型语言&#xff0c;…...

前端vue实现获取七天时间和星期几功能

前端vue实现获取七天时间和星期几功能 功能展示代码 <div v-for"(item,index) in same_week" :class"[same_dayitem.date? activ :,dis]" click"select(item)" :keyindex><span>{{item.name}}</span><span>{{item.…...

zookeeper单机部署

一.下载zookeeper压缩包 二.上传解压安装包到/data/zookeeper目录&#xff0c;并解压 tar -zxvf apache-zookeeper-3.5.8-bin.tar.gz 三.修改配置文件 cd apache-zookeeper-3.5.10-bin/conf mv zoo_sample.cfg zoo.cfg vi zoo.cfg 修改为如下&#xff1a; dataDir/data/zooke…...

单片机输入输出模式

单片机输入输出模式输入模式模拟输入、浮空输入、上拉输入、下拉输入GPIO输出模式推挽输出、开漏输出、复用推挽输出、复用开漏输出。上下拉电阻上拉电阻下拉电阻输入模式 模拟输入、浮空输入、上拉输入、下拉输入 模拟输入&#xff1a;I/O端口的模拟信号&#xff08;电压信号…...

数据结构_ 堆结构与堆排序(c++ 实现 + 完整代码 )

堆结构与堆排序 文章目录堆结构与堆排序引入堆堆结构所满足的数学特性准备代码----------- 往堆中插入元素----------- 删除堆顶堆排序构建完整代码及测试动态分配版本非动态版本引入堆 二叉树 具有左孩子与右孩子的最普通的二叉树。 满二叉树 特殊的二叉树&#xff1a;每个节…...

【MySQL】sql中explain解释和应用

这里写目录标题学习原因MySQL中explain的使用和用法解释explain的使用explain 运行结果的意义文字展示表格展示参考资料&#xff1a;结束语学习原因 在对sql的优化过程中使用了explain对指定的sql进行查看它的运行效果&#xff0c;以便找出sql的性能特点并进行优化 MySQL中ex…...

从零实现深度学习框架:Seq2Seq从理论到实战【实战篇】

来源&#xff1a;投稿 作者&#xff1a;175 编辑&#xff1a;学姐 往期内容&#xff1a; 从零实现深度学习框架1&#xff1a;RNN从理论到实战&#xff08;理论篇&#xff09; 从零实现深度学习框架2&#xff1a;RNN从理论到实战&#xff08;实战篇&#xff09; 从零实现深度…...

【数据结构入门】-链表之单链表(1)

个人主页&#xff1a;平行线也会相交 欢迎 点赞&#x1f44d; 收藏✨ 留言✉ 加关注&#x1f493;本文由 平行线也会相交 原创 收录于专栏【数据结构初阶&#xff08;C实现&#xff09;】 文章标题回顾链表链表的概念及结构各种节点打印链表尾插创建节点尾删头插头删查找在pos…...

Docker竟如此简单!

文章目录什么是容器&#xff1f;容器隔离何为“边界”&#xff1f;容器和虚拟机一样吗&#xff1f;基于 Linux Namespace 隔离机制的弊端容器限制何为“限制”&#xff1f;Cgroups 对资源的限制能力缺陷单进程模型容器镜像容器的诞生容器的一致性何为“层&#xff08;layer&…...

在外包干了几年,感觉自己都快费了

先说一下自己的情况。大专生&#xff0c;18年通过校招进入湖南某软件公司&#xff0c;干了接近2年的点点点&#xff0c;今年年上旬&#xff0c;感觉自己不能够在这样下去了&#xff0c;长时间呆在一个舒适的环境会让一个人堕落&#xff01;而我已经在一个企业干了五年的功能测试…...

Java实现多线程有几种方式(满分回答)

目录JDK8 创建的线程的两种方式orcle文档解释方式一&#xff1a;继承Thread类方式二&#xff1a;实现Runnable接口同时用两种的情况其他间接创建方式Callable接口线程池JDK8 创建的线程的两种方式 orcle文档解释 orcle文档&#xff1a;https://docs.oracle.com/javase/8/docs…...