怎么做淘课网站,韩国外贸网站,南通企业建站系统模板,专业定制房地产网站建设目录
哈希表总结
leetcode题目
一、两数之和
二、判定是否互为字符重排
三、存在重复元素
四、存在重复元素 II
五、字母异位词分组
六、在长度2N的数组中找出重复N次的元素
七、两个数组的交集
八、两个数组的交集 II
九、两句话中的不常见单词 哈希表总结 1.存储数…目录
哈希表总结
leetcode题目
一、两数之和
二、判定是否互为字符重排
三、存在重复元素
四、存在重复元素 II
五、字母异位词分组
六、在长度2N的数组中找出重复N次的元素
七、两个数组的交集
八、两个数组的交集 II
九、两句话中的不常见单词 哈希表总结 1.存储数据的容器 2.需要快速查找数据时用哈希表 3.当题目中给定的字符串或者数组只包含小写字母或数据范围是0~100/1000等等时可以用数组模拟哈希表 4.当数据范围是负数到正数时不建议用数组模拟哈希表因为还要加一个数转化之后进行映射建议直接使用STL容器 leetcode题目
一、两数之和
1. 两数之和 - 力扣LeetCodehttps://leetcode.cn/problems/two-sum/1.题目解析 给定数组与target, 返回和为target的两个元素下标 2.算法分析
解法一: 暴力枚举
策略一: 先固定一个数然后依次与该数之后的数相加
策略二: 先固定一个数然后依次与该数之前的数相加
解法二: 使用哈希表优化
暴力解法之所以慢以策略二为例, 是因为枚举到nums[i]时要在这个位置之前都遍历一下看哪个数字等于target-nums[i], 所以如果我们枚举到nums[i]时前面的数字都被扔进了哈希表中我们就可以以O(1)的时间复杂度找到结果~
注意如果是用哈希表暴力枚举策略一最好是倒着遍历~
3.算法代码
暴力枚举策略一:
class Solution {
public:vectorint twoSum(vectorint nums, int target) {for(int i 0; i nums.size(); i){for(int j i 1; j nums.size(); j){if(nums[i] nums[j] target)return {i, j}; }}return {-1, -1};}
};
暴力枚举策略二:
class Solution {
public:vectorint twoSum(vectorint nums, int target) {for(int i 1; i nums.size(); i){for(int j i - 1; j 0; j--){if(nums[i] nums[j] target)return {i, j}; }}return {-1, -1};}
};
哈希表优化策略一:
class Solution {
public:vectorint twoSum(vectorint nums, int target) {unordered_mapint, int hash; //nums[i], ifor(int i nums.size()-1; i 0; i--){int x target - nums[i];if(hash.count(x)) return {hash[x], i};hash[nums[i]] i;}return {-1, -1}; //照顾编译器}
};
哈希表优化策略二:
class Solution {
public:vectorint twoSum(vectorint nums, int target) {unordered_mapint, int hash; //nums[i], ifor(int i 0; i nums.size(); i){int x target - nums[i];if(hash.count(x)) return {hash[x], i};hash[nums[i]] i;}return {-1, -1}; //照顾编译器}
};
二、判定是否互为字符重排
面试题 01.02. 判定是否互为字符重排 - 力扣LeetCodehttps://leetcode.cn/problems/check-permutation-lcci/1.题目解析 给定两个字符串判断一个字符串是否能够通过重排变成另一个字符串 2.算法分析
如果s1能够重排形成s2, 那么s1每个字符出现的个数和s2对应字符出现的个数是相等的于是可以使用哈希表而题目中说字符串只有小写字母因此用数组模拟哈希表即可。所以解法就是用两个哈希表然后判断哈希表是否相等即可
优化1: 只使用一个哈希表统计s1中字符个数然后遍历第二个字符串把对应字符在哈希表中的个数-- 如果--之后是负数了返回false即可
优化2: 两个字符串的长度不相等直接返回false即可
3.算法代码
class Solution {
public:bool CheckPermutation(string s1, string s2){//优化if(s1.size() ! s2.size()) return false;int hash[26] {0};for(auto e : s1) hash[e - a];for(auto e : s2){hash[e - a]--;if(hash[e - a] 0)return false;}return true;}
};
三、存在重复元素
217. 存在重复元素 - 力扣LeetCodehttps://leetcode.cn/problems/contains-duplicate/1.题目解析 数组中存在重复元素返回true, 不存在重复元素返回false 2.算法分析
使用哈希表解决问题~
3.算法代码
unordered_map:
class Solution {
public:bool containsDuplicate(vectorint nums) {unordered_mapint, int hash;for(auto e : nums){hash[e];if(hash[e] 1) return true;}return false;}
};
unordered_set:
class Solution {
public:bool containsDuplicate(vectorint nums) {unordered_setint hash;for(auto e : nums){if(hash.count(e)) return true;elsehash.insert(e);}return false;}
};
四、存在重复元素 II
219. 存在重复元素 II - 力扣LeetCodehttps://leetcode.cn/problems/contains-duplicate-ii/1.题目解析 判断数组中是否存在两个相同的元素并且下标的绝对值小于等于k 2.算法分析
从前向后遍历数组同时将遍历过的元素和下标绑定扔进哈希表遍历的同时判断是否满足题意即可
小细节nums [1 0 2 1 3 1 4], k 2, 当遍历到第2个1时发现下标i-j3k, 不满足题意此时将1和下标3绑定扔进哈希表覆盖之前的 1, 0 是完全可以的, 因为题目求的是 i-j k, 因此i和j越近越好因此我们可以直接覆盖原先的值~
3.算法代码
class Solution {
public:bool containsNearbyDuplicate(vectorint nums, int k) {unordered_mapint, int hash; // nums[i], ifor(int i 0; i nums.size(); i){if(hash.count(nums[i]) i-hash[nums[i]] k)return true;hash[nums[i]] i;}return false;}
};
五、字母异位词分组
49. 字母异位词分组 - 力扣LeetCodehttps://leetcode.cn/problems/group-anagrams/description/1.题目解析 给一个字符串数组将所有的字母异位词放到一组返回一个二维数组 2.算法分析 1.判断两个字符串是否是字母异位词(可以用哈希表但是代码不好写我们选择直接排序, 排序结果一样那就互为字母异位词) 2.将相同的字母异位词分组 --- 借助哈希表 string, string[ ], 哈希表第一个位置存储排序后的字符串第二个存储一个字符串数组 3.算法代码
class Solution {
public:vectorvectorstring groupAnagrams(vectorstring strs) {unordered_mapstring, vectorstring hash;//1.将所有的字母异位词分组for(auto s : strs){string tmp s;sort(tmp.begin(), tmp.end());hash[tmp].push_back(s);}//2.提取结果vectorvectorstring ret;for(auto [x, y] : hash){ret.push_back(y);}return ret;}
};
六、在长度2N的数组中找出重复N次的元素
961. 在长度 2N 的数组中找出重复 N 次的元素 - 力扣LeetCodehttps://leetcode.cn/problems/n-repeated-element-in-size-2n-array/description/1.题目解析 我们在深剖一下题意本质就是只有1个数重复出现了其他数都只出现了一次 2.算法分析
思路一: 遍历数组将当前元素和出现次数丢进哈希表当某个数出现次数 n时返回该数
思路二: 遍历数组进循环先判断该数是否已经存在存在就直接返回不存在就将该数丢进哈希表
3.算法代码
思路一:
class Solution {
public: int repeatedNTimes(vectorint nums) { size_t n nums.size() / 2;unordered_mapint, int hash; // [x, count] for(auto e : nums) { hash[e]; if(hash[e] n) return e; } return -1;}
};
思路二:
class Solution {
public: int repeatedNTimes(vectorint nums) { unordered_mapint, int hash; // [x, count] for(auto e : nums) { if(hash[e] 1) // 只需要检查是否已经存在即重复了一次 return e; hash[e]; } return -1;}
};
七、两个数组的交集
349. 两个数组的交集 - 力扣LeetCodehttps://leetcode.cn/problems/intersection-of-two-arrays/submissions/
1.题目解析 返回两个数组的交集输出结果的每个元素要是唯一的 2.算法分析
将两个数组元素扔进两个 unordered_set 哈希表进行去重然后遍历其中一个哈希表看该哈希表中的元素在另一个哈希表中是否存在存在就插入到结果数组中
3.算法代码
class Solution {
public:vectorint intersection(vectorint nums1, vectorint nums2) {vectorint ret;unordered_setint hash1;unordered_setint hash2;for(auto e : nums1) //对nums1元素去重hash1.insert(e);for(auto e : nums2) //对nums2元素去重hash2.insert(e);for(auto e : hash1)if(hash2.count(e))ret.push_back(e);return ret;}
};
八、两个数组的交集 II
350. 两个数组的交集 II - 力扣LeetCodehttps://leetcode.cn/problems/intersection-of-two-arrays-ii/1.题目解析 返回两个数组的交集 (结果中可以有重复元素) 2.算法分析
定义一个哈希表 unordered_map遍历第一个数组将 数组元素和出现的个数绑定扔进哈希表, 然后遍历第二个数组元素在哈希表中出现就插入到结果数组中然后将该元素在哈希表中的个数--即可
3.算法代码
class Solution {
public:vectorint intersect(vectorint nums1, vectorint nums2) {unordered_mapint, int hash;for(auto e : nums1)hash[e];vectorint ret;for(auto e : nums2){if(hash[e]){ret.push_back(e);hash[e]--;}}return ret;}
};
九、两句话中的不常见单词
884. 两句话中的不常见单词 - 力扣LeetCodehttps://leetcode.cn/problems/uncommon-words-from-two-sentences/description/
1.题目解析 返回两句话中互相在另一句话中没有出现的所有单词 2.算法分析
可以将两个字符串合在一起提取出所有的单词同时扔进哈希表统计单词出现的次数然后遍历一遍哈希表出现次数为1的单词就是我们要的结果
3.算法代码
class Solution {
public:vectorstring uncommonFromSentences(string s1, string s2) {//1.将所有的单词提取出来vectorstring words;string tmp;string s s1 s2;unordered_mapstring, int hash;for(size_t i 0; i s.size(); i){if(s[i] ! i ! s.size())tmp s[i];else{words.push_back(tmp);hash[tmp];tmp.clear();}}//2.从哈希表中提取结果vectorstring ret;for(auto [x, y] : hash)if(y 1)ret.push_back(x);return ret;}
};
十、字符串中的第一个唯一字符
387. 字符串中的第一个唯一字符 - 力扣LeetCodehttps://leetcode.cn/problems/first-unique-character-in-a-string/
1.题目解析 找字符串中第一个只出现一次的字符 2.算法分析
数组模拟哈希表遍历字符串s统计出每个字符出现的次数然后再遍历一遍哈希表找出出现次数为1的字符返回下标
3.算法代码
class Solution {
public:int firstUniqChar(string s) {int hash[26] {0};for(auto e : s)hash[e-a];for(int i 0; i s.size(); i)if(hash[s[i]-a] 1)return i;return -1;}
};
