【蓝桥杯集训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进制数字(哈希值),实现不同的字符串映射到不同的数字
对形如
的字符串,采用字符的ascii 码乘上 P 的次方来计算哈希值
映射公式
注意:
- 任意字符不可以映射成0,否则会出现不同的字符串都映射成0的情况,比如A,AA,AAA皆为0
- 通过巧妙设置P (131 或 13331) , Q (
)的值,一般可以理解为不产生冲突
比较不同区间的子串是否相同,就转化为对应的哈希值是否相同
求一个字符串的哈希值就相当于求前缀和,求一个字符串的子串哈希值就相当于求部分和
字符串前缀和公式:
h[i] = h[i-1]*P + s[i];区间和公式:
区间和公式的理解: ABCDE 与 ABC 的前三个字符值是一样,只差两位,
乘上把 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. 笨拙的手指 - 哈希表 秦九韶算法(进制转换) 枚举 秦九韶算法——将x进制数转化为十进制数 手写哈希表 活动 - AcWing 1、开放寻址法 设 h(x)k,也就是 x 的哈希值…...
Java Scanner 类,超详细整理,适合新手入门
目录 一、什么是 Java Scanner 类? 二、引用数据类型 1、引用数据类型的定义 三、Scanner 类有哪些常用方法? hasNext()用法 四、next() 与 nextLine() 区别 next(): nextLine(): 五、使用 next 方法 五、使用 nextLine方法 一、什…...
干货 | 中小企业选型 Elasticsearch 避坑指南
1、线上常见问题在我线下对接企业或线上交流的时候,经常会遇到各种业务场景不同的问题。比如,常见问题归类如下:常见问题1:ES 适合场景及架构选型问题。公司的核心业务是做企业员工健康管理,数据来自电子化后的员工体检…...
全局组件和局部组件
全局组件第一种定义方法:A、创建自己的组件: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…...
提取括号中的内容
正则能解决不嵌套的括号内容提取问题遇到一个问题,就是需要提取字符串中每一个中括号里的内容,在网上搜了一下,发现用正则表达式(\[[^\]]*\])可以提取中括号中的内容,以下面文本为匹配对象:PerformanceManager[第1个中…...
数据结构-算法的空间复杂度(1.2)
目录 1.空间复杂度 1.1 例子 1.2 空间的特殊性质 写在最后: 1.空间复杂度 空间复杂度也是一个数学表达式, 是对一个算法在运行过程中临时占用存储空间大小的量度。 他也是用大O渐进表示法。 1.1 例子 例1: 冒泡排序: v…...
【总结】python3启动web服务引发的一系列问题
背景 在某行的实施项目,需要使用python3环境运行某些py脚本。 由于行内交付的机器已自带python3 ,没有采取自行安装python3,但是运行python脚本时报没有tornado module。 错误信息 ModuleNotFoundError:No module named ‘torn…...
Linux:基于libevent读写管道代码,改进一下上一篇变成可以接收键盘输入
对上一篇进行改进,变成可以接收键盘输入,然后写入管道: 读端代码: #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函数
凡事发生必将有益于我,高手,从来都不仅仅是具备某种思维的人,而是那些具备良好学习习惯的人,成为高手,无他,手熟尔!加油在最近的学习之中,对于格式化输出这个知识点,这里…...
Nginx之反向代理、负载均衡、动静分离。
Nginx之反向代理、负载均衡、动静分离。 1、Nginx是啥? 轻量级Web服务器、反向代理服务器、电子邮件(IMAP/POP3)代理服务器 在 BSD-like 协议下发行、占内存少、并发高(同时处理请求能力)。 2、安装 官网…...
0401不定积分的概念和性质-不定积分
文章目录1 原函数与不定积分的概念1.1 原函数1.2 原函数存在定理1.3 不定积分2 不定积分的性质3 基本积分表4 例题后记1 原函数与不定积分的概念 1.1 原函数 定义1 如果在区间I上,可导函数F(x)的导航为f(x),即对任一x∈Ix\in Ix∈I,都有 F′…...
数组中的各种迭代API方法手写
js的数组上有很多实用的方法,不论是在遍历数组上,还是在操作数组内元素上,它有许多不同的遍历数组的方法,同时它还有着可以直接操作数组中间元素的方法。 接下来,我来带大家手写数组里的 遍历方法 。 Array.forEach(…...
详解量子计算:相位反冲与相位反转
前言 本文需要对量子计算有一定的了解。需要的请翻阅我的量子专栏,这里不再涉及基础知识的科普。 量子相位反冲是什么? 相位反转(phase kickback)是量子计算中的一种现象,通常在量子算法中使用,例如量子…...
C++——C++11第三篇
目录 包装器 function包装器 bind 包装器 function包装器 function包装器 也叫作适配器。C中的function本质是一个类模板,也是一个包装器。 上面的程序验证,我们会发现useF函数模板实例化了三份。 包装器可以很好的解决上面的问题 ,让它只实…...
180 2 22222
选择题(共180题,合计180.0分) 1. 在项目开工会议期间,项目发起人告诉产品负责人和团队项目章程即将完成。然而,由于存在在紧迫的期限内满足政府监管要求的压力,发起人希望立即开始工作。产品负责人下一步应该做什么? A 告诉发起人…...
成人高考初中毕业能报名吗 需要什么条件
初中学历的人员不能直接报名成人高考,考生需要有普通高中,职业高中,中专毕业证等高中同等学力就可以进行报名,在报名期间登陆所在省的教育考试院的成人高考报名入口进行报考。成人高考报名条件是什么1、遵守宪法和法律。2、国家承…...
ChatGPT初体验
ChatGPT初体验 前言 嘿嘿,最近啊AI ChatGPT刷新各大网站,对于我们国人而将很不友好,真的太不友好了。我呢在去年open AI发布的时候就有所关注,那个时候还没有像现在这样火热。谁知道短短几个月便传遍大街小巷。 一、什么是chatG…...
ChatGPT概念狂飙!究竟魅力何在?
原文:http://www.btcwbo.com/6988.html 近期,ChatGPT引领的人工智能概念在资本市场一路狂飙,AIGC题材持续发酵。截至2月7日,Wind ChatGPT指数今年以来累计上涨超50%,汉王科技、海天瑞声、云从科技等概念股股价已经翻倍…...
如何下载阅读Spring源码-全过程详解
这篇文章记录了下载spring源码和在IDEA中打开运行的全过程,并且记录了过程中遇到的问题和解决方案,适合需要学习spring源码的同学阅读。 1.spring源码下载地址 通过Git下载spring-framework项目源码: git clone https://github.com/spring…...
学了两个月的Java,最后自己什么也不会,该怎么办?
学着学着你会发现每天的知识都在更新,也都在遗忘,可能就放弃了。但是只要自己肯练,肯敲代码,学过的知识是很容易就被捡起来的。等你学透了用不了一年也可以学好 Java的运行原理:Java是一门编译解释型语言,…...
GD32串口DMA实战:如何优化数据传输效率与内存占用
GD32串口DMA实战:如何优化数据传输效率与内存占用 在嵌入式开发中,串口通信是最基础也最常用的外设之一。当面对高速数据流或实时性要求较高的场景时,传统的轮询或中断方式往往难以满足需求。这时,DMA(直接内存访问&am…...
OpenClaw多任务测试:百川2-13B-4bits模型在并行处理中的显存管理
OpenClaw多任务测试:百川2-13B-4bits模型在并行处理中的显存管理 1. 测试背景与动机 上周在调试一个自动化工作流时,遇到了一个典型问题:当OpenClaw同时处理文件格式转换、网页信息抓取和邮件发送任务时,后台的百川2-13B模型频繁…...
Qwen3-4B快速上手:无需深度学习基础,轻松玩转AI对话
Qwen3-4B快速上手:无需深度学习基础,轻松玩转AI对话 想体验一个反应迅速、对话流畅的AI助手吗?阿里通义千问的Qwen3-4B模型或许就是你需要的。这个专门优化过的版本去掉了所有视觉处理功能,专注于文本对话,响应速度大…...
革新华硕笔记本性能控制:轻量级开源工具GHelper全面解析
革新华硕笔记本性能控制:轻量级开源工具GHelper全面解析 【免费下载链接】g-helper Lightweight Armoury Crate alternative for Asus laptops. Control tool for ROG Zephyrus G14, G15, G16, M16, Flow X13, Flow X16, TUF, Strix, Scar and other models 项目地…...
智能资金概念在算法交易中的深度解析:从理论到实战应用
智能资金概念在算法交易中的深度解析:从理论到实战应用 【免费下载链接】smartmoneyconcepts This is a python package for smart money concept indicators 项目地址: https://gitcode.com/gh_mirrors/smar/smartmoneyconcepts 在当今算法交易领域…...
springboot-vue+nodejs 的酒店客房预定管理系统的设计与实现
目录技术栈选择系统模块划分后端实现前端实现中间层实现数据库设计支付集成测试与部署项目技术支持源码获取详细视频演示 :文章底部获取博主联系方式!同行可合作技术栈选择 Spring Boot 作为后端框架,提供 RESTful API 接口;Vue.…...
OpenClaw极简开发:用nanobot镜像快速验证自动化脚本
OpenClaw极简开发:用nanobot镜像快速验证自动化脚本 1. 为什么选择nanobot镜像进行OpenClaw开发 作为一名长期在本地折腾AI自动化脚本的开发者,我深知环境配置的痛。每次换机器重装OpenClaw,总要在Node.js版本、Python依赖和模型部署之间反…...
AI和苹果夹逼,国产手机顶不住了,网传大规模人才优化已在进行中
某已没落的手机企业在转卖后,近期又传出重大消息,只是这次是相当悲惨的消息,手机硬件研发被砍掉,半数员工就地解散,揭开了手机行业人才优化的序幕,其实手机行业的这种操作早在去年底就已悄然进行࿰…...
想转行做产品经理?看看你身上有没有这5个“隐藏技能”
在数字经济飞速发展的当下,产品经理早已不是互联网行业的“专属岗位”,而是横跨互联网、硬件、金融、制造业等多个领域的核心角色——连接用户需求与技术实现,主导产品从创意到落地的全流程,被称为“CEO的学前班”。正因如此&…...
Web开发环境快速搭建:Miniconda-Python3.11镜像实战应用
Web开发环境快速搭建:Miniconda-Python3.11镜像实战应用 1. 为什么选择Miniconda-Python3.11 Python作为Web开发的主流语言之一,环境配置一直是新手面临的第一个挑战。Miniconda-Python3.11镜像提供了一种开箱即用的解决方案,相比传统安装方…...

