C++:哈希表——模拟散列表
模拟散列表
维护一个集合,支持如下几种操作:
1.“I x”,插入一个数x
2.“Q x”,询问数x是否在集合中出现过
现在要进行N次操作,对于每个询问操作输出对应的结果
输入格式
第一行包含整数N,表示操作数量
接下来N行,每行包含一个操作指令,操作指令为"I x","Q x"中的一种
输出格式
对于每个询问指令"Q x",输出一个询问结果,如果x在集合中出现过,则输出"Yes",否则输出"No"
每个结果占一行
数据范围
1 ≤ N ≤ 1 0 5 1\le N\le 10^5 1≤N≤105
− 1 0 9 ≤ x ≤ 1 0 9 -10^9\le x\le 10^9 −109≤x≤109
输入样例
5
I 1
I 2
Q 2
Q 5
输出样例
Yes
No
问题分析
哈希表 { 存储结构 { 开放寻址法 拉链法 字符串哈希方式 哈希表\left\{ \begin{aligned} 存储结构 \left\{ \begin{aligned} 开放寻址法\\ 拉链法 \end{aligned} \right. \\ \\ 字符串哈希方式 \end{aligned} \right. 哈希表⎩ ⎨ ⎧存储结构{开放寻址法拉链法字符串哈希方式
AC代码
法一:拉链法
#include<iostream>
#include<cstring>
using namespace std;const int N = 1e5 + 3;int h[N], e[N], ne[N], idx;void insert(int x) {// keep the remainder positive int k = (x % N + N) % N;e[idx] = x;ne[idx] = h[k];h[k] = idx++;
}bool 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;
}int main() {int n;scanf("%d", &n);memset(h, -1, sizeof(h));while(n--) {char op[2];int x;scanf("%s%d", op, &x);if(op[0] == 'I') insert(x);else {if(find(x)) puts("Yes");else puts("No");}}return 0;
}
法二:开放寻址法(推荐)
#include<iostream>
#include<cstring>
using namespace std;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() {int n;scanf("%d", &n);memset(h, 0x3f, sizeof(h));while(n--) {char op[2];int x;scanf("%s%d", op, &x);int k = find(x);if(op[0] == 'I') h[k] = x;else {if(h[k] != null) puts("Yes");else puts("No");}}return 0;
}
相关文章:
C++:哈希表——模拟散列表
模拟散列表 维护一个集合,支持如下几种操作: 1.“I x”,插入一个数x 2.“Q x”,询问数x是否在集合中出现过 现在要进行N次操作,对于每个询问操作输出对应的结果 输入格式 第一行包含整数N,表示操作数量 …...
项目配置中心介绍
目录 什么是配置中心 为什么要有配置中心 配置中心的做法(读取和通知) 配置中心优点: 常用的配置中心中间件 什么是配置中心 配置中心就是用来管理项目当中所有配置的系统,也是微服务系统当中不可或缺的一部分。项目的配置文件不放到本地…...
14-案例:购物车
综合案例-购物车 需求说明: 1. 渲染功能 v-if/v-else v-for :class 2. 删除功能 点击传参 filter过滤覆盖原数组 3. 修改个数 点击传参 find找对象 4. 全选反选 计算属性computed 完整写法 get/set 5. 统计 选中的 总价 和 数量 计算属性conputed reduce条件求和 6. 持久化到本…...
上海市青少年算法2023年2月月赛(丙组)
上海市青少年算法2023年2月月赛(丙组)T1 格式改写 题目描述 给定一个仅由拉丁字符组成字符序列,需要改写一些字符的大小写,使得序列全部变成大写或全部变成小写,请统计最少修改多少个字符才能完成这项任务。 输入格式 一个字符序列:保证仅由拉丁字符构成 输出格式 单个整…...
jetpack5.0.2 已经安装了 cudnn 和 tensorrt
在平台 jetson Xavier NX 中想使用 cudnn 和 tensorrt。然后自己下载了相应包并解压,拷贝,编译 安装 cudnn 1.下载对应包文件,例如:cudnn-linux-sbsa-8.4.1.50_cuda11.6-archive.tar.xz 2.解压,移动到解压目录&#…...
我的编程语言学习笔记
前言 作为一名编程初学者,我深知学习编程需要不断积累和记录。在这篇博客文章中,我将分享一些我在学习C/C编程语言过程中记录的常用代码、特定函数、复杂概念以及特定功能。希望能与大家一起切磋进步! 常用代码: 1. 输入输出操作…...
一个DW的计算
一个DW的计算 1- 题目: 已知一个DW1.1 要求: 从DW中取出指定的位的值1.1.1 分析1.1.2 实现1.1.3 简化实现1.1.4 验证 2- 题目: 已知一个DW2.1 要求: 从DW中的指定的P和S,取出指定的位的值2.1.1 分析2.1.2 实现 1- 题目: 已知一个DW 有图中所示一行信息,表示一个DW(…...
java.net.BindException Address already in use: NET_Bind解决
java.net.BindException Address already in use: NET_Bind 两种解决方法 两种解决方法 (1) kill 占用此端口的线程 查看报错的端口 netstat -ano | findstr 16825tasklist | findstr 1092 如果占用的程序不重要直接kill taskkill /f /pid 16825 (2) 修改启动端口 找一个没…...
JMM内存模型之happens-before阐述
文章目录 一、happens-before的定义二、happens-before的规则1. 程序顺序规则:2. 监视器锁规则:3. volatile变量规则:4. 传递性:5. start()规则:6. join()规则: 一、happens-before的定义 如果一个操作hap…...
大数据课程I2——Kafka的架构
文章作者邮箱:yugongshiye@sina.cn 地址:广东惠州 ▲ 本章节目的 ⚪ 掌握Kafka的架构; ⚪ 掌握Kafka的Topic与Partition; 一、Kafka核心概念及操作 1. producer生产者,可以是一个测试线程,也可以是某种技术框架(比如flume)。 2. producer向kafka生…...
vscode如何汉化
首先我们到vscode官网下载 链接如下: Visual Studio Code - Code Editing. Redefined 根据自己需要的版本下载就好 下载并且安装完毕之后 运行vscode 然后按快捷键 CTRLSHIFTX 打开安装扩展界面 搜索简体中文 安装就可以了 谢谢大家观看...
matlab保存图片
仅作为记录,大佬请跳过。 文章目录 用界面中的“另存为”用saveas 用界面中的“另存为” 即可。 参考 感谢大佬博主文章:传送门 用saveas 必须在编辑器中的plot之后用saveas(也就是不能在命令行中单独使用——比如在编辑器中plot…...
产业园区数字孪生3d可视化全景展示方案
随着数字经济的发展,数字技术给企业发展带来了机遇的同时,也为企业管理带来挑战。比如园区运维,不仅体量大,复杂的运维管理系统,落地难度也较高。那么如何通过数字化手段重塑园区运营,打通园区各业务数据孤…...
centos7 jupyter notebook 安装自动补全插件
激活juoyter notebook的安装环境 conda activate prod执行以下命令安装 pip install jupyter_contrib_nbextensions -i https://pypi.tuna.tsinghua.edu.cn/simple jupyter contrib nbextension install --userpip install jupyter_nbextensions_configurator -i https://py…...
【算法——双指针】LeetCode 202 快乐数
题目描述: 思路:快慢指针 看到循环,我就想起了快慢指针的方法,从题目我们可以看出,我们需要模拟一个过程:不断用当前的数去生成下一个数,生成的规则就是将当前数的各位的平方累加; …...
AndroidManifest清单文件中,Activity的screenOrientation属性详解
screenOrientation用于控制Acivity的屏幕方向,参数有16个。 参数值功能自动旋转打开自动旋转关闭unspecified-1让系统决定Activity的方向,由传感器和系统设置共同决定四个方向不旋转landscape0强制为横屏,忽略传感器和系统设置不旋转不旋转portrait1强制为竖屏,忽略传感器和系统…...
Qt+Pyhton实现麒麟V10系统下word文档读写功能
目录 前言1.C调用python1.1 安装Python开发环境1.2 修改Qt工程配置1.3 初始化Python环境1.4 C 调用Python 函数1.5 常用的Python接口 2.python虚拟环境2.1Python虚拟环境简介2.2 virtualenv 安装及使用2.3 在C程序中配置virtualenv 虚拟环境 3.python-docx库的应用4.总结 前言 …...
TCP/IP 下的计算机网络江湖
〇、引言 在当今数字化时代,计算机网络宛如广袤江湖,涵盖着五大门派:物理层、数据链路层、网络层、传输层和应用层。每个门派独具技能,共同构筑着现代网络的框架。物理层宛如江湖基石,将比特流传输;数据链路层如武林传承,组织数据帧传递;网络层则像导航大师,寻找传送路…...
智能家居(4)---火灾报警线程封装
封装火灾报警线程实现智能家居中的火灾报警功能 mainPro.c(主函数) #include <stdio.h> #include "controlDevice.h" #include "inputCommand.h"#include <pthread.h>struct Devices *pdeviceHead NULL; …...
C#语音播报问题之 无法嵌入互操作类型SpVoiceClass,请改用适用的窗口
C#语音播报问题之 无法嵌入互操作类型SpVoiceClass,请改用适用的窗口 解决办法如下: 只需要将引入的Interop.SpeechLib的属性嵌入互操作类型改为false 改为false 即可解决!...
XML Group端口详解
在XML数据映射过程中,经常需要对数据进行分组聚合操作。例如,当处理包含多个物料明细的XML文件时,可能需要将相同物料号的明细归为一组,或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码,增加了开…...
Golang dig框架与GraphQL的完美结合
将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用,可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器,能够帮助开发者更好地管理复杂的依赖关系,而 GraphQL 则是一种用于 API 的查询语言,能够提…...
WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)
一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解,适合用作学习或写简历项目背景说明。 🧠 一、概念简介:Solidity 合约开发 Solidity 是一种专门为 以太坊(Ethereum)平台编写智能合约的高级编…...
【C语言练习】080. 使用C语言实现简单的数据库操作
080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...
【JavaSE】绘图与事件入门学习笔记
-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角,以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向,距离坐标原点x个像素;第二个是y坐标,表示当前位置为垂直方向,距离坐标原点y个像素。 坐标体系-像素 …...
智能仓储的未来:自动化、AI与数据分析如何重塑物流中心
当仓库学会“思考”,物流的终极形态正在诞生 想象这样的场景: 凌晨3点,某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径;AI视觉系统在0.1秒内扫描包裹信息;数字孪生平台正模拟次日峰值流量压力…...
今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存
文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...
Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析
Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问(基础概念问题) 1. 请解释Spring框架的核心容器是什么?它在Spring中起到什么作用? Spring框架的核心容器是IoC容器&#…...
嵌入式学习笔记DAY33(网络编程——TCP)
一、网络架构 C/S (client/server 客户端/服务器):由客户端和服务器端两个部分组成。客户端通常是用户使用的应用程序,负责提供用户界面和交互逻辑 ,接收用户输入,向服务器发送请求,并展示服务…...
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要: 近期,在使用较新版本的OpenSSH客户端连接老旧SSH服务器时,会遇到 "no matching key exchange method found", "n…...
