维护网站费用怎么做会计凭证,公司推广做哪个网站吗,网站广告位图片更换没反应,wordpress 文章id排序算法沉淀——哈希算法 01.两数之和02.判定是否互为字符重排03.存在重复元素04.存在重复元素 II05.字母异位词分组 哈希算法#xff08;Hash Algorithm#xff09;是一种将任意长度的输入#xff08;也称为消息#xff09;映射为固定长度的输出的算法。这个输出通常称为哈希… 算法沉淀——哈希算法 01.两数之和02.判定是否互为字符重排03.存在重复元素04.存在重复元素 II05.字母异位词分组 哈希算法Hash Algorithm是一种将任意长度的输入也称为消息映射为固定长度的输出的算法。这个输出通常称为哈希值或摘要。哈希算法的主要目的是快速、高效地检索数据因为哈希值可以用作数据的唯一标识。 哈希算法的特点包括
固定输出长度 无论输入的数据大小如何哈希算法都会生成固定长度的哈希值。快速计算 对于给定的输入哈希算法应该迅速生成相应的哈希值。不可逆性 从哈希值不能逆向推导出原始输入的内容。即使输入的数据发生微小变化生成的哈希值也应该是大不相同的。雪崩效应 输入数据的微小变化应该导致输出哈希值的巨大变化以确保输入数据的任何改变都能产生不同的哈希值。
在算法题中哈希算法有许多实际运用。以下是一些常见的应用场景
查找和检索 使用哈希表HashMap来快速查找元素。通过将元素的键映射到哈希表中的索引可以在常量时间内执行查找操作。去重 利用哈希集合HashSet来检测和删除重复元素。通过将元素的哈希值映射到集合中可以轻松检测是否已经存在相同的元素。缓存 使用哈希表来实现缓存以快速检索先前计算的结果。这种方法被称为缓存哈希。字符串匹配 使用哈希算法来加速字符串匹配过程。例如Rabin-Karp字符串匹配算法使用哈希值来比较字符串以快速检测是否匹配。数据校验 哈希算法用于验证数据的完整性。通过生成数据的哈希值并将其与已知的哈希值进行比较可以确保数据在传输或存储过程中没有被篡改。分布式系统 在分布式系统中哈希算法被用于负载均衡和数据分片。通过将资源或数据的标识哈希到一组节点上可以实现均匀分布和高效的访问。密码学 在密码学中哈希算法用于生成密码的摘要以便安全地存储密码或验证用户身份。图算法 在图算法中哈希算法可用于快速判断两个图是否相同或是否存在同构关系。
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:vectorint twoSum(vectorint nums, int target) {// 哈希表用于存储元素值及其对应的索引unordered_mapint, 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(vectorint nums) {unordered_setint 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] 1090 k 105
思路
这道题相比于上一道题我们只需修改一下条件即可在遇到相同元素时相减判断若不符合我们将之前的下标覆盖若将整个数组插入完毕则不存在。
代码
class Solution {
public:bool containsNearbyDuplicate(vectorint nums, int k) {unordered_mapint, 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 1040 strs[i].length 100strs[i] 仅包含小写字母
思路
这里使用哈希的写法可以极大的减轻我们的代码量以及简单易懂首先我们呢将每个字符串临时排序将哈希的key值设为排序后的字符串这样异位词就可以在相同的key值后不断插入最后我们将hash中的value全部导出即可。
代码
class Solution {
public:vectorvectorstring groupAnagrams(vectorstring strs) {unordered_mapstring, vectorstring hash; // 用于存储排序后的字符串和对应的字母异位词组for (string s : strs) {string tmp s;sort(tmp.begin(), tmp.end()); // 将字符串排序使得字母异位词变得相同hash[tmp].emplace_back(s); // 将排序后的字符串作为 key将原始字符串添加到对应的字母异位词组中}vectorvectorstring ret;// 遍历哈希表将每个字母异位词组添加到结果中for (auto [k, v] : hash) {ret.emplace_back(v);}return ret;}
};
