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

C++ 模拟散列表 || 哈希表存储与查询,模版题(拉链法)

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

I x,插入一个整数 x

Q x,询问整数 x
是否在集合中出现过;
现在要进行 N
次操作,对于每个询问操作输出对应的结果。

输入格式
第一行包含整数 N
,表示操作数量。

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

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

每个结果占一行。

数据范围
1≤N≤105

−109≤x≤109
输入样例:
5
I 1
I 2
I 3
Q 2
Q 5

#include <iostream>
#include <cstring>using namespace std;const int N = 100003;int n;
int h[N], e[N], ne[N], idx; 
//h是哈希表(头结点数组)、e是元素数组、ne是链表中下一个元素的索引
/*h 数组是哈希表的数组,每个元素表示一个桶。
h[k] 存储的是第 k 个桶的头结点,即链表中第一个元素的索引。(存的拉链的头结点的下标)
e 数组存储具体的元素值,每个元素值对应一个索引。
ne 数组存储链表中每个元素的下一个元素的索引。
idx 是当前要插入的元素的索引。*/void insert(int x)
{// 计算哈希值,使用取模运算防止越界int k = (x % N + N) % N; // x % N x是负数的话保证这个哈希函数映射一定是正数// 插入到哈希表中,使用链地址法处理哈希冲突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()
{scanf("%d", &n);memset(h, -1, sizeof h);// 初始化哈希表的头结点为 -1,表示空链表while(n -- ){char op[2];int x;scanf("%s%d", op, &x);if(op[0] == 'I'){insert(x);}else{if(find(x)) printf("Yes\n");else printf("No\n");}}return 0;
}

相关文章:

C++ 模拟散列表 || 哈希表存储与查询,模版题(拉链法)

维护一个集合&#xff0c;支持如下几种操作&#xff1a; I x&#xff0c;插入一个整数 x &#xff1b; Q x&#xff0c;询问整数 x 是否在集合中出现过&#xff1b; 现在要进行 N 次操作&#xff0c;对于每个询问操作输出对应的结果。 输入格式 第一行包含整数 N &#xff0c…...

详解Skywalking 服务Overview页面的参数含义(适合小白)

本文针对刚刚接触skywalking的同学&#xff0c;重点讲解服务Overview页面中各个参数的含义&#xff0c;为大家快速上手skywalking会起到帮助作用&#xff01; 最重要的三个指标 Service Apdex&#xff08;数字&#xff09;:当前服务的评分 Successful Rate&#xff08;数字&a…...

Android studio GridView应用设计

一、xml布局文件设计: <GridViewandroid:id="@+id/gridView"android:layout_width="match_parent"android:layout_height="match_parent"tools:layout_editor_absoluteX="1dp"tools:layout_editor_absoluteY="1dp"andr…...

K8s 是如何完成调度和权重调整?

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、调度流程二、kuble-scheduler 调度原理1 kubernetes 1.23版本调度器filter阶段和score阶段源码分析2 修改调度器插件默认权重示例2.1 环境准备2.2 调整Inte…...

计算机毕业设计----Springboot超市订单管理系统

项目介绍 该超市订单管理毕业设计基于jdk8版本开发&#xff0c;在部署时需要使用jdk8以上的版本。使用了目前流行的框架组合springbootmybatis的框架技术&#xff0c; 实现了供应商管理对供应商实现增删改查、订单管理对超市订单实现增删改查、用户管理等功能&#xff0c;适用…...

如何给AI下达精准的指令,哪些提示词对于AI是有效的?

刚上手那会&#xff0c;我倾向于将 prompt 翻译为“指令”&#xff0c;但这并不精确。“指令”通常对应instructions&#xff0c;属于 prompt 中的纯指令部分&#xff0c;通常是一个动宾结构&#xff08;做什么&#xff09;。剩下的部分更多是描述&#xff08;describe&#xf…...

软件外包资源网站分享

经济不景气导致很多人失业&#xff0c;能否找到一份工作或找些项目做做&#xff0c;这里列了一些国内和国外的资源网上&#xff0c;希望对大家有益&#xff1a; 国内篇&#xff1a; 软件项目交易网&#xff1a;(软件项目交易网)这是一个专注于软件开发需求的外包平台&#xf…...

在控制理论里,单个输入变量被施加了饱和特性处理,那么后续怎么利用李雅普诺夫判据判断系统稳定性呢?

在控制理论中&#xff0c;当一个系统的输入变量被施加了饱和特性&#xff08;即输入被限制在某个范围内&#xff09;&#xff0c;系统的稳定性分析可能变得更复杂。使用李雅普诺夫方法判断这样的系统稳定性通常需要考虑非线性特性。下面是如何使用李雅普诺夫方法进行稳定性分析…...

MySQL夯实之路-查询性能优化深入浅出

MySQL调优分析 explain&#xff1b;show status查看服务器状态信息 优化 减少子任务&#xff0c;减少子任务执行次数&#xff0c;减少子任务执行时间&#xff08;优&#xff0c;少&#xff0c;快&#xff09; 查询优化分析方法 1&#xff0e;访问了太多的行和列&#xff1…...

UniApp面试题

面试题1 问&#xff1a;什么是 UniApp&#xff1f;它有哪些特点&#xff1f; 答&#xff1a;UniApp 是一种基于 Vue.js 开发跨平台应用的框架。它可以同时构建运行在多个平台&#xff08;包括但不限于小程序、H5、App&#xff09;的应用程序。UniApp 的特点包括&#xff1a;一…...

30 树的定义

树的定义 树的度&#xff1f;叶节点&#xff1f; 注意&#xff1a;k为叶节点 孩子/双亲/子孙/祖先 树的高度&#xff1f; 有序树 森林 树的一些操作&#xff1a; 粗略的框架代码&#xff1a; 省略。。。 小结&#xff1a; 树是线性表的扩展...

程序员必备的面试技巧

程序员必备的面试技巧 “程序员必备的面试技巧&#xff0c;就像是编写一段完美的代码一样重要。在面试战场上&#xff0c;我们需要像忍者一样灵活&#xff0c;像侦探一样聪明&#xff0c;还要像无敌铁金刚一样坚定。只有掌握了这些技巧&#xff0c;我们才能在面试的舞台上闪耀…...

【NI-DAQmx入门】LabVIEW中DAQmx同步

1.同步解释 1.1 同步基础概念 触发器&#xff1a;触发器是控制采集的命令。您可以使用触发器来启动、停止或暂停采集。触发信号可以源自软件或硬件源。 时钟&#xff1a;时钟是用于对数据采集计时的周期性数字信号。根据具体情况&#xff0c;您可以使用时钟信号直接控制数据采…...

FlinkRestAPI

which flink 找到Flink客户端地址 如果输出结果为空&#xff0c;则说明 Flink 客户端没有安装在系统路径中。在这种情况下&#xff0c;您可以通过设置 FLINK_HOME 环境变量来指定 Flink 客户端的路径。例如&#xff1a; export FLINK_HOME/opt/flink 然后&#xff0c;您可以使…...

Qt获取当前系统网络接口信息

1.QInterface获取网络接口信息 void NetProperty::init() {// 获取所有网络接口const QList<QNetworkInterface> interfaces QNetworkInterface::allInterfaces();ui->com_Interface->clear();for(const QNetworkInterface& interface : interfaces){ui->…...

【C++】STL 算法 ④ ( 函数对象与谓词 | 一元函数对象 | “ 谓词 “ 概念 | 一元谓词 | find_if 查找算法 | 一元谓词示例 )

文章目录 一、函数对象与谓词1、一元函数对象2、" 谓词 " 概念3、find_if 查找算法 二、一元谓词示例1、代码示例 - 一元谓词示例2、执行结果 一、函数对象与谓词 1、一元函数对象 " 函数对象 " 是通过 重载 函数调用操作符 () 实现的 operator() , 函数对…...

C++ 并发编程 | 并发世界

一、C 并发世界 1、什么是并发&#xff1f; 并发是指两个或更多独立的活动同时发生&#xff0c;计算机中的并发指的是&#xff0c;在单个系统里同时执行多个独立的活动...

GitHub注册新账号的操作流程(详细)

目录 第一步 进入官网&#xff0c;点击右上角的"Sign up" 第二步 输入email地址 第三步 设置密码 第四步 输入昵称 第五步 根据个人喜好决定要不要接收GitHub的邮件推送。然后回答他们的验证问题 第六步 输入验证码 我在注册github账号时遇到过一些阻碍&#x…...

Kali安装Xrdp结合内网穿透实现无公网ip远程访问系统桌面

文章目录 前言1. Kali 安装Xrdp2. 本地远程Kali桌面3. Kali 安装Cpolar 内网穿透4. 配置公网远程地址5. 公网远程Kali桌面连接6. 固定连接公网地址7. 固定地址连接测试 前言 Kali远程桌面的好处在于&#xff0c;它允许用户从远程位置访问Kali系统&#xff0c;而无需直接物理访…...

【WEB API自动化测试】接口文档与在线测试

这一篇我们主要介绍如何做API帮助文档&#xff0c;给API的调用人员介绍各个 API的功能, 输入参数&#xff0c;输出参数, 以及在线测试 API功能(这个也是方便我们自己开发调试) 我们先来看看我们的API最终帮助文档及在线测试最终达到的效果: 概要图 GET API 添加产品API: 删除…...

【大模型RAG】Docker 一键部署 Milvus 完整攻略

本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装&#xff1b;只需暴露 19530&#xff08;gRPC&#xff09;与 9091&#xff08;HTTP/WebUI&#xff09;两个端口&#xff0c;即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...

SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现

摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序&#xff0c;以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务&#xff0c;提供稳定高效的数据处理与业务逻辑支持&#xff1b;利用 uniapp 实现跨平台前…...

全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比

目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec&#xff1f; IPsec VPN 5.1 IPsec传输模式&#xff08;Transport Mode&#xff09; 5.2 IPsec隧道模式&#xff08;Tunne…...

uniapp 字符包含的相关方法

在uniapp中&#xff0c;如果你想检查一个字符串是否包含另一个子字符串&#xff0c;你可以使用JavaScript中的includes()方法或者indexOf()方法。这两种方法都可以达到目的&#xff0c;但它们在处理方式和返回值上有所不同。 使用includes()方法 includes()方法用于判断一个字…...

深入理解Optional:处理空指针异常

1. 使用Optional处理可能为空的集合 在Java开发中&#xff0c;集合判空是一个常见但容易出错的场景。传统方式虽然可行&#xff0c;但存在一些潜在问题&#xff1a; // 传统判空方式 if (!CollectionUtils.isEmpty(userInfoList)) {for (UserInfo userInfo : userInfoList) {…...

【前端异常】JavaScript错误处理:分析 Uncaught (in promise) error

在前端开发中&#xff0c;JavaScript 异常是不可避免的。随着现代前端应用越来越多地使用异步操作&#xff08;如 Promise、async/await 等&#xff09;&#xff0c;开发者常常会遇到 Uncaught (in promise) error 错误。这个错误是由于未正确处理 Promise 的拒绝&#xff08;r…...

嵌入式常见 CPU 架构

架构类型架构厂商芯片厂商典型芯片特点与应用场景PICRISC (8/16 位)MicrochipMicrochipPIC16F877A、PIC18F4550简化指令集&#xff0c;单周期执行&#xff1b;低功耗、CIP 独立外设&#xff1b;用于家电、小电机控制、安防面板等嵌入式场景8051CISC (8 位)Intel&#xff08;原始…...

协议转换利器,profinet转ethercat网关的两大派系,各有千秋

随着工业以太网的发展&#xff0c;其高效、便捷、协议开放、易于冗余等诸多优点&#xff0c;被越来越多的工业现场所采用。西门子SIMATIC S7-1200/1500系列PLC集成有Profinet接口&#xff0c;具有实时性、开放性&#xff0c;使用TCP/IP和IT标准&#xff0c;符合基于工业以太网的…...

FFmpeg avformat_open_input函数分析

函数内部的总体流程如下&#xff1a; avformat_open_input 精简后的代码如下&#xff1a; int avformat_open_input(AVFormatContext **ps, const char *filename,ff_const59 AVInputFormat *fmt, AVDictionary **options) {AVFormatContext *s *ps;int i, ret 0;AVDictio…...

解析两阶段提交与三阶段提交的核心差异及MySQL实现方案

引言 在分布式系统的事务处理中&#xff0c;如何保障跨节点数据操作的一致性始终是核心挑战。经典的两阶段提交协议&#xff08;2PC&#xff09;通过准备阶段与提交阶段的协调机制&#xff0c;以同步决策模式确保事务原子性。其改进版本三阶段提交协议&#xff08;3PC&#xf…...