【算法系列篇】哈希表
文章目录
- 前言
- 1. 两数之和
- 1.1 题目要求
- 1.2 做题思路
- 1.3 Java代码实现
- 2. 判断是否为字符重排
- 2.1 题目要求
- 2.2 做题思路
- 2.3 Java代码实现
- 3. 存在重复元素
- 3.1 题目要求
- 3.2 做题思路
- 3.3 Java代码实现
- 4. 存在重复元素II
- 4.2 题目要求
- 4.2 做题思路
- 4.3 Java代码实现
- 5. 字母异位词分组
- 5.1 题目要求
- 5.2 做题思路
- 5.3 Java代码实现
前言
哈希表(Hash Table)是一种依赖哈希函数组织数据,以达到常数级别时间复杂度,插入和搜索都非常高效的数据结构。它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。哈希表在查询数据方面有着突出的优势。那么今天我将为大家分享关于哈希表方面的算法。
1. 两数之和
https://leetcode.cn/problems/two-sum/?envType=list&envId=9Lulrn6r
1.1 题目要求
给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1:
输入:nums = [2,7,11,15], target = 9
输出:[0,1]
解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。
示例 2:
输入:nums = [3,2,4], target = 6
输出:[1,2]
示例 3:
输入:nums = [3,3], target = 6
输出:[0,1]
提示:
2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案
class Solution {public int[] twoSum(int[] nums, int target) {}
}
1.2 做题思路
这道题目的要求很简单,就是在数组中查找两个和为 target 的数。使用暴力解法就是列举出数组中任意两个数的组合,看它们的和是否等于target,暴力解法的时间复杂度为 O(N*2) 。
既然是查询的话,我们就可以用到哈希表这个数据结构来降低时间复杂度。使用哈希表只需要遍历一遍数组,当遍历到一个数的时候,就看哈希表中是否存在一个数等于 target - nums[i] 如果有则返回当前这个数的下标和哈希表中存储的 target - num[i] 的下标;如果不存在,则将该位置的数作为 key 值,该位置的下标作为 value 值存放进哈希表中。
1.3 Java代码实现
class Solution {public int[] twoSum(int[] nums, int target) {//创建出一个哈希表Map<Integer, Integer> map = new HashMap<>();for (int i = 0; i < nums.length; i++) {int t = target - nums[i];if (map.containsKey(t)) return new int[]{i, map.get(t)};map.put(nums[i], i);}return new int[]{-1,-1};}
}
2. 判断是否为字符重排
https://leetcode.cn/problems/check-permutation-lcci/?envType=list&envId=9Lulrn6r
2.1 题目要求
给定两个由小写字母组成的字符串 s1 和 s2,请编写一个程序,确定其中一个字符串的字符重新排列后,能否变成另一个字符串。
示例 1:
输入: s1 = "abc", s2 = "bca"
输出: true
示例 2:
输入: s1 = "abc", s2 = "bad"
输出: false
说明:
0 <= len(s1) <= 100
0 <= len(s2) <= 100
class Solution {public boolean CheckPermutation(String s1, String s2) {}
}
2.2 做题思路
判断是否为字符重排的方法就是看字符串 str2 中的字符是否都包含且只包含字符串 str1 中的字符,要想判断字符串 str2 中的字符是否存在于字符串 str1 中且数量一样,就可以用到哈希表来作为存储的容器。先遍历一遍字符串 str1,将字符串 str1 中遇到的字符以及字符出现的次数存储下来,然后在遍历字符串 str2 中的每个字符的时候就看哈希表中是否存在这个字符。
2.3 Java代码实现
class Solution {public boolean CheckPermutation(String s1, String s2) {int len1 = s1.length();int len2 = s2.length();//当两个字符串长度不相同的时候可以直接返回if (len1 != len2) return false;//这里使用数组模拟出哈希表是因为题目中给出了字符串中的字符都是小写字母//字符的范围给了,数组的存储和读取速度相较于哈希表速度更快int[] hash = new int[26];for (int i = 0; i < len1; i++) {hash[s1.charAt(i) - 'a']++;}for (int i = 0; i < len2; i++) {if (--hash[s2.charAt(i) - 'a'] < 0) return false;}return true;}
}
3. 存在重复元素
https://leetcode.cn/problems/contains-duplicate/?envType=list&envId=9Lulrn6r
3.1 题目要求
给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ,返回 true ;如果数组中每个元素互不相同,返回 false 。
示例 1:
输入:nums = [1,2,3,1]
输出:true
示例 2:
输入:nums = [1,2,3,4]
输出:false
示例 3:
输入:nums = [1,1,1,3,3,4,3,2,4,2]
输出:true
提示:
1 <= nums.length <= 105
-109 <= nums[i] <= 109
class Solution {public boolean containsDuplicate(int[] nums) {}
}
3.2 做题思路
判断数组中是否存在重复元素,我们可以也可以使用哈希表这种数据结构来判断重复。HashSet 里面保证了容器中的元素只存在一个,具有去重性。
3.3 Java代码实现
class Solution {public boolean containsDuplicate(int[] nums) {Set<Integer> set = new HashSet<>();for(int n : nums) {if (set.contains(n)) return true;set.add(n);}return false;}
}
4. 存在重复元素II
https://leetcode.cn/problems/contains-duplicate-ii/?envType=list&envId=9Lulrn6r
4.2 题目要求
给你一个整数数组 nums 和一个整数 k ,判断数组中是否存在两个 不同的索引 i 和 j ,满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在,返回 true ;否则,返回 false 。
示例 1:
输入:nums = [1,2,3,1], k = 3
输出:true
示例 2:
输入:nums = [1,0,1,1], k = 1
输出:true
示例 3:
输入:nums = [1,2,3,1,2,3], k = 2
输出:false
提示:
1 <= nums.length <= 105
-109 <= nums[i] <= 109
0 <= k <= 105
class Solution {public boolean containsNearbyDuplicate(int[] nums, int k) {}
}
4.2 做题思路
这道题目是上面的重复元素的延展,这道题目不仅需要判断是否存在重复的元素,还需要判断这两个重复元素的下标的差值小于等于k。所以这个题目就需要用到哈希表 HashMap 这种数据结构,将某位置所表示的数字作为 key 值,该位置的下标作为 value 值存放在哈希表中。当该位置的数字在哈希表中存在的时候,就判断这两个数字的下标的差值是否小于等于k,如果小于则直接返回true,如果不小于,则需要更新哈希表中该key值的value值,因为这题目的要求是两个相等元素的下标差值小于等于k。
4.3 Java代码实现
class Solution {public boolean containsNearbyDuplicate(int[] nums, int k) {Map<Integer, Integer> map = new HashMap<>();for (int i = 0; i < nums.length; i++) {if(map.containsKey(nums[i])) {if(i - map.get(nums[i]) <= k) return true;}//这个操作不仅可以解决第一次添加的问题,也可以解决覆盖之前key的valuemap.put(nums[i], i);}return false;}
}
5. 字母异位词分组
https://leetcode.cn/problems/group-anagrams/
5.1 题目要求
给你一个字符串数组,请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
示例 1:
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
示例 2:
输入: strs = [""]
输出: [[""]]
示例 3:
输入: strs = ["a"]
输出: [["a"]]
提示:
1 <= strs.length <= 104
0 <= strs[i].length <= 100
strs[i] 仅包含小写字母
class Solution {public List<List<String>> groupAnagrams(String[] strs) {}
}
5.2 做题思路
这个题目的意思就是将可以构成异位词的字符串分在一组,异位词就是两个字符串都是由相同字符以及字符数量相等的字符组成的字符串。但是这个题目有很多组的异位词,我们遍历字符串的时候又该如何判断该字符串属于哪一个组呢?难道要在遍历一遍哈希表吗,这样时间复杂度也会很高,所以我们不使用这个方法。
这道题的思路是,将字符串经过 ASCII 码排序之后作为key值存放在哈希表中,然后哈希表的value值是一个链表,用来存储同一组异位词,当遍历字符串的时候也是将该字符串进行 ASCII 码排序之后将这个字符串放入指定的key-value中。
5.3 Java代码实现
class Solution {public List<List<String>> groupAnagrams(String[] strs) {Map<String, List<String>> map = new HashMap<>();for(String s : strs) {//将字符串转换为字符数组之后进行排序,然后再转换为字符串char[] tmp = s.toCharArray();Arrays.sort(tmp);String key = new String(tmp);//如果哈希表中不存在key值,则需要先创建出key的Listif (!map.containsKey(key)) {map.put(key, new ArrayList<String>());}//将该字符串添加进对应分组中map.get(key).add(s);}return new ArrayList(map.values());}
}
相关文章:

【算法系列篇】哈希表
文章目录 前言1. 两数之和1.1 题目要求1.2 做题思路1.3 Java代码实现 2. 判断是否为字符重排2.1 题目要求2.2 做题思路2.3 Java代码实现 3. 存在重复元素3.1 题目要求3.2 做题思路3.3 Java代码实现 4. 存在重复元素II4.2 题目要求4.2 做题思路4.3 Java代码实现 5. 字母异位词分…...

计算机视觉——飞桨深度学习实战-起始篇
后面我会直接跳到实战项目,将计算机视觉的主要任务和目标都实现一遍,但是需要大家下去自己多理解和学习一下。例如,什么是深度学习,什么是计算机视觉,什么是自然语言处理,计算机视觉的主要任务有哪些&#…...
vscode中运行脚手架项目报表
必选在cmd页面里面安装脚手架离谱啊,不然无法执行npm命令啊 vscode运行vue项目_小何不秃头06的博客-CSDN博客 finereport激活成功 - 帆软 (fanruan.com)...

中睿天下荣获2023全国智能驾驶测试赛车联网安全比赛第一名
9月24日,由工业和信息化部、公安部、交通运输部、中国科学技术协会、北京市人民政府共同主办的2023世界智能网联汽车大会展览会在北京闭幕。同期举行的全国智能驾驶测试赛(京津冀赛区)宣布比赛结果,中睿天下凭借过硬的产品实力&am…...

opencv图像数组坐标系
在OpenCV的Python接口(cv2)中,加载的图像数组遵循以下坐标系和方向约定: 1. **坐标系:** OpenCV的坐标系遵循数学中的坐标系,原点(0, 0)位于图像的左上角。横轴(X轴&…...

zookeeper mac安装
目录 1.下载zookeeper安装包 2.解压安装包 3.修改配置文件 4.启动服务端 5.启动客户端 这边工作中用到了zookeeper组件,但自己独立安装弄的不太多,这边本机mac装一个做测试使用 以下是安装记录,可以作为参考 从以下链接zookeeper版本列…...
js生成随机16进制数
在JavaScript中,可以使用以下的代码来生成一个100位的随机十六进制数: function generateRandomHex(length) {var result ;var characters 0123456789abcdef;for (var i 0; i < length; i) {result characters.charAt(Math.floor(Math.random() …...

第七章 查找 八、B树
目录 一、定义 二、B树的核心特性 1、B树各个结点的子树数和关键字数 2、子树高度 3、关键字的值 4、B树高度 三、B树的插入 四、B树的删除 一、定义 B树,又称多路平衡查找树,B树中所有结点的孩子个数的最大值称为B树的阶,通常用m表示…...

Vue以及整合ElementUI
初始化vue项目 #vue 脚手架使用 webpack 模板初始化一个 appname 项目 vue init webpack appname启动 vue 项目 #项目的 package.json 中有 scripts,代表我们能运行的命令 npm start npm run dev #启动项目 npm run build:将项目打包项目结构 运行流程…...

免费、丰富、便捷的资源论坛——Yiove论坛,包括但不限于阿里云盘、夸克云盘、迅雷云盘等等
引言 目前资源的数量达到了60000,六万多的资源意味着在这里几乎可以找到任何你想要的资源。 当然,资源并不是论坛的全部,其中还包括了技术交流、福利分享、最新资讯等等。 传送门:YiOVE论坛 - 一个有资源有交流,有一…...

1.3 互联网的组成
思维导图: 前言: 我的笔记: #### 一、总览 - **互联网的结构**: - 具有全球覆盖和复杂的拓扑结构。 - 即便结构复杂,还是可以从工作方式上简化为两大部分:边缘部分和核心部分。 #### 二、边缘部分 -…...

【机器学习】熵和概率分布,图像生成中的量化评估IS与FID
详解机器学习中的熵、条件熵、相对熵、交叉熵 图像生成中常用的量化评估指标通常有Inception Score (IS)和Frchet Inception Distance (FID) Inception Score (IS) 与 Frchet Inception Distance (FID) GAN的量化评估方法——IS和FID,及其pytorch代码...

Vue3.0跨端Web SDK访问微信小程序云储存,文件上传路径不存在/文件受损无法显示问题(已解决)
整理需求: 需要vue3.0作为pc端的后台管理来连接微信小程序客户端需要Web SDK的引入,实现vue3.0接入云开发环境需要以云环境作为线上服务器,将vue3.0上传的本地文件通过云环境进入云储存,并将文件在云端生成云端快捷访问路径及htt…...

使用chat GPT 生成一个js 生成天数的方法
function calculateDaysDifference(targetDateString) {const currentDate new Date();const targetDate new Date(targetDateString);// 计算毫秒差异const timeDifference targetDate - currentDate;// 计算天数差异,如果结果为负数,则设置为0const…...

BUUCTF reverse wp 76 - 80
[CISCN2018]2ex 四处游走寻找关键代码 int __fastcall sub_400430(int a1, unsigned int a2, int a3) {unsigned int v3; // $v0int v4; // $v0int v5; // $v0int v6; // $v0unsigned int i; // [sp8h] [8h]unsigned int v9; // [sp8h] [8h]int v10; // [spCh] [Ch]v10 0;for…...

科技资讯|AirPods Pro基于定位控制的自适应音频功能
在接受 TechCrunch 媒体采访时,苹果高管 Ron Huang 和 Eric Treski 谈到了关于 AirPods Pro 自适应音频(Adaptive Audio)功能的轶事,曾考虑基于 GPS 信号来控制自适应音频级别。 Treski 表示在探索自适应音频功能初期࿰…...

《Jetpack Compose从入门到实战》第九章 Accompanist 与第三方组件库
目录 AccompanistSystemUiControllerPagerSwipeRefreshFlow LayoutInsets LottieCoilAsyncImageSubcomposeAsyncImageAsyncImagePainter Accompanist 最新可用版本accompanist官方文档 SystemUiController 依赖:implementation “com.google.accompanist:accompa…...
Centos7 docker 容器内root身份应用自启动 /usr/sbin/init 问题
Centos7 docker 容器内root身份应用自启动 & /usr/sbin/init 问题 环境:我在一个 docker 容器内手动安装了 mysql、nginx、autotestsystem(自己的服务); mysql 和 nginx 都做了服务脚本:mysqld.service、nginx.se…...
STL学习笔记之容器
首先我们要学习的是容器 第一个是容器的初始化(构造方式)有三种方式 分别是 第一种 int arr[]{1,2,3} vector<int> v1(arr,arr3) 即容器存放的种类和从另外一个数组去拷贝一段数据。 第二种 vector<int> v2(3,10); 第一个3是指存放…...
Java基础---第十二篇
系列文章目录 文章目录 系列文章目录一、获取一个类Class对象的方式有哪些?二、ArrayList 和 LinkedList 的区别有哪些?三、用过 ArrayList 吗?说一下它有什么特点?一、获取一个类Class对象的方式有哪些? 搞清楚类对象和实例对象,但都是对象。 第一种:通过类对象的 get…...

iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘
美国西海岸的夏天,再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至,这不仅是开发者的盛宴,更是全球数亿苹果用户翘首以盼的科技春晚。今年,苹果依旧为我们带来了全家桶式的系统更新,包括 iOS 26、iPadOS 26…...
macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用
文章目录 问题现象问题原因解决办法 问题现象 macOS启动台(Launchpad)多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显,都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放
简介 前面两期文章我们介绍了I2S的读取和写入,一个是通过INMP441麦克风模块采集音频,一个是通过PCM5102A模块播放音频,那如果我们将两者结合起来,将麦克风采集到的音频通过PCM5102A播放,是不是就可以做一个扩音器了呢…...
Spring Boot面试题精选汇总
🤟致敬读者 🟩感谢阅读🟦笑口常开🟪生日快乐⬛早点睡觉 📘博主相关 🟧博主信息🟨博客首页🟫专栏推荐🟥活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...
css的定位(position)详解:相对定位 绝对定位 固定定位
在 CSS 中,元素的定位通过 position 属性控制,共有 5 种定位模式:static(静态定位)、relative(相对定位)、absolute(绝对定位)、fixed(固定定位)和…...
Python 包管理器 uv 介绍
Python 包管理器 uv 全面介绍 uv 是由 Astral(热门工具 Ruff 的开发者)推出的下一代高性能 Python 包管理器和构建工具,用 Rust 编写。它旨在解决传统工具(如 pip、virtualenv、pip-tools)的性能瓶颈,同时…...
NPOI Excel用OLE对象的形式插入文件附件以及插入图片
static void Main(string[] args) {XlsWithObjData();Console.WriteLine("输出完成"); }static void XlsWithObjData() {// 创建工作簿和单元格,只有HSSFWorkbook,XSSFWorkbook不可以HSSFWorkbook workbook new HSSFWorkbook();HSSFSheet sheet (HSSFSheet)workboo…...

【Post-process】【VBA】ETABS VBA FrameObj.GetNameList and write to EXCEL
ETABS API实战:导出框架元素数据到Excel 在结构工程师的日常工作中,经常需要从ETABS模型中提取框架元素信息进行后续分析。手动复制粘贴不仅耗时,还容易出错。今天我们来用简单的VBA代码实现自动化导出。 🎯 我们要实现什么? 一键点击,就能将ETABS中所有框架元素的基…...
Spring Boot + MyBatis 集成支付宝支付流程
Spring Boot MyBatis 集成支付宝支付流程 核心流程 商户系统生成订单调用支付宝创建预支付订单用户跳转支付宝完成支付支付宝异步通知支付结果商户处理支付结果更新订单状态支付宝同步跳转回商户页面 代码实现示例(电脑网站支付) 1. 添加依赖 <!…...

算术操作符与类型转换:从基础到精通
目录 前言:从基础到实践——探索运算符与类型转换的奥秘 算术操作符超级详解 算术操作符:、-、*、/、% 赋值操作符:和复合赋值 单⽬操作符:、--、、- 前言:从基础到实践——探索运算符与类型转换的奥秘 在先前的文…...