「LeetCode Top100」之哈希篇
1. 两数之和
题目链接：https://leetcode.cn/problems/two-sum/description/?envType=study-plan-v2&envId=top-100-liked
解题状态：通过
标签：数组、哈希表
思路：
通过创建一个哈希表来保存数组中的元素，每当遍历一个元素时，若哈希表中不存在另一个与之相加为目标值的元素，就将元素插入到哈希表中。
代码：
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> num;
for(int i = 0; i < nums.size(); ++i) {
auto iter = num.find(target - nums[i]);
if(iter != num.end()) {
return {iter->second, i};
}
num[nums[i]] = i;
}
return {};
}
};
49. 字母异位词分组
题目链接：https://leetcode.cn/problems/group-anagrams/description/?envType=study-plan-v2&envId=top-100-liked
解题状态：个人思路无法实现，看题解通过！
标签：数组、哈希表、字符串、排序
思路一：
使用unordered_map。
由于异位词中的字母是相同的且个数也是相同的，首先将字符串中每个数组内部排序，获得唯一的排序，然后使用map来存储当前唯一排序对应的字符串，最后输出map中的字符串即可。
代码一：
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> mp;
for(string &str : strs) {
string key = str;
sort(key.begin(), key.end());
mp[key].emplace_back(str);
}
vector<vector<string>> res;
for(auto it = mp.begin(); it != mp.end(); ++it) {
res.emplace_back(it->second);
}
return res;
}
};
思路二：
使用哈希表，官方题解中将字符串中每个字母出现的次数使用字符串表示，作为哈希表的键。但是代码写的真是一言难尽，根本不想看。
代码二：
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
// 自定义对 array<int, 26> 类型的哈希函数
auto arrayHash = [fn = hash<int>{}] (const array<int, 26>& arr) -> size_t {
return accumulate(arr.begin(), arr.end(), 0u, [&](size_t acc, int num) {
return (acc << 1) ^ fn(num);
});
};
unordered_map<array<int, 26>, vector<string>, decltype(arrayHash)> mp(0, arrayHash);
for (string& str: strs) {
array<int, 26> counts{};
int length = str.length();
for (int i = 0; i < length; ++i) {
counts[str[i] - 'a'] ++;
}
mp[counts].emplace_back(str);
}
vector<vector<string>> ans;
for (auto it = mp.begin(); it != mp.end(); ++it) {
ans.emplace_back(it->second);
}
return ans;
}
};
128. 最长连续序列
题目链接：https://leetcode.cn/problems/longest-consecutive-sequence/description/?envType=study-plan-v2&envId=top-100-liked
解题状态：个人思路无法实现，看题解通过！
标签：并查集、数组、哈希表
思路：
使用哈希表来存储序列中的所有元素，然后遍历每个元素，先判断当前元素的前一个数值是否存在这个哈希表中，若不存在则表示当前元素是第一个连续元素，接着遍历是否包含下一个数值，最后返回最长的连续序列。
代码：
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
unordered_set<int> num_set;
for(auto &num : nums) num_set.insert(num);
int longStreak = 0;
for(auto &num : num_set) {
if(!num_set.count(num - 1)) {
int currentNum = num;
int currentStreak = 1;
while(num_set.count(currentNum + 1)) {
currentNum += 1;
currentStreak += 1;
}
longStreak = max(longStreak, currentStreak);
}
}
return longStreak;
}
};