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

算法沉淀——哈希算法(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/

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

示例 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 ,判断数组中是否存在两个 不同的索引 ij ,满足 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.lryc.cn/news/300975.html

相关文章:

  • 深入理解Redis哨兵原理
  • MySQL-存储过程(PROCEDURE)
  • linux系统监控工具prometheus的安装以及监控mysql
  • 初识tensorflow程序设计模式
  • 【QT+QGIS跨平台编译】之三十八:【GDAL+Qt跨平台编译】(一套代码、一套框架,跨平台编译)
  • 黑马鸿蒙教程学习1:Helloworld
  • 蓝桥杯每日一题------背包问题(四)
  • OpenAI发布Sora技术报告深度解读!真的太强了!
  • AJAX——接口文档
  • leetcode hot100不同路径
  • 【前端工程化面试题目】webpack 的热更新原理
  • 不花一分钱,在 Mac 上跑 Windows(M1/M2 版)
  • Attempt to call an undefined function glutInit
  • AB测试最小样本量
  • 在Spring中事务失效的场景
  • Rust 学习笔记 - 变量声明与使用
  • windows 下跑起大模型(llama)操作笔记
  • 人工智能专题:基础设施行业智能化的基础设施,自智网络双价值分析
  • docker 编译安装redis脚本
  • 鸿蒙开发系列教程(二十三)--List 列表操作(2)
  • C#根据权重抽取随机数
  • SORA:OpenAI最新文本驱动视频生成大模型技术报告解读
  • 阿里云第七代云服务器ECS计算c7、通用g7和内存r7配置如何选择?
  • 视觉slam十四讲学习笔记(六)视觉里程计 1
  • PyTorch-线性回归
  • C++数据结构与算法——栈与队列
  • 掌上新闻随心播控,HarmonyOS SDK助力新浪新闻打造精致易用的资讯服务新体验
  • 2024年危险化学品经营单位主要负责人证模拟考试题库及危险化学品经营单位主要负责人理论考试试题
  • C/C++如何把指针所指向的指针设为空指针?
  • 第三节:基于 InternLM 和 LangChain 搭建你的知识库(课程笔记)