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

<6>-MySQL表的增删查改

目录 一&#xff0c;create&#xff08;创建表&#xff09; 二&#xff0c;retrieve&#xff08;查询表&#xff09; 1&#xff0c;select列 2&#xff0c;where条件 三&#xff0c;update&#xff08;更新表&#xff09; 四&#xff0c;delete&#xff08;删除表&#xf…...

MongoDB学习和应用(高效的非关系型数据库)

一丶 MongoDB简介 对于社交类软件的功能&#xff0c;我们需要对它的功能特点进行分析&#xff1a; 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具&#xff1a; mysql&#xff1a;关系型数据库&am…...

【Linux】C语言执行shell指令

在C语言中执行Shell指令 在C语言中&#xff0c;有几种方法可以执行Shell指令&#xff1a; 1. 使用system()函数 这是最简单的方法&#xff0c;包含在stdlib.h头文件中&#xff1a; #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...

FastAPI 教程:从入门到实践

FastAPI 是一个现代、快速&#xff08;高性能&#xff09;的 Web 框架&#xff0c;用于构建 API&#xff0c;支持 Python 3.6。它基于标准 Python 类型提示&#xff0c;易于学习且功能强大。以下是一个完整的 FastAPI 入门教程&#xff0c;涵盖从环境搭建到创建并运行一个简单的…...

电脑插入多块移动硬盘后经常出现卡顿和蓝屏

当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时&#xff0c;可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案&#xff1a; 1. 检查电源供电问题 问题原因&#xff1a;多块移动硬盘同时运行可能导致USB接口供电不足&#x…...

[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...

Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级

在互联网的快速发展中&#xff0c;高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司&#xff0c;近期做出了一个重大技术决策&#xff1a;弃用长期使用的 Nginx&#xff0c;转而采用其内部开发…...

【开发技术】.Net使用FFmpeg视频特定帧上绘制内容

目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法&#xff0c;当前调用一个医疗行业的AI识别算法后返回…...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖

在Vuzix M400 AR智能眼镜的助力下&#xff0c;卢森堡罗伯特舒曼医院&#xff08;the Robert Schuman Hospitals, HRS&#xff09;凭借在无菌制剂生产流程中引入增强现实技术&#xff08;AR&#xff09;创新项目&#xff0c;荣获了2024年6月7日由卢森堡医院药剂师协会&#xff0…...

【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)

本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...