模板建网站价格,织梦网站广告代码教程,南昌信息推广平台,未央网站建设【ps】本篇有 5 道 leetcode OJ。 一、算法简介 哈希表是一种存储数据的容器#xff0c;可以快速查找某个元素#xff0c;其查找的时间复杂度为 O(1)#xff0c;非常合适需要频繁查找某一个元素的场景。其具体用法为#xff1a;
直接使用底层为哈希表的 STL 容器。用数组… 【ps】本篇有 5 道 leetcode OJ。 一、算法简介 哈希表是一种存储数据的容器可以快速查找某个元素其查找的时间复杂度为 O(1)非常合适需要频繁查找某一个元素的场景。其具体用法为
直接使用底层为哈希表的 STL 容器。用数组模拟简易的哈希表例如利用数组统计字符串中字符的频次、整型的数据范围很小时映射某些值等。 二、相关例题
1两数之和
1. 两数之和 .1- 题目解析 不难想到暴力解法两层 for 循环将所有组合枚举一遍即可找到答案。 不过我们还可以用一个 unordered_map 来记录原始数组中每个元素的下标而要找到和为 target 的两个元素只需在遍历到原始数组中一个元素 x 时查询哈希表中是否有值为 target - x 的原始数组元素有则返回这两个元素作为最终结果。 .2- 代码编写
class Solution {
public:vectorint twoSum(vectorint nums, int target) {unordered_mapint,int hash;for(int i0;inums.size();i){int xtarget-nums[i];//有则返回结果if(hash.count(x))return {hash[x],i};//将当前元素统计入哈希表hash[nums[i]]i;}return {-1,-1};}
}; 2判定是否互为字符重排
面试题 01.02. 判定是否互为字符重排 .1- 题目解析 如果两个字符串 s1 和 s2 是互为字符重排的那么它们中的字符相应出现的频次是相同的我们可以用一个数组来模拟哈希表统计两个字符串中字符出现的频次。 .2- 代码编写
//写法1用两个哈希表分别统计后再比对
class Solution {
public:bool CheckPermutation(string s1, string s2) {if(s1.size()!s2.size())return false;int hash1[26]{0};int hash2[26]{0};for(auto ch:s1)hash1[ch-a];for(auto ch:s2){hash2[ch-a];}for(int i0;i26;i){if(hash1[i]!hash2[i])return false;}return true;}
};
//写法2用一个哈希表来统计和比对
class Solution {
public:bool CheckPermutation(string s1, string s2) {if(s1.size()!s2.size())return false;int hash[26]{0};for(auto ch:s1)hash[ch-a];for(auto ch:s2){hash[ch-a]--;if(hash[ch-a]0)return false;}return true;}
}; 3存在重复元素
217. 存在重复元素 .1- 题目解析 直接用一个哈希表统计数字出现的频次即可。 .2- 代码编写
class Solution {
public:bool containsDuplicate(vectorint nums) {unordered_mapint,int hash;for(auto x:nums){hash[x];if(hash[x]%20)return true;}return false;} 4存在重复元素 II
219. 存在重复元素 II .1- 题目解析 这道题相较于上一道哈希表的映射关系不再是 数字频次而应是 数字在原数组中的下标返回条件不再是数字出现的频次为 2而是相同两数的下标之差小于 k。 .2- 代码编写
class Solution {
public:bool containsNearbyDuplicate(vectorint nums, int k) {unordered_mapint,int hash;for(int i0;inums.size();i){if(hash.count(nums[i])){if(i-hash[nums[i]]k)return true;}hash[nums[i]]i;}return false;}
}; 5字母异位词分组
49. 字母异位词分组 .1- 题目解析 字母异位词之间字符出现的频次是相同的。我们可以对每一个词通过 ascii 码来进行排序将排序结果相同的放在一起即放在一个字符串数组中由此我们可以用一个哈希表来存储结果哈希表中的映射关系是 排序后的字符串同组的字母异位词。 .2- 代码编写
class Solution {
public:vectorvectorstring groupAnagrams(vectorstring strs) {//用哈希表对字母异位词分组unordered_mapstring,vectorstring hash;for(auto s:strs){string tmps;sort(tmp.begin(),tmp.end());hash[tmp].push_back(s);}//构建返回结果vectorvectorstring ret;for(auto[x,y]:hash)ret.push_back(y);return ret;}
};
