leetcode|【leetcode刷题】哈希表-第1篇哈希表|C++|最小覆盖子串|重复

文章目录

第一题：字母异位词分组
第二题：有效的数独
第三题：最小覆盖子串
第四题：只出现一次的数字
第五题：快乐数
第六题：计数质数
第七题：存在重复元素
第八题：存在重复元素II
第九题：有效的字母异位词
第十题：H指数

第一题：字母异位词分组

题目：

文章图片

解题思路：使用排序的string作为key，未排序的string作为value

class Solution { public: vector> groupAnagrams(vector>& strs) { unordered_map, vector>> mp; for (auto str: strs) { string key = str; sort(key.begin(), key.end()); mp[key].push_back(str); } vector> ans; for (auto it = mp.begin(); it != mp.end(); ++it) { ans.push_back(it->second); } return ans; } };

第二题：有效的数独

题目：

文章图片

题目解析：定义3*9个哈希表，只要其中一个哈希表的个数大于1，就返回false。

class Solution { public: bool isValidSudoku(vector>& board) { unordered_maprow[9], column[9], box[9]; //定义3*9个哈希表 for (int i = 0; i < 9; i++) for (int j = 0; j < 9; j++) if (board[i][j] != '.' && (row[i][board[i][j]]++ || column[j][board[i][j]]++ || box[i / 3 * 3 + j / 3][board[i][j]]++))//超过一次退出 return false; return true; } };

第三题：最小覆盖子串

题目：

文章图片

解题思路：

需要注意字符个数也要包含。

然后创建两个哈希表，一个哈希表保留t中的元素，另一个哈希表保留s中包含t的元素。其中每个元素都满足s>=t，则表示包含，也就是下面代码中的check。

l表示所说，r表示扩展。ansL和ansR表示最终的结果。

class Solution { public: unordered_map mapT, mapS; bool check() { for (const auto &t: mapT) { if (mapS[t.first] < t.second) { return false; } } return true; }string minWindow(string s, string t) { for (const auto &c: t) { ++mapT[c]; }int l = 0, r = -1; int len = INT_MAX, ansL = -1, ansR = -1; while (r < int(s.size())) { if (mapT.find(s[++r]) != mapT.end()) { ++mapS[s[r]]; }//扩张 while (check() && l <= r) {//收缩 if (r - l + 1 < len) { len = r - l + 1; ansL = l; } if (mapT.find(s[l]) != mapT.end()) { --mapS[s[l]]; } ++l; } }return ansL == -1 ? string() : s.substr(ansL, len); } };

第四题：只出现一次的数字

题目：

文章图片

解题思路：使用哈希表统计每个元素出现的次数。

class Solution { public: int singleNumber(vector& nums) { unordered_map myMap; for(auto num : nums) { myMap[num]++; } for(auto m : myMap) { if(m.second == 1)return m.first; } return 0; } };

第五题：快乐数

题目：

文章图片

【leetcode|【leetcode刷题】哈希表-第1篇】使用哈希表记录每一次求平均数的值，如果有重复的，则表示会无限循环。

class Solution { public: bool isHappy(int n) { if(n <= 0)return false; unordered_map myMap; //用来检验是否重复 myMap[n] = true; int tmp = 0; while(1) { while(n >= 10) { tmp += pow(n % 10, 2); n = n / 10; } tmp += pow(n, 2); //个位数 if(tmp == 1) return true; else if(myMap.find(tmp) == myMap.end()) //没找到 { myMap[tmp] = true; n = tmp; tmp = 0; } else return false; //找到相同的数字 } return false; } };

第六题：计数质数

题目

文章图片

质数：在大于 11 的自然数中，除了 11 和它本身以外不再有其他因数的自然数，也称为素数。

解题思路：厄拉多塞筛法。

文章图片

class Solution { public: int countPrimes(int n) { int count = 0; //初始默认所有数为质数 vector signs(n, true); for (int i = 2; i < n; i++) { if (signs[i]) { count++; for (int j = i + i; j < n; j += i) {//i的倍数是非质数 signs[j] = false; } } } return count; } };

第七题：存在重复元素

题目：

文章图片

解题思路：一个哈希表查找，这里使用unordered_set就可以了。

class Solution { public: bool containsDuplicate(vector& nums) { unordered_set mySet; for(auto num : nums) { if( mySet.find(num) == mySet.end() ) mySet.insert(num); else return true; } return false; } };

第八题：存在重复元素II

题目：

文章图片

解题思路：使用unordered_set保留k个元素，然后判断它有没有重复元素。

class Solution { public: bool containsNearbyDuplicate(vector& nums, int k) { unordered_set mySet; for(int i = 0; i < nums.size(); i++) { if(i <= k) { if(mySet.find(nums[i]) == mySet.end()) mySet.insert(nums[i]); else return true; } else { mySet.erase(nums[i - k - 1]); //删除前面的元素 if(mySet.find(nums[i]) == mySet.end()) mySet.insert(nums[i]); //后端插入 else return true; } } return false; } };

第九题：有效的字母异位词

题目：

文章图片

解题思路：创建两个哈希表，判断他们是否相等即可。（看了解答，还可以排序之后依次判断每个位数是否相等。）

class Solution { public: bool isAnagram(string s, string t) { unordered_map mapS, mapT; for(auto ss : s)mapS[ss]++; for(auto tt : t)mapT[tt]++; if(mapT == mapS) return true; return false; } };

第十题：H指数

题目：

文章图片

解题思路：先排序，然后从小到大依次判断。（或者从大到小排序）

class Solution { public: int hIndex(vector& citations) { sort(citations.begin(), citations.end()); int n = citations.size(); int ans = min(n, citations[n - 1]); for(int i = 0; i < citations.size(); i++) { if(ans <= citations[i])return ans; //剩余元素已经满足条件 else ans = min(ans, n - i - 1); //剩余元素，和当前最大可能的取值进行比较 } return ans; } };