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

数据结构哈希表

这里个大家用数组来模拟哈希表

法一:拉链法

法二:开放寻址法

/** Project: 11_哈希表* File Created:Sunday, January 17th 2021, 2:11:23 pm* Author: Bug-Free* Problem:AcWing 840. 模拟散列表 拉链法*/
#include <cstring>
#include <iostream>using namespace std;const int N = 1e5 + 3;  // 取大于1e5的第一个质数,取质数冲突的概率最小 可以百度//* 开一个槽 h
int h[N], e[N], ne[N], idx;  //邻接表void insert(int x) {// c++中如果是负数 那他取模也是负的 所以 加N 再 %N 就一定是一个正数int k = (x % N + N) % N;e[idx] = x;ne[idx] = h[k];h[k] = idx++;
}bool find(int x) {//用上面同样的 Hash函数 讲x映射到 从 0-1e5 之间的数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 n;int main() {cin >> n;memset(h, -1, sizeof h);  //将槽先清空 空指针一般用 -1 来表示while (n--) {string op;int x;cin >> op >> x;if (op == "I") {insert(x);} else {if (find(x)) {puts("Yes");} else {puts("No");}}}return 0;
}

/** Project: 11_哈希表* File Created:Sunday, January 17th 2021, 4:39:01 pm* Author: Bug-Free* Problem:AcWing 840. 模拟散列表  开放寻址法*/
#include <cstring>
#include <iostream>using namespace std;//开放寻址法一般开 数据范围的 2~3倍, 这样大概率就没有冲突了
const int N = 2e5 + 3;        //大于数据范围的第一个质数
const int null = 0x3f3f3f3f;  //规定空指针为 null 0x3f3f3f3fint h[N];int find(int x) {int t = (x % N + N) % N;while (h[t] != null && h[t] != x) {t++;if (t == N) {t = 0;}}return t;  //如果这个位置是空的, 则返回的是他应该存储的位置
}int n;int main() {cin >> n;memset(h, 0x3f, sizeof h);  //规定空指针为 0x3f3f3f3fwhile (n--) {string op;int x;cin >> op >> x;if (op == "I") {h[find(x)] = x;} else {if (h[find(x)] == null) {puts("No");} else {puts("Yes");}}}return 0;
}

相关文章:

数据结构哈希表

这里个大家用数组来模拟哈希表 法一&#xff1a;拉链法 法二&#xff1a;开放寻址法 /** Project: 11_哈希表* File Created:Sunday, January 17th 2021, 2:11:23 pm* Author: Bug-Free* Problem:AcWing 840. 模拟散列表 拉链法*/ #include <cstring> #include <iostr…...

[C#]winform使用引导APSF和梯度自适应卷积增强夜间雾图像的可见性算法实现夜间雾霾图像的可见度增强

【算法介绍】 提升夜间雾霾图像可见度的技术研究&#xff1a;引导APSF与梯度自适应卷积的应用 随着城市化的快速发展&#xff0c;雾霾现象日益严重&#xff0c;尤其是在夜间&#xff0c;雾霾对图像的可见度造成了极大的影响。因此&#xff0c;提升夜间雾霾图像的可见度成为了…...

【Django】Django自定义后台表单——对一个关联外键对象同时添加多个内容

以官方文档为例&#xff1a; 一个投票问题包含多个选项&#xff0c;基本的表单设计只能一个选项一个选项添加&#xff0c;效率较低&#xff0c;如何在表单设计中一次性添加多个关联选项&#xff1f; 示例代码&#xff1a; from django.contrib import adminfrom .models impo…...

迷茫?没有努力的方向?没有耐心去坚持?精选书籍推荐2

迷茫书籍推荐 在渡过自卑期后&#xff0c;下一阶段就是迷茫期&#xff0c;我就是典型。坚持考研失败&#xff0c;然后工作上不顺利&#xff0c;尽管稍稍改变了自卑&#xff0c;但是却因为从前的失败&#xff0c;对下一步何去何从产生了迷茫。这也是我这篇文章希望帮助大家解决的…...

MySQL报错:sql_mode=only_full_group_by解决方法

Linux环境 ubuntu 22.04 MySQL是8.0.35版本 问题描述 Expression #1 of SELECT list is not in GROUP BY clause and contains nonaggregated column auth_system.t_class_temp_config.id which is not functionally dependent on columns in GROUP BY clause; this is inco…...

SQL表连接方式

一、SQL中的表连接方式&#xff1a; 内连接&#xff08;INNER JOIN&#xff09;&#xff1a;返回两个表中符合连接条件的交集。外连接&#xff08;OUTER JOIN&#xff09;&#xff1a; 左外连接&#xff08;LEFT JOIN&#xff09;&#xff1a;返回左表中所有记录&#xff0c;以…...

5 原型模式 Prototype

1.模式定义: 指原型实例指定创建对象的种类&#xff0c;并且通过拷贝这些原型创建新的对象 2.应用场景&#xff1a; 当代码不应该依赖于需要复制的对象的具体类时&#xff0c;请使用Prototype模式。 Spring源码中的应用 org.springframework.beans.factory.support.AbstractB…...

springboot java 项目连接es

springboot java 项目连接es 介绍 小项目&#xff0c;没有引用es客户端&#xff0c;直接使用的http的方式进行连接的&#xff0c;方式比较简单&#xff0c;但是依赖较少&#xff0c;一个比较小的项目&#xff0c;部署方便 业务也很简单就是把数据库中的数据读到es中&#xf…...

MySQL学习笔记3: MySQL数据库基础

目录 前言目标数据库操作&#xff08;针对database 的操作&#xff09;1. 创建数据库 create database 数据库名;2. 查看数据库 show databases;3. 选中数据库 use 数据库名;4. 删除数据库 drop database 数据库名; mysql中支持的数据类型1. 数值类型: NUMERIC(M,D)2. 字符串类…...

GB/T 17640-2023 长丝机织土工布检测

长丝机织土工布是指以合成纤维长丝为原料织制而成的土工布&#xff0c;按纤维品种分为涤纶、丙纶、锦纶 等长丝机织土工布&#xff1b;按用途分为反滤布、复合用基布、管袋布、模袋布等。 GB/T 17640-2023 长丝机织土工布测试项目&#xff1a; 测试要求 测试标准 经向抗拉强…...

MedicalGPT 训练医疗大模型,实现了包括增量预训练、有监督微调、RLHF(奖励建模、强化学习训练)和DPO(直接偏好优化)

MedicalGPT 训练医疗大模型&#xff0c;实现了包括增量预训练、有监督微调、RLHF(奖励建模、强化学习训练)和DPO(直接偏好优化)。 MedicalGPT: Training Your Own Medical GPT Model with ChatGPT Training Pipeline. 训练医疗大模型&#xff0c;实现了包括增量预训练、有监督微…...

UE4 C++联网RPC教程笔记(一)(第1~4集)

UE4 C联网RPC教程笔记&#xff08;一&#xff09;&#xff08;第1~4集&#xff09; 前言1. 教程介绍与资源2. 自定义 Debug 功能3. Actor 的复制4. 联网状态判断 前言 本系列笔记将会对梁迪老师的《UE4C联网RPC框架开发吃鸡》教程进行个人的知识点梳理与总结&#xff0c;此课程…...

备战蓝桥杯 Day11(滚动数组优化+完全背包)

01背包的滚动数组优化 【题目描述】 经典0—1背包问题,有n个物品&#xff0c;编号为i的物品的重量为w[i]&#xff0c;价值为c[i]&#xff0c;现在要从这些物品中选一些物品装到一个容量为m的背包中&#xff0c;使得背包内物体在总重量不超过m的前提下价值尽量大。 #include&…...

Java SE 入门到精通—4.抽象类与接口【Java】

抽象类 同接口一样&#xff0c;用来约束子类&#xff0c;限制子类必须拥有某些方法&#xff0c;比普通类多了个抽象方法&#xff0c;用抽象方法该类必为抽象类 概念 没有具体的对象&#xff0c;具体的方法的一个类 abstract关键字声明为抽象类/方法 一个类中有抽象方法则该…...

Python 开发转 Java 简易路线 - 更新中

有了 Python 开发基础&#xff0c;Java 的内容都可以快速过一遍&#xff0c;复杂地方跟着写一遍。 一、基础 1、Java 基础&#xff1a;尚硅谷 - Java基础 全部快速过一遍&#xff0c; 2、数据库&#xff1a;略。 着重 mysql 高级部分&#xff08;针对面试&#xff09;&…...

Python编程语言学习

1.Python 特点 Python是一种简单、易读、易学和高效的编程语言&#xff0c;具有以下特点&#xff1a; 简单易学&#xff1a;Python采用清晰简洁的语法&#xff0c;注重代码的可读性和可维护性&#xff0c;使得初学者能够快速上手并编写出清晰的代码。 面向对象&#xff1a;Py…...

Cartographer框架简述

catographer框架分为前端和后端 前端包括雷达数据处理&#xff1b;位姿预测&#xff1b;扫描匹配和栅格地图更新。 后端包括后端&#xff1a;线程池任务与调度&#xff1b;向位姿图添加节点&#xff0c;计算节点的子图内约束和子图间约束&#xff08;回环检测&#xff09;&…...

适用于 Linux、Windows 和 macOS 的免费 ONLYOFFICE 桌面应用程序

前言&#xff1a; 最近也是发现了一款特别好用的免费ONLYOFFICE 桌面应用程序忍不住分享给大家&#xff0c;这款编辑器能够打开、阅读和编辑多种文件类型&#xff0c;包括.docx文档、.pptx幻灯片和.xlsx表格等开放XML格式的Office文档。此外&#xff0c;ONLYOFFICE桌面编辑器还…...

C++面向对象程序设计-北京大学-郭炜【课程笔记(四)】

C面向对象程序设计-北京大学-郭炜【课程笔记&#xff08;四&#xff09;】 1、this指针1.1、this指针的作用1.2、this指针和静态成员函数 2、静态成员变量和静态成员函数2.1、基本概念2.2、基本概念总结2.3、如何访问静态成员2.4、静态成员变量的使用场景&#xff08;重要&…...

前端构建效率优化之路

项目背景 我们的系统&#xff08;一个 ToB 的 Web 单页应用&#xff09;前端单页应用经过多年的迭代&#xff0c;目前已经累积有大几十万行的业务代码&#xff0c;30 路由模块&#xff0c;整体的代码量和复杂度还是比较高的。 项目整体是基于 Vue TypeScirpt&#xff0c;而构…...

【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15

缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下&#xff1a; struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...

Spring Boot 实现流式响应(兼容 2.7.x)

在实际开发中&#xff0c;我们可能会遇到一些流式数据处理的场景&#xff0c;比如接收来自上游接口的 Server-Sent Events&#xff08;SSE&#xff09; 或 流式 JSON 内容&#xff0c;并将其原样中转给前端页面或客户端。这种情况下&#xff0c;传统的 RestTemplate 缓存机制会…...

visual studio 2022更改主题为深色

visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中&#xff0c;选择 环境 -> 常规 &#xff0c;将其中的颜色主题改成深色 点击确定&#xff0c;更改完成...

UE5 学习系列(三)创建和移动物体

这篇博客是该系列的第三篇&#xff0c;是在之前两篇博客的基础上展开&#xff0c;主要介绍如何在操作界面中创建和拖动物体&#xff0c;这篇博客跟随的视频链接如下&#xff1a; B 站视频&#xff1a;s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序

一、开发环境准备 ​​工具安装​​&#xff1a; 下载安装DevEco Studio 4.0&#xff08;支持HarmonyOS 5&#xff09;配置HarmonyOS SDK 5.0确保Node.js版本≥14 ​​项目初始化​​&#xff1a; ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...

使用Matplotlib创建炫酷的3D散点图:数据可视化的新维度

文章目录 基础实现代码代码解析进阶技巧1. 自定义点的大小和颜色2. 添加图例和样式美化3. 真实数据应用示例实用技巧与注意事项完整示例(带样式)应用场景在数据科学和可视化领域,三维图形能为我们提供更丰富的数据洞察。本文将手把手教你如何使用Python的Matplotlib库创建引…...

基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解

JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用&#xff0c;结合SQLite数据库实现联系人管理功能&#xff0c;并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能&#xff0c;同时可以最小化到系统…...

人工智能--安全大模型训练计划:基于Fine-tuning + LLM Agent

安全大模型训练计划&#xff1a;基于Fine-tuning LLM Agent 1. 构建高质量安全数据集 目标&#xff1a;为安全大模型创建高质量、去偏、符合伦理的训练数据集&#xff0c;涵盖安全相关任务&#xff08;如有害内容检测、隐私保护、道德推理等&#xff09;。 1.1 数据收集 描…...

Vue ③-生命周期 || 脚手架

生命周期 思考&#xff1a;什么时候可以发送初始化渲染请求&#xff1f;&#xff08;越早越好&#xff09; 什么时候可以开始操作dom&#xff1f;&#xff08;至少dom得渲染出来&#xff09; Vue生命周期&#xff1a; 一个Vue实例从 创建 到 销毁 的整个过程。 生命周期四个…...

ArcGIS Pro+ArcGIS给你的地图加上北回归线!

今天来看ArcGIS Pro和ArcGIS中如何给制作的中国地图或者其他大范围地图加上北回归线。 我们将在ArcGIS Pro和ArcGIS中一同介绍。 1 ArcGIS Pro中设置北回归线 1、在ArcGIS Pro中初步设置好经纬格网等&#xff0c;设置经线、纬线都以10间隔显示。 2、需要插入背会归线&#xf…...