算法沉淀——哈希算法（leetcode真题剖析）

在这里插入图片描述

算法沉淀——哈希算法

  • 01.两数之和
  • 02.判定是否互为字符重排
  • 03.存在重复元素
  • 04.存在重复元素 II
  • 05.字母异位词分组

哈希算法（Hash Algorithm）是一种将任意长度的输入（也称为消息）映射为固定长度的输出的算法。这个输出通常称为哈希值或摘要。哈希算法的主要目的是快速、高效地检索数据，因为哈希值可以用作数据的唯一标识。

哈希算法的特点包括：

  1. 固定输出长度： 无论输入的数据大小如何，哈希算法都会生成固定长度的哈希值。
  2. 快速计算： 对于给定的输入，哈希算法应该迅速生成相应的哈希值。
  3. 不可逆性： 从哈希值不能逆向推导出原始输入的内容。即使输入的数据发生微小变化，生成的哈希值也应该是大不相同的。
  4. 雪崩效应： 输入数据的微小变化应该导致输出哈希值的巨大变化，以确保输入数据的任何改变都能产生不同的哈希值。

在算法题中，哈希算法有许多实际运用。以下是一些常见的应用场景：

  1. 查找和检索： 使用哈希表（HashMap）来快速查找元素。通过将元素的键映射到哈希表中的索引，可以在常量时间内执行查找操作。
  2. 去重： 利用哈希集合（HashSet）来检测和删除重复元素。通过将元素的哈希值映射到集合中，可以轻松检测是否已经存在相同的元素。
  3. 缓存： 使用哈希表来实现缓存，以快速检索先前计算的结果。这种方法被称为缓存哈希。
  4. 字符串匹配： 使用哈希算法来加速字符串匹配过程。例如，Rabin-Karp字符串匹配算法使用哈希值来比较字符串，以快速检测是否匹配。
  5. 数据校验： 哈希算法用于验证数据的完整性。通过生成数据的哈希值并将其与已知的哈希值进行比较，可以确保数据在传输或存储过程中没有被篡改。
  6. 分布式系统： 在分布式系统中，哈希算法被用于负载均衡和数据分片。通过将资源或数据的标识哈希到一组节点上，可以实现均匀分布和高效的访问。
  7. 密码学： 在密码学中，哈希算法用于生成密码的摘要，以便安全地存储密码或验证用户身份。
  8. 图算法： 在图算法中，哈希算法可用于快速判断两个图是否相同或是否存在同构关系。

01.两数之和

题目链接：https://leetcode.cn/problems/two-sum/

给定一个整数数组 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
  • 只会存在一个有效答案

**进阶：**你可以想出一个时间复杂度小于 O(n2) 的算法吗？

思路

如果我们在事先将「数组内的元素」和「下标」绑定在一起存入「哈希表」中，然后直接在哈希表中查找每一个元素的 target - nums[i]，就能快速地找到「目标和的下标」。这里有一个小技巧，我们可以不用将元素全部放入到哈希表之后再来二次遍历（因为要处理元素相同的情况）。而是在将元素放入到哈希表中的「同时」，直接来检查表中是否已经存在当前元素所对应的目标元素（即 target - nums[i]）。如果它存在，那么我们已经找到了对应解，并立即将其返回。无需将元素全部放入哈希表中，提高效率。由于哈希表中查找元素的时间复杂度是 O(1)，遍历一遍数组的时间复杂度为 O(N)，因此可以将时间复杂度降到 O(N)。这是一个典型的「用空间换时间」的方式。

代码

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {// 哈希表，用于存储元素值及其对应的索引unordered_map<int, int> hash;int n = nums.size();for(int i = 0; i < n; ++i) {int x = target - nums[i]; // 计算目标值与当前元素的差值if(hash.count(x)) {// 如果差值在哈希表中存在，说明找到了两个数的和等于目标值return {hash[x], i};}hash[nums[i]] = i; // 将当前元素值及其索引存入哈希表}// 如果未找到符合条件的两个数，返回 {-1, -1}return {-1, -1};}
};

02.判定是否互为字符重排

题目链接：https://leetcode.cn/problems/check-permutation-lcci/

给定两个由小写字母组成的字符串 s1 和 s2，请编写一个程序，确定其中一个字符串的字符重新排列后，能否变成另一个字符串。

示例 1：

输入: s1 = "abc", s2 = "bca"
输出: true

示例 2：

输入: s1 = "abc", s2 = "bad"
输出: false

说明：

  • 0 <= len(s1) <= 100
  • 0 <= len(s2) <= 100

思路

这里使用哈希的思想，首先我们可以将两个字符串分别建立哈希，然后再进行对比，但这样时间和空间复杂度都很高，所以我们第一次优化使用一个哈希遍历完第一个字符串，再将第二个字符串进行遍历，每次减计数前先判断是否计数已经为0，如果已经为0，说明不匹配，直接返回false，这里要提一点，因为这里是26个小写字母，所以我们可以直接使用数组来进一步优化，其次，字符串如果长度不相等我们可以在最开始就判断为false

代码

class Solution {
public:bool CheckPermutation(string s1, string s2) {// 如果两个字符串长度不相等，直接返回 falseif(s1.size() != s2.size()) return false;int hash[26] = {0}; // 用于统计每个字符在 s1 中的出现次数// 统计 s1 中每个字符的出现次数for(char& c : s1) {hash[c - 'a']++;}// 遍历 s2 中的字符for(char& c : s2) {// 如果字符 c 在 s1 中不存在或出现次数已经用尽，返回 falseif(hash[c - 'a'] == 0) {return false;}hash[c - 'a']--; // 减少字符 c 在 s1 中的出现次数}// 如果遍历完 s2 后每个字符在 s1 中的出现次数都匹配，返回 truereturn true;}
};

03.存在重复元素

题目链接：https://leetcode.cn/problems/contains-duplicate/

给你一个整数数组 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

思路

这里我们使用哈希中的set容器就可以很好的解决这个问题，我们将数组中的数一个一个插入set，再插入之前先统计该数是否已经存在，存在就返回true，全部插入完毕，说明不存在重复元素。

代码

class Solution {
public:bool containsDuplicate(vector<int>& nums) {unordered_set<int> hash; // 用于存储已经遍历过的元素// 遍历数组中的每个元素for(int& i : nums) {// 如果当前元素已经在 hash 中存在，说明数组包含重复元素，返回 trueif(hash.count(i)) {return true;}// 将当前元素插入到 hash 中hash.insert(i);}// 如果遍历完数组都没有发现重复元素，返回 falsereturn false;}
};

04.存在重复元素 II

题目链接：https://leetcode.cn/problems/contains-duplicate-ii/

给你一个整数数组 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:bool containsNearbyDuplicate(vector<int>& nums, int k) {unordered_map<int, int> hash; // 用于存储元素及其最近一次出现的索引int n = nums.size();// 遍历数组中的每个元素for (int i = 0; i < n; ++i) {// 如果当前元素已经在 hash 中存在if (hash.count(nums[i])) {// 检查当前元素的索引与最近一次出现的索引之差是否不超过 kif (i - hash[nums[i]] <= k) {return true;}}// 更新当前元素的最近一次出现的索引hash[nums[i]] = i;}// 遍历完数组都没有发现符合条件的重复元素，返回 falsereturn false;}
};

05.字母异位词分组

题目链接：https://leetcode.cn/problems/group-anagrams/

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 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] 仅包含小写字母

思路

这里使用哈希的写法可以极大的减轻我们的代码量以及简单易懂，首先我们呢将每个字符串临时排序，将哈希的key值设为排序后的字符串，这样异位词就可以在相同的key值后不断插入，最后我们将hash中的value全部导出即可。

代码

class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {unordered_map<string, vector<string>> hash; // 用于存储排序后的字符串和对应的字母异位词组for (string& s : strs) {string tmp = s;sort(tmp.begin(), tmp.end()); // 将字符串排序，使得字母异位词变得相同hash[tmp].emplace_back(s); // 将排序后的字符串作为 key，将原始字符串添加到对应的字母异位词组中}vector<vector<string>> ret;// 遍历哈希表，将每个字母异位词组添加到结果中for (auto& [k, v] : hash) {ret.emplace_back(v);}return ret;}
};

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

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

相关文章

MATLAB 1：基础知识

MATLAB 1：基础知识

MATLAB中的数据类型主要包括数值类型、逻辑类型、字符串、函数句柄、结构体和单元数组类型。这六种基本的数据类型都是按照数组形式存储和操作的。 MATLAB中还有两种用于高级交叉编程的数据类型&#xff0c;分别是用户自定义的面向对象的用户类类型和Java类类型。 1.1.1数值类…
阅读更多...
SpringBoot 接入讯飞星火大模型实现对话

SpringBoot 接入讯飞星火大模型实现对话

申请地址 https://xinghuo.xfyun.cn/sparkapi?scrprice 免费申请200万Token 开发文档 https://www.xfyun.cn/doc/spark/Web.html#_1-接口说明 页面最下面有相关demo可以参考 介绍 接口是以套接字的形式分段返回&#xff0c;而且非http请求&#xff0c;比较繁琐&#xff0c;官…
阅读更多...
【Linux】yum软件包管理器

【Linux】yum软件包管理器

目录 Linux 软件包管理器 yum 什么是软件包 Linux安装软件 查看软件包 关于rzsz Linux卸载软件 查看yum源 扩展yum源下载 Linux开发工具 vim编辑器 上述vim三种模式之间的切换总结&#xff1a; 命令模式下&#xff0c;一些命令&#xff1a; vim配置 Linux 软件包管理…
阅读更多...
微服务—ES数据同步

微服务—ES数据同步

目录 数据同步 问题分析 方案1. 同步调用 方案2. 异步通知 方案3. 监听binlog​编辑 各方案对比 案例——利用MQ实现数据同步 步骤1. 导入hotel-admin项目 步骤2. 声明交换机、队列 步骤3. 发送MQ消息 步骤4. 接收MQ消息 步骤5. 测试同步功能 数据同步 elasticsea…
阅读更多...
统一数据格式返回，统一异常处理

统一数据格式返回，统一异常处理

目录 1.统一数据格式返回 2.统一异常处理 3.接口返回String类型问题 1.统一数据格式返回 添加ControllerAdvice注解实现ResponseBodyAdvice接口重写supports方法&#xff0c;beforeBodyWrite方法 /*** 统一数据格式返回的保底类 对于一些非对象的数据的再统一 即非对象的封…
阅读更多...
typescript中的Omit排除类型及Pick取想要的属性

typescript中的Omit排除类型及Pick取想要的属性

Omit 的使用:排除类型 type OmitUser {name: string,age: number,sex:string } type newOmit Omit<OmitUser, sex>// 定义一个对象并将其类型设置为 newOmit const example: newOmit {name: "John",age: 30 };console.log( Omit 的使用:排除类型 , example…
阅读更多...
AJAXJSON入门篇

AJAXJSON入门篇

AJAX&JSON 概念&#xff1a;AJAX(Asynchronous JavaScript And XML):异步的JavaScript和XML AJAX作用&#xff1a; 与服务器进行数据交换&#xff1a;通过AJAX可以给服务器发送请求&#xff0c;并获取服务器响应的数据 使用了AJAX和服务器进行通信&#xff0c;就可以使用H…
阅读更多...
lv15 平台总线驱动开发——ID匹配 3

lv15 平台总线驱动开发——ID匹配 3

一、ID匹配之框架代码 id匹配&#xff08;可想象成八字匹配&#xff09;&#xff1a;一个驱动可以对应多个设备 ------优先级次低&#xff08;上一章名称匹配只能1对1&#xff09; 注意事项&#xff1a; device模块中&#xff0c;id的name成员必须与struct platform_device中…
阅读更多...
MySQL主从环境，主库改端口后，从库如何操作？

MySQL主从环境，主库改端口后，从库如何操作？

主库&#xff1a;mysql-111 从库&#xff1a;mysql-112 主库由3306端口修改成3307后&#xff0c; 从库执行如下命令 mysql> stop slave; mysql> change master to master_port3307; mysql> CHANGE MASTER TO MASTER_HOST192.168.10.111,MASTER_USERbeifen,MASTER_PA…
阅读更多...
npm install 安装依赖如何加速

npm install 安装依赖如何加速

在使用npm安装依赖时&#xff0c;有几种方法可以加速这一过程&#xff0c;尤其是在面临网络限制或npm官方源速度慢的情况下。以下是一些常用的加速技巧&#xff1a; 1. 使用国内镜像源 国内有几个镜像源可以提供更快的下载速度&#xff0c;例如淘宝npm镜像。你可以通过以下命…
阅读更多...
如何用一根网线和51单片机做简单门禁[带破解器]

如何用一根网线和51单片机做简单门禁[带破解器]

仓库:https://github.com/MartinxMax/Simple_Door 支持原创是您给我的最大动力… 原理 -基础设备代码程序- -Arduino爆破器程序 or 51爆破器程序- 任意选一个都可以用… —Arduino带TFT屏幕——— —51带LCD1602——— 基础设备的最大密码长度是0x7F&#xff0c;因为有一位…
阅读更多...
Excel模板1：彩色甘特图

Excel模板1：彩色甘特图

Excel模板1&#xff1a;彩色甘特图 分享地址 当前效果&#xff1a;只需要填写进度&#xff0c; 其余效果都是自动完成的 。 阿里网盘永久分享&#xff1a;https://www.alipan.com/s/cXhq1PNJfdm ​省心。能用公式的绝不使用手动输入。 ​​ 这个区域以及标题可以手动输入…
阅读更多...
Python爬虫——解析库安装（1）

Python爬虫——解析库安装（1）

目录 1.lxml安装2.Beautiful Soup安装3.pyquery 的安装 我创建了一个社区&#xff0c;欢迎大家一起学习交流。社区名称&#xff1a;Spider学习交流 注&#xff1a;该系列教程已经默认用户安装了Pycharm和Anaconda&#xff0c;未安装的可以参考我之前的博客有将如何安装。同时默…
阅读更多...
机器学习之局部最优和全局最优

机器学习之局部最优和全局最优

(1)局部最优&#xff0c;就是在函数值空间的一个有限区域内寻找最小值;而全局最优&#xff0c;是在函数值空间整个区域寻找最小值问题。 (2)函数局部最小点是它的函数值小于或等于附近点的点&#xff0c;但是有可能大于较远距离的点。 (3)全局最小点是那种它的函数值小于或等于…
阅读更多...
二叉树-------前,中,后序遍历 + 前，中，后序查找+删除节点 （java详解）

二叉树-------前,中,后序遍历 + 前，中，后序查找+删除节点 （java详解）

目录 提要&#xff1a; 创建一个简单的二叉树&#xff1a; 二叉树的前中后序遍历&#xff1a; 二叉树的前序遍历&#xff1a; 二叉树的中序遍历&#xff1a; 二叉树的后续遍历&#xff1a; 小结&#xff1a; 二叉树的前中后续查找&#xff1a; 二叉树的前序查找&#…
阅读更多...
Python 数据可视化之山脊线图 Ridgeline Plots

Python 数据可视化之山脊线图 Ridgeline Plots

文章目录 一、前言二、主要内容三、总结 &#x1f349; CSDN 叶庭云&#xff1a;https://yetingyun.blog.csdn.net/ 一、前言 JoyPy 是一个基于 matplotlib pandas 的单功能 Python 包&#xff0c;它的唯一目的是绘制山脊线图 Joyplots&#xff08;也称为 Ridgeline Plots&…
阅读更多...
SpringMVC原理（设计原理+启动原理+工作原理）

SpringMVC原理（设计原理+启动原理+工作原理）

文章目录 前言正文一、设计原理1.1 servlet生命周期简述1.2 设计原理小结 二、启动原理2.1 AbstractHandlerMethodMapping 初始化 --RequestMapping注解解析2.2 DispatcherServlet 的初始化2.3 DispatcherServlet#initHandlerMappings(...) 初始化示例说明 三、工作原理 前言 …
阅读更多...
python - OSError：错误没有名为 [‘pytorch_model.bin‘

python - OSError：错误没有名为 [‘pytorch_model.bin‘

python - OSError&#xff1a;错误没有名为 [‘pytorch_model.bin’] 自己训练的模型存储好了以后 model MT5ForConditionalGeneration.from_pretrained(“ner/best”) 之前还可以跑 现在报错 错误没有名为 [‘pytorch_model.bin’] 还原了一下conda env 把四版变成三版了 …
阅读更多...
面试前的准备

面试前的准备

面试前的准备 Java程序员校招与社招的区别 校招和社招都是企业招聘形式的一种&#xff0c;只是面向的对象不同。校招 只允许在校生参加&#xff0c;社招理论上是任何人都能参加的(包括在校生)。 但是&#xff0c;无论是社招还是校招&#xff0c;它的难度都取决于你的水平高低。…
阅读更多...
Unity SRP 管线【第十讲：SRP/URP 图形API】

Unity SRP 管线【第十讲：SRP/URP 图形API】

Unity 封装的图形API 文章目录 Unity 封装的图形API一、 CommandBuffer 要执行的图形命令列表1. CommandBuffer 属性2. CommandBuffer 常用图形API&#xff08;方法&#xff09;(1)设置(2)获取临时纹理 GetTemporaryRT以及释放(3)设置纹理为渲染目标 SetRenderTarget(4)Command…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023