【LeetCode】哈希表精选5题
目录
1. 两数之和（简单）
创建一个哈希表，对于每一个nums[i]，我们首先查询哈希表中是否存在target - nums[i]，然后将nums[i]插入到哈希表中，即可保证不会让nums[i]和自己匹配。
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int n = nums.size();
unordered_map<int, int> hash; // key——nums[i] value——i
for (int i = 0; i < n; i++)
{
int x = target - nums[i];
if (hash.count(x))
return { hash[x],i };
hash[nums[i]] = i;
}
return { -1,-1 };
}
};2. 验证外星语词典（简单）
用数组模拟哈希表，hash[0]表示字母'a'在字母表中的顺序，hash[1]表示字母'b'在字母表中的顺序……
为了判断两个单词是否是按照字母表的顺序排序的，可以扫描两个单词中的字母找出第一个不相同的字母。哪个单词的第一个不相同的字母在字母表中的位置靠前，排序的时候它就排在前面。如果没有找到不相同的字母，那么短的单词在排序的时候应该排在前面。
class Solution {
public:
bool isAlienSorted(vector<string>& words, string order) {
// 初始化哈希表
for (int i = 0; i < order.size(); i++)
{
hash[order[i] - 'a'] = i;
}
// 判断相邻的两个单词是否按照字母表的顺序排序
for (int i = 0; i < words.size() - 1; i++)
{
if (!isSorted(words[i], words[i + 1]))
return false;
}
return true;
}
private:
bool isSorted(string& word1, string& word2)
{
int i = 0;
while (i < word1.size() && i < word2.size())
{
char ch1 = word1[i];
char ch2 = word2[i];
if (ch1 == ch2)
{
i++;
}
else
{
if (hash[ch1 - 'a'] < hash[ch2 - 'a'])
return true;
if (hash[ch1 - 'a'] > hash[ch2 - 'a'])
return false;
}
}
return i == word1.size();
}
int hash[26]; // 记录字母在字母表中的顺序
};3. 存在重复元素（简单）
出现至少两次就是数组中存在着重复的元素，因此我们可以无需统计元素出现的数目。仅需在遍历数组的过程中，检查当前元素是否在之前已经出现过即可。
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
unordered_set<int> hash;
for (auto& e : nums)
{
if (hash.count(e))
return true;
else
{
hash.insert(e);
}
}
return false;
}
};4. 存在重复元素 II（简单）
创建一个哈希表，对于每一个nums[i]，我们首先查询哈希表中是否存在nums[i]，并且i - hash[nums[i]] <= k，然后将nums[i]插入到哈希表中，即可保证不会让nums[i]和自己匹配。
class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
int n = nums.size();
unordered_map<int, int> hash; // key——nums[i] value——i
for (int i = 0; i < n; i++)
{
int x = nums[i];
if (hash.count(x) && i - hash[x] <= k)
return true;
hash[x] = i;
}
return false;
}
};5. 字母异位词分组（中等）
把一组字母异位词映射到同一个单词，由于互为字母异位词的单词的字母出现的次数分别相同，因此如果把单词中的字母排序就会得到相同的字符串。
创建一个哈希表，key为把单词字母排序得到的字符串，value为一组字母异位词。
例如，eat tea ate -> aet，创建哈希表，key——"aet"，value——{ "eat","tea","ate" }。
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> hash;
for (string& str: strs)
{
string s = str;
sort(s.begin(), s.end());
hash[s].push_back(str);
}
vector<vector<string>> ans;
for(auto& [x, y] : hash)
{
ans.push_back(y);
}
return ans;
}
};原文地址：https://blog.csdn.net/Qiuhan_909/article/details/135330115
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！