Hash表算法

哈希表

  • 理论知识(本文来自于代码随想录摘抄)
    • 什么是哈希
    • 常见的三种哈希结
      • 数组:
      • set:
      • map:
      • 其他常用方法或者技巧(自己总结的)
    • 练习题和讲解
      • 有效的字母移位词
      • 349. 两个数组的交集
      • 1. 两数之和
      • 454. 四数相加 II
      • 15. 三数之和
    • 总结

理论知识(本文来自于代码随想录摘抄)

什么是哈希

哈希表中关键码就是数组的索引下标,然后通过下标直接访问数组中的元素,如下图所示:
在这里插入图片描述
那么哈希表能解决什么问题呢,一般哈希表都是用来快速判断一个元素是否出现集合里

常见的三种哈希结

当我们想使用哈希法来解决问题的时候,我们一般会选择如下三种数据结构。
数组
set (集合)
map(映射)

数组:

当目标的范围是已知的,是小的,我们会使用数组。(经常使用,所以少介绍。)

set:

在这里插入图片描述

map:

在这里插入图片描述

其他常用方法或者技巧(自己总结的)

在这里插入图片描述
10,用来判断某个值是否存在哈希表中:containsKey()

if(result.containsKey(temp)){}

练习题和讲解

有效的字母移位词

使用int
前置知识:
字母a-z,A-Z的ASCII码是连续的。
所以’a’-‘a’=0;‘z’-‘a’=25;
在这里插入图片描述

class Solution {public boolean isAnagram(String s, String t) {int[] arr=new int[26];              //用来存储26个字母出现的次数for(int i=0;i<s.length();i++){      //字符串用length()方法,数组为length。因为对于字符串,length是方法,数组是内置属性。    arr[s.charAt(i)-'a']++;             //charAt(i)获取字符串中i位置的字符。  我们在对于的下标的位置+1.比如出现z,则是'z'-'a',在25这个位置+1.};for(int i=0;i<t.length();i++){arr[t.charAt(i)-'a']--;         //目的同样,在对应位置-1,抵消s字符串中出现的字母。};for(int a:arr){                     //增强for循环方法。if(a!=0){                       //进行判断,如果不等0,证明两个里面的出现字母的数量不一致。return false;}}return true;}
}

349. 两个数组的交集

349. 两个数组的交集
使用set

class Solution {public int[] intersection(int[] nums1, int[] nums2) {if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {return new int[0];}                   //首先判断是否为空Set<Integer> set1 = new HashSet<>();        //使用set可以直接去重Set<Integer> resSet = new HashSet<>();//遍历数组1for (int i : nums1) {set1.add(i);    }//遍历数组2的过程中判断哈希表中是否存在该元素for (int i : nums2) {if (set1.contains(i)) {         //contains() 判断这个值是否在哈希表中resSet.add(i);}}//另外申请一个数组存放setRes中的元素,最后返回数组int[] arr = new int[resSet.size()];int j = 0;for(int i : resSet){arr[j++] = i;}return arr;}
}

1. 两数之和

1. 两数之和
使用map(需要存放 key value)

class Solution {public int[] twoSum(int[] nums, int target) {// 创建一个 HashMap 来存储数字及其对应的索引Map<Integer, Integer> map = new HashMap<>();int n = nums.length;// 遍历数组for (int i = 0; i < n; i++) {// 计算当前元素的补数int temp = target - nums[i];// 检查补数是否在 HashMap 中if (map.containsKey(temp)) {// 找到结果,那么返回当前索引和补数的索引return new int[]{map.get(temp), i};}// 如果没有找到补数,就把当前数字和它的索引放入 HashMapmap.put(nums[i], i);}// 如果没有找到,返回一个空数组,考虑到题目保证有解这里可以省略return new int[]{};}
}

454. 四数相加 II

454. 四数相加 II

class Solution {public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {int res = 0;//不仅要保存值,还需要保存其出现次数,所以使用map(key,value)来进行存储数据。Map<Integer, Integer> map = new HashMap<Integer, Integer>();//统计两个数组中的元素之和,同时统计出现的次数,放入mapfor (int i : nums1) {for (int j : nums2) {int sum = i + j;map.put(sum, map.getOrDefault(sum, 0) + 1);//getOrDefault这个的意思是,如果存在,返回存在的值,不存在返回default0}}//统计剩余的两个元素的和,在map中找是否存在相加为0的情况,同时记录次数for (int i : nums3) {for (int j : nums4) {//因为本题不去重,所以有不同组合,需要统计的值为 res+sum(对应的值);res += map.getOrDefault(0 - i - j, 0);}}return res;}
}

15. 三数之和

15. 三数之和

使用哈希集合:

class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> result = new ArrayList<>();Arrays.sort(nums);for (int i = 0; i < nums.length; i++) {// 如果第一个元素大于零,不可能凑成三元组if (nums[i] > 0) {return result;}// 三元组元素a去重if (i > 0 && nums[i] == nums[i - 1]) {continue;}HashSet<Integer> set = new HashSet<>();for (int j = i + 1; j < nums.length; j++) {// 三元组元素b去重if (j > i + 2 && nums[j] == nums[j - 1] && nums[j - 1] == nums[j - 2]) {continue;}int c = -nums[i] - nums[j];if (set.contains(c)) {result.add(Arrays.asList(nums[i], nums[j], c));set.remove(c); // 三元组元素c去重} else {set.add(nums[j]);}}}return result;}
}

使用双指针(更为推荐)

class Solution {public List<List<Integer>> threeSum(int[] nums) {//二维集合,因为不止一个集合List<List<Integer>> ans=new ArrayList();int len=nums.length;//如果值小于3,则没有意义if(len<3||nums==null) return ans;//排序,更方便我们双指针的移动Arrays.sort(nums);//定i的位置,然后动left和right两个指针的位置来凑0for(int i=0;i<len;i++){//如果第一个i都>0,则不可能三数之和为0if(nums[i]>0) break;//题目去重,所以我们判断前一位值如果等于后一位,则跳过。if(i>0&&nums[i]==nums[i-1]) continue;//定义左右指针    int L=i+1;int R=len-1;   while(L<R){int sum =nums[i]+nums[R]+nums[L];//如果相等,则添加进入二维数组中if(sum==0){ans.add(Arrays.asList(nums[i],nums[L],nums[R]));//归零while(L<R&& nums[L]==nums[L+1]) L++;while(L>R&& nums[R]==nums[R-1]) R--;L++;R--;}//和小,就左指针右移,和大,就右指针左移else  if(sum<0)L++;else if(sum>0)R--;}}//返回二维数组。return ans;}
}

总结

哈希表理论基础
在关于哈希表,你该了解这些! (opens new window)中,我们介绍了哈希表的基础理论知识,不同于枯燥的讲解,这里介绍了都是对刷题有帮助的理论知识点。

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

对于哈希表,要知道哈希函数和哈希碰撞在哈希表中的作用。

哈希函数是把传入的key映射到符号表的索引上。

哈希碰撞处理有多个key映射到相同索引上时的情景,处理碰撞的普遍方式是拉链法和线性探测法。

接下来是常见的三种哈希结构:

数组
set(集合)
map(映射)
在C++语言中,set 和 map 都分别提供了三种数据结构,每种数据结构的底层实现和用途都有所不同,在关于哈希表,你该了解这些! (opens new window)中我给出了详细分析,这一知识点很重要!

例如什么时候用std::set,什么时候用std::multiset,什么时候用std::unordered_set,都是很有考究的。

只有对这些数据结构的底层实现很熟悉,才能灵活使用,否则很容易写出效率低下的程序。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/459574.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

4款专业音频在线剪辑工具帮你开启创意之路。

音频在线剪辑工具能够为我们提供很大的便利&#xff0c;对于不管是专业的音乐制作人还是音频创作爱好者来说&#xff0c;都能借助一些音频编辑工具来充分发挥自己的创意。所以这一次&#xff0c;我要给大家介绍几个专业方便的音频剪辑工具。 1、福昕音频在线 直达链接&#x…

基于yolov8的布匹缺陷检测系统,支持图像、视频和摄像实时检测【pytorch框架、python源码】

更多目标检测和图像分类识别项目可看我主页其他文章 功能演示&#xff1a; 基于yolov8的布匹缺陷检测系统&#xff0c;支持图像、视频和摄像实时检测【pytorch框架、python源码】_哔哩哔哩_bilibili &#xff08;一&#xff09;简介 基于yolov8的布匹缺陷检测系统是在 PyTo…

基于SSM的心理咨询管理管理系统(含源码+sql+视频导入教程+文档+PPT)

&#x1f449;文末查看项目功能视频演示获取源码sql脚本视频导入教程视频 1 、功能描述 基于SSM的心理咨询管理管理系统拥有三个角色&#xff1a;学生用户、咨询师、管理员 管理员&#xff1a;学生管理、咨询师管理、文档信息管理、预约信息管理、测试题目管理、测试信息管理…

Cesium基础-(Entity)-(Corridor 走廊)

里边包含Vue、React框架代码详细步骤、以及代码详细解释 4、Corridor 走廊 以下是 CorridorGeometry 类的属性、方法和静态方法,以表格形式展示: 属性 属性名类型默认值描述positionsArray.定义走廊中心的坐标点数组。widthnumber走廊

预览 PDF 文档

引言 在现代Web应用中&#xff0c;文件预览功能是非常常见的需求之一。特别是在企业级应用中&#xff0c;用户经常需要查看各种类型的文件&#xff0c;如 PDF、Word、Excel 等。本文将详细介绍如何在Vue项目中实现 PDF 文档的预览功能。 实现原理 后端API 后端需要提供一个…

GIT使用list

清空当前commit区 方法 1&#xff1a;软重置到初始状态 如果希望保留文件内容&#xff0c;但清空所有 commit 历史&#xff0c;可以使用以下命令&#xff1a; git reset --soft $(git rev-list --max-parents0 HEAD)解释&#xff1a; --soft 表示重置 commit 历史&#xff…

uniapp的IOS证书申请(测试和正式环境)及UDID配置流程

1.说明 本教程只提供uniapp在ios端的证书文件申请&#xff08;包含正式环境和开发环境&#xff09;、UDID配置说明&#xff0c;请勿用文档中的账号和其他隐私数据进行测试&#xff0c;请勿侵权&#xff01; 2.申请前准备 证书生成网站&#xff1a;苹果应用上传、解析&#x…

【AscendC算子开发】笔记3 矩阵计算及高级开发技巧

pytorch调用算子 矩阵计算 为什么上图提供了两种矩阵结果访问方式&#xff1f; 如果只需要结果&#xff0c;那么拿注释的一行代码就可以得到结果&#xff0c;如果之后还有其他的操作&#xff0c;可以计算一小块就用起来&#xff0c;那么需要使用上述操作&#xff0c;可以形成流…

Unity Newtonsoft.Json 大对象序列化失败

Unity Newtonsoft.Json 大对象序列化失败 &#x1f4a3;崩溃了没&#xff1f;&#x1f600;替代方案 &#x1f4a3;崩溃了没&#xff1f; Newtonsoft.Json.JsonTextWriter:WriteValueInternal(string,Newtonsoft.Json.JsonToken) InvalidCastException: Specified cast is not…

Kafka认证时Successfully logged in真的认证成功了?

背景 某个应用需要配置 Kafka 集群信息&#xff0c;且需要在验证集群是否可达。基本实现思路是创建一个生产者对象&#xff0c;然后发送一条测试数据&#xff0c;调用 Producer 的 send 方法发送消息后&#xff0c;再调用 get() 方法&#xff0c;即同步发送消息&#xff0c;测…

SpringBoot后端开发常用工具详细介绍——flyway数据库版本控制工具

文章目录 什么是flyway简介为什么要使用flyway 流程介绍整合springboot添加pom文件配置flyway向resource/db/migration添加sql文件 注意事项1. 迁移报错2. 迁移顺序 参考 什么是flyway 简介 为什么要使用flyway 我们在开发时往往会有这样一种情况&#xff1a; 进行软件开发…

【Linux系统编程】线程深入运用

目录 一&#xff0c;C线程与系统线程 二&#xff0c;分离线程 三&#xff0c;线程结构 四&#xff0c;__thread关键字 五&#xff0c;Linux线程互斥 1&#xff0c;线程互斥相关的背景概念 2&#xff0c;互斥锁 3&#xff0c;死锁 4&#xff0c;互斥锁的弊端 六&#…

2024年10月25日练习(双指针算法)

一.283. 移动零 - 力扣&#xff08;LeetCode&#xff09; 1.题目描述&#xff1a; 这里题目要求了说必须在不复制数组的情况下对数组进行原地操作&#xff0c;所以说不能来用暴力的解法来 实现。 2.算法原理&#xff1a; 这个题目就是经典的数组划分&#xff0c;数组分块问题…

react-signature-canvas 实现画笔与橡皮擦功能

react-signature-canvas git 地址 代码示例 import React, { Component } from react import { createRoot } from react-dom/clientimport SignaturePad from ../../src/index.tsximport * as styles from ./styles.module.cssclass App extends Component {state { trimmed…

NLTK无法下载?

以下内容仅为当前认识&#xff0c;可能有不足之处&#xff0c;欢迎讨论&#xff01; 文章目录 nltk无法下载怎么办&#xff1f;什么是NLTK&#xff1f;为什么要用NLTK&#xff1f;如何下载&#xff1f; nltk无法下载怎么办&#xff1f; 什么是NLTK&#xff1f; NLTK是学习自然…

【Qt】窗口——Qt窗口的概念、常用的窗口函数、菜单栏、工具栏、状态栏、浮动窗口、对话框

文章目录 Qt窗口Qt窗口的概念菜单栏工具栏状态栏浮动窗口对话框 Qt 窗口 Qt窗口的概念 QMainWindow 类概述&#xff1a; QMainWindow 是一个为用户提供主窗口程序的类&#xff0c;它继承自 QWidget 类&#xff0c;并且提供了一个预定义的布局。 菜单栏 菜单栏常用属性&#xf…

紫光同创——盘古 50KN 网口板

本原创文章由深圳市小眼睛科技有限公司创作&#xff0c;版权归本公司所有&#xff0c;如需转载&#xff0c;需授权并注明出处&#xff08;www.meyesemi.com) 一、开发系统介绍 盘古 50KN 网口板开发板&#xff08;MES50H-Ethernet&#xff09;采用了核心板扩展板的结 构&#…

---synchronized 关键字---

在多线程编程中&#xff0c;由于代码的并发执行&#xff0c;导致了不同的线程在修改相同的变量会导致变量的值错误 比如 变量 c 2&#xff0c;这里有线程A 和 B一起使用 c变量并对他加1&#xff0c;这时就会有多中情况 这里要注意的是变量c是储存在内存中的&#xff0c;而线…

【git】 git 删除了文件,如何找回

git 删除了文件&#xff0c;如何找回 使用 git revert 并不是恢复误删除文件的最佳方法&#xff0c;因为 git revert 通常用于撤销已经提交的更改&#xff08;生成一个反向提交&#xff09;。如果你误删除了文件&#xff0c;还未提交更改&#xff0c;或者已经提交但想恢复删除…

2024年9月电子学会青少年软件编程Python等级考试(三级)真题试卷

2024年9月青少年软件编程Python等级考试&#xff08;三级&#xff09;真题试卷 选择题 第 1 题 单选题 以下python表达式的值为True的是&#xff1f;&#xff08; &#xff09; A.all( ,1,2,3) B.any([]) C.bool(abc) D.divmod(6,0) 第 2 题 单选题 下列python代码的…