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

【20230206-0209】哈希表小结

哈希表

一般哈希表都是用来快速判断一个元素是否出现在集合里。

哈希函数

哈希碰撞--解决方法:拉链法和线性探测法。

拉链法:冲突的元素都被存储在链表中

线性探测法:一定要保证tableSize大于dataSize,利用哈希表中的空位解决碰撞问题。

三种哈希结构

数组、set(集合)、map(映射)

set与map的共同点:

set、map都是C++的关联容器,只是通过它提供的接口对里面的元素进行访问,底层都是采用红黑树实现。

set与map的不同点:

set:用来判断一个元素是否在一个组里。

map:映射,相当于字典,把一个值映射成另一个值,可以创建字典。

set

map

小结

当要用集合来解决哈希问题时,优先使用unordered_set,因为它的查询和增删效率是最优的,如果需要集合有序,就用set,要有重复数据,就用multiset。


1.为什么要成倍的扩容,而不是一次增加一个固定大小的容量?

保证常数的时间复杂度。

2.为什么以两倍方式扩容?

考虑可能产生的堆空间浪费,所以增长倍数不能太大。

3.为什么insert后,以前保存的iterator不会失效?

因为map和set储存的是节点,不需要内存拷贝和内存移动。但是vector在插入数据时如果内存不够,会重新开辟一块内存。map和set的iterator指向的是节点的指针,vector指向的是内存的某个位置。

4.为什么map和set的插入删除效率比其他序列容器高?

因为map和set底层实现为红黑树,插入和删除的时间复杂度为O(logn)。


例题:

  1. 有效的字母异位词(小写字母,用数组!)

  1. 赎金信(与有效的字母异位词类似)

  1. 两个数组的交集(输出结果是去重的,无序的,用unordered_set)

  1. 两个数组的交集II(哈希映射,有重复元素)

  1. 字母异位词分组(字符串排序的效果、通过设计哈希表中的键值进行归类)

  1. 快乐数(各个位上数的提取、判断是否有重复的数字出现,是否出现了死循环或者出现了1)

  1. 两数之和(经典,利用哈希查询效率高)

  1. 四数相加II(四个数组,两两分组)

//9、10使用双指针

  1. 三数之和(双指针法,对三个元素的去重)

  1. 四数之和(与三数之和类似,在一级剪枝时,判断条件要注意,nums[i]>0且target>0,对各个元素进行去重

相关文章:

【20230206-0209】哈希表小结

哈希表一般哈希表都是用来快速判断一个元素是否出现在集合里。哈希函数哈希碰撞--解决方法:拉链法和线性探测法。拉链法:冲突的元素都被存储在链表中线性探测法:一定要保证tableSize大于dataSize,利用哈希表中的空位解决碰撞问题。…...

c++11 标准模板(STL)(std::multimap)(一)

定义于头文件 <map> template< class Key, class T, class Compare std::less<Key>, class Allocator std::allocator<std::pair<const Key, T> > > class multimap;(1)namespace pmr { template <class Key, class T…...

python进阶——自动驾驶寻找车道

大家好&#xff0c;我是csdn的博主&#xff1a;lqj_本人 这是我的个人博客主页&#xff1a; lqj_本人的博客_CSDN博客-微信小程序,前端,python领域博主lqj_本人擅长微信小程序,前端,python,等方面的知识https://blog.csdn.net/lbcyllqj?spm1011.2415.3001.5343哔哩哔哩欢迎关注…...

男,26岁,做了一年多的自动化测试,最近在纠结要不要转行,求指点。?

最近一个粉丝在后台问我&#xff0c;啊大佬我现在26了&#xff0c;做了做了一年多的自动化测试&#xff0c;最近在纠结要不要转行&#xff0c;求指点。首选做IT这条路&#xff0c;就是很普通的技术蓝领。对于大部分来说干一辈子问题不大&#xff0c;但是发不了什么财。如果你在…...

源码级别的讲解JAVA 中的CAS

没有CAS之前实现线程安全 多线程环境不使用原子类保证线程安全&#xff08;基本数据类型&#xff09; public class T3 {volatile int number 0;//读取public int getNumber(){return number;}//写入加锁保证原子性public synchronized void setNumber(){number;} }多线程环…...

JUC锁与AQS技术【我的Android开发技术】

JUC锁与AQS技术【我的Android开发技术】 AQS原理 AQS就是一个同步器&#xff0c;要做的事情就相当于一个锁&#xff0c;所以就会有两个动作&#xff1a;一个是获取&#xff0c;一个是释放。获取释放的时候该有一个东西来记住他是被用还是没被用&#xff0c;这个东西就是一个状…...

【问题代码】顺序点的深入理解(汇编剖析+手画图解)

这好像是一个哲学问题。 目录 前言 一、顺序点是什么&#xff1f; 二、发生有关顺序点的问题代码 vs中&#xff1a; gcc中&#xff1a; 三、细读汇编 1.vs汇编如下&#xff08;示例&#xff09;&#xff1a; 2.gcc汇编如下&#xff08;示例&#xff09;&#xff1a; 四…...

BinaryAI全新代码匹配模型BAI-2.0上线,“大模型”时代的安全实践

导语BinaryAI&#xff08;https://www.binaryai.net&#xff09;科恩实验室在2021年8月首次发布二进制安全智能分析平台—BinaryAI&#xff0c;BinaryAI可精准高效识别二进制文件的第三方组件及其版本号&#xff0c;旨在推动SCA&#xff08;Software Composition Analysis&…...

nvidia设置wifi和接口

tx-nx设置wifi和接口前言基础知识点1.创建和删除一个wifi连接2. 启动连接和关闭连接代码和调试1. 代码展示2. 调试写到最后前言 针对嵌入式开发&#xff0c;有时候通过QT或PAD跨网络对设备设置WIFI&#xff0c;在此记录下&#xff0c;方便后续的查阅。 基础知识点 1.创建和删…...

PostgreSQL 变化数据捕捉(CDC)

PostgreSQL 变化数据捕捉&#xff08;CDC&#xff09;基于CDC&#xff08;变更数据捕捉&#xff09;的增量数据集成总体步骤&#xff1a;1.捕获源数据库中的更改数据2.将变更的数据转换为您的消费者可以接受的格式3.将数据发布到消费者或目标数据库PostgreSQL支持触发器&#x…...

Spring 事务【隔离级别与传播机制】

Spring 事务【隔离级别与传播机制】&#x1f34e;一.事务隔离级别&#x1f352;1.1 事务特性回顾&#x1f352;1.2 事务的隔离级别(5种)&#x1f352;1.3 事务隔离级别的设置&#x1f34e;二.Spring 事务传播机制&#x1f352;2.1 Spring 事务传播机制的作用&#x1f352;2.2 事…...

HTTP和HTTPS协议

HTTP协议 HTTP协议是一种应用层的协议&#xff0c;全称为超文本传输协议。 URL URL值统一资源定位标志&#xff0c;也就是俗称的网址。 协议方案名 http://表示的就是协议方案名&#xff0c;常用的协议有HTTP协议、HTTPS协议、FTP协议等。HTTPS协议是以HTTP协议为基础&#…...

day3——有关java运算符的笔记

今天主要学习的内容有java的运算符 赋值运算符算数运算符关系运算符逻辑运算符位运算符&#xff08;专门写一篇笔记&#xff09;条件运算符运算符的优先级流程控制 赋值运算符 赋值运算符&#xff08;&#xff09;主要用于给变量赋值&#xff0c;可以跟算数运算符相结合&…...

Git多人协同远程开发

1. 李四&#xff08;项目负责人&#xff09;操作步骤 在github中创建远程版本库testgit将基础代码上传⾄testgit远程库远程库中基于main分⽀创建dev分⽀将 githubleaflife/testgit 共享给组员李四继续在基础代码上添加⾃⼰负责的模块内容 2. 张三、王五&#xff08;组员&…...

Chapter4:机器人仿真

ROS1{\rm ROS1}ROS1的基础及应用&#xff0c;基于古月的课&#xff0c;各位可以去看&#xff0c;基于hawkbot{\rm hawkbot}hawkbot机器人进行实际操作。 ROS{\rm ROS}ROS版本&#xff1a;ROS1{\rm ROS1}ROS1的Melodic{\rm Melodic}Melodic&#xff1b;实际机器人&#xff1a;Ha…...

python(14)--集合

前言 本篇文章学习的是 python 中集合的基础知识。 集合元素的内容是不可变的&#xff0c;常见的元素有整数、浮点数、字符串、元组等。至于可变内容列表、字典、集合等不可以是集合元素。虽然集合不可以是集合的元素&#xff0c;但是集合本身是可变的&#xff0c;可以去增加或…...

【Spark分布式内存计算框架——Spark Core】4. RDD函数(中)Transformation函数、Action函数

3.2 Transformation函数 在Spark中Transformation操作表示将一个RDD通过一系列操作变为另一个RDD的过程&#xff0c;这个操作可能是简单的加减操作&#xff0c;也可能是某个函数或某一系列函数。值得注意的是Transformation操作并不会触发真正的计算&#xff0c;只会建立RDD间…...

Mysql 数据类型

1、数值数据类型 1.1 整数类型(精确值) INTEGER, INT, SMALLINT, TINYINT, MEDIUMINT, BIGINT MySQL支持SQL标准的整数类型INTEGER (或INT)和SMALLINT。作为标准的扩展&#xff0c;MySQL还支持整数类型TINYINT、MEDIUMINT和BIGINT。下表显示了每种整数类型所需的存储和范围。…...

运行Whisper笔记(1)

最近chatGPT很火&#xff0c;就去逛了一下openai的github项目。发现了这个项目。 这个项目可以识别视频中的音频&#xff0c;转换出字幕。 带着一颗好奇的心就尝试自己去部署玩一玩 跟着这篇文章一步步来进行安装&#xff0c;并且跟着这篇文章解决途中遇到的问题。 途中还会遇…...

2023年最强大的12款数据可视化工具,值得收藏

做数据分析也有年头了&#xff0c;好的坏的工具都用过&#xff0c;推荐几个觉得很好用的&#xff0c;避坑必看&#xff01; PS&#xff1a;一般比较成熟的公司里&#xff0c;数据分析工具不只是满足业务分析和报表制作&#xff0c;像我现在给我们公司选型BI工具&#xff0c;是做…...

多模态2025:技术路线“神仙打架”,视频生成冲上云霄

文&#xff5c;魏琳华 编&#xff5c;王一粟 一场大会&#xff0c;聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中&#xff0c;汇集了学界、创业公司和大厂等三方的热门选手&#xff0c;关于多模态的集中讨论达到了前所未有的热度。其中&#xff0c;…...

以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:

一、属性动画概述NETX 作用&#xff1a;实现组件通用属性的渐变过渡效果&#xff0c;提升用户体验。支持属性&#xff1a;width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项&#xff1a; 布局类属性&#xff08;如宽高&#xff09;变化时&#…...

UDP(Echoserver)

网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法&#xff1a;netstat [选项] 功能&#xff1a;查看网络状态 常用选项&#xff1a; n 拒绝显示别名&#…...

ios苹果系统,js 滑动屏幕、锚定无效

现象&#xff1a;window.addEventListener监听touch无效&#xff0c;划不动屏幕&#xff0c;但是代码逻辑都有执行到。 scrollIntoView也无效。 原因&#xff1a;这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作&#xff0c;从而会影响…...

第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词

Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵&#xff0c;其中每行&#xff0c;每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid&#xff0c;其中有多少个 3 3 的 “幻方” 子矩阵&am…...

接口自动化测试:HttpRunner基础

相关文档 HttpRunner V3.x中文文档 HttpRunner 用户指南 使用HttpRunner 3.x实现接口自动化测试 HttpRunner介绍 HttpRunner 是一个开源的 API 测试工具&#xff0c;支持 HTTP(S)/HTTP2/WebSocket/RPC 等网络协议&#xff0c;涵盖接口测试、性能测试、数字体验监测等测试类型…...

日常一水C

多态 言简意赅&#xff1a;就是一个对象面对同一事件时做出的不同反应 而之前的继承中说过&#xff0c;当子类和父类的函数名相同时&#xff0c;会隐藏父类的同名函数转而调用子类的同名函数&#xff0c;如果要调用父类的同名函数&#xff0c;那么就需要对父类进行引用&#…...

水泥厂自动化升级利器:Devicenet转Modbus rtu协议转换网关

在水泥厂的生产流程中&#xff0c;工业自动化网关起着至关重要的作用&#xff0c;尤其是JH-DVN-RTU疆鸿智能Devicenet转Modbus rtu协议转换网关&#xff0c;为水泥厂实现高效生产与精准控制提供了有力支持。 水泥厂设备众多&#xff0c;其中不少设备采用Devicenet协议。Devicen…...

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…...

【无标题】湖北理元理律师事务所:债务优化中的生活保障与法律平衡之道

文/法律实务观察组 在债务重组领域&#xff0c;专业机构的核心价值不仅在于减轻债务数字&#xff0c;更在于帮助债务人在履行义务的同时维持基本生活尊严。湖北理元理律师事务所的服务实践表明&#xff0c;合法债务优化需同步实现三重平衡&#xff1a; 法律刚性&#xff08;债…...