当前位置: 首页 > 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;而构…...

linux之kylin系统nginx的安装

一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源&#xff08;HTML/CSS/图片等&#xff09;&#xff0c;响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址&#xff0c;提高安全性 3.负载均衡服务器 支持多种策略分发流量…...

(十)学生端搭建

本次旨在将之前的已完成的部分功能进行拼装到学生端&#xff0c;同时完善学生端的构建。本次工作主要包括&#xff1a; 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...

Debian系统简介

目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版&#xff…...

线程同步:确保多线程程序的安全与高效!

全文目录&#xff1a; 开篇语前序前言第一部分&#xff1a;线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分&#xff1a;synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分&#xff…...

【网络安全产品大调研系列】2. 体验漏洞扫描

前言 2023 年漏洞扫描服务市场规模预计为 3.06&#xff08;十亿美元&#xff09;。漏洞扫描服务市场行业预计将从 2024 年的 3.48&#xff08;十亿美元&#xff09;增长到 2032 年的 9.54&#xff08;十亿美元&#xff09;。预测期内漏洞扫描服务市场 CAGR&#xff08;增长率&…...

OkHttp 中实现断点续传 demo

在 OkHttp 中实现断点续传主要通过以下步骤完成&#xff0c;核心是利用 HTTP 协议的 Range 请求头指定下载范围&#xff1a; 实现原理 Range 请求头&#xff1a;向服务器请求文件的特定字节范围&#xff08;如 Range: bytes1024-&#xff09; 本地文件记录&#xff1a;保存已…...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)

UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中&#xff0c;UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化&#xf…...

MySQL账号权限管理指南:安全创建账户与精细授权技巧

在MySQL数据库管理中&#xff0c;合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号&#xff1f; 最小权限原则&#xf…...

mac 安装homebrew (nvm 及git)

mac 安装nvm 及git 万恶之源 mac 安装这些东西离不开Xcode。及homebrew 一、先说安装git步骤 通用&#xff1a; 方法一&#xff1a;使用 Homebrew 安装 Git&#xff08;推荐&#xff09; 步骤如下&#xff1a;打开终端&#xff08;Terminal.app&#xff09; 1.安装 Homebrew…...

Spring AI Chat Memory 实战指南:Local 与 JDBC 存储集成

一个面向 Java 开发者的 Sring-Ai 示例工程项目&#xff0c;该项目是一个 Spring AI 快速入门的样例工程项目&#xff0c;旨在通过一些小的案例展示 Spring AI 框架的核心功能和使用方法。 项目采用模块化设计&#xff0c;每个模块都专注于特定的功能领域&#xff0c;便于学习和…...