当前位置: 首页 > 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: 删除…...

Qt Widget类解析与代码注释

#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码&#xff0c;写上注释 当然可以&#xff01;这段代码是 Qt …...

理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端

&#x1f31f; 什么是 MCP&#xff1f; 模型控制协议 (MCP) 是一种创新的协议&#xff0c;旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议&#xff0c;它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...

【HTTP三个基础问题】

面试官您好&#xff01;HTTP是超文本传输协议&#xff0c;是互联网上客户端和服务器之间传输超文本数据&#xff08;比如文字、图片、音频、视频等&#xff09;的核心协议&#xff0c;当前互联网应用最广泛的版本是HTTP1.1&#xff0c;它基于经典的C/S模型&#xff0c;也就是客…...

华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建

华为云FlexusDeepSeek征文&#xff5c;DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色&#xff0c;华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型&#xff0c;能助力我们轻松驾驭 DeepSeek-V3/R1&#xff0c;本文中将分享如何…...

GC1808高性能24位立体声音频ADC芯片解析

1. 芯片概述 GC1808是一款24位立体声音频模数转换器&#xff08;ADC&#xff09;&#xff0c;支持8kHz~96kHz采样率&#xff0c;集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器&#xff0c;适用于高保真音频采集场景。 2. 核心特性 高精度&#xff1a;24位分辨率&#xff0c…...

初探Service服务发现机制

1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能&#xff1a;服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源&#xf…...

LLMs 系列实操科普(1)

写在前面&#xff1a; 本期内容我们继续 Andrej Karpathy 的《How I use LLMs》讲座内容&#xff0c;原视频时长 ~130 分钟&#xff0c;以实操演示主流的一些 LLMs 的使用&#xff0c;由于涉及到实操&#xff0c;实际上并不适合以文字整理&#xff0c;但还是决定尽量整理一份笔…...

基于Springboot+Vue的办公管理系统

角色&#xff1a; 管理员、员工 技术&#xff1a; 后端: SpringBoot, Vue2, MySQL, Mybatis-Plus 前端: Vue2, Element-UI, Axios, Echarts, Vue-Router 核心功能&#xff1a; 该办公管理系统是一个综合性的企业内部管理平台&#xff0c;旨在提升企业运营效率和员工管理水…...

comfyui 工作流中 图生视频 如何增加视频的长度到5秒

comfyUI 工作流怎么可以生成更长的视频。除了硬件显存要求之外还有别的方法吗&#xff1f; 在ComfyUI中实现图生视频并延长到5秒&#xff0c;需要结合多个扩展和技巧。以下是完整解决方案&#xff1a; 核心工作流配置&#xff08;24fps下5秒120帧&#xff09; #mermaid-svg-yP…...

前端调试HTTP状态码

1xx&#xff08;信息类状态码&#xff09; 这类状态码表示临时响应&#xff0c;需要客户端继续处理请求。 100 Continue 服务器已收到请求的初始部分&#xff0c;客户端应继续发送剩余部分。 2xx&#xff08;成功类状态码&#xff09; 表示请求已成功被服务器接收、理解并处…...