LeetCode刷题 -- 哈希表
目录
两数之和
题目解析
算法原理
法一：暴力枚举，固定第一个数，从第二个数开始遍历找两数之和为target,从固定的数往后遍历
法二：暴力枚举，固定第一个数，从第一个数遍历到固定的数
法三：从法二的基础上，加入一个哈希表，只要前面的数和固定的数相加不等于target就丢入哈希表中，相等就返回两个数的下标
法四：在法一的基础上，加入一个哈希表，先把所有的数丢入哈希表中，在判断固定的数和表中的数相加是否为target,但是要特判同一个数相加为target
比如[1,3,4,5] target = 8 固定的数是4,哈希表中的数也是4，这样要判断 nums[i] == x&&hash[nums[i]] != i ,x = target - nums[i]
代码
class Solution
{
public:
vector<int> twoSum(vector<int>& nums, int target)
{
// vector<int> ret;
// int n = nums.size();
// for(int i = 0;i < n;++i)
// {
// for(int j = i-1;j >= 0;j--)
// {
// if(nums[i] + nums[j] == target)
// {
// ret.push_back(i);
// ret.push_back(j);
// break;
// }
// }
// if(ret.size() == 2) break;
// }
// return ret;
unordered_map<int,int> hash;// 存储元素的值和下标
int n = nums.size();
for(int i = 0;i < n;++i)
{
int x = target - nums[i];
if(hash.count(x)) return {hash[x],i};// hash.count(x) 是在哈希表中找x
else hash[nums[i]] = i;
}
return {-1,-1};
}
};
面试题 01.02. 判定是否互为字符重排
题目解析
s1字符串重排后可以得到s2字符串
算法原理
法一：只用一个数组模拟哈希表，先把字符串1丢入哈希表中，再遍历字符串2，如果字符串2中存在字符串1中的字符，哈希表就减减，如果哈希中的值小于0则为假
法二：用两个数组模拟哈希表，先把字符串1中字符丢入哈希表中，再把字符串2丢入第二个哈希表中，再遍历26个字符判断对应字符是否存在
代码
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;
// int hash1[128] = {0}; // s1
// int hash2[128] = {0}; // s2
// for(int i = 0;i < s1.size();++i)
// hash1[s1[i]]++;
// for(int i = 0;i < s2.size();++i)
// hash2[s2[i]]++;
// for(int i = 97;i < 128;++i)
// {
// if(hash1[i] != hash2[i]) return false;
// }
// return true;
}
};
存在重复元素
题目解析
算法原理
这题和两数之和的解法是一样的
只需要从前往后遍历，把前面的数都加入哈希表中，固定到某个数时，诺某个数出现了第二次就返回true，否则返回false
代码
class Solution
{
public:
bool containsDuplicate(vector<int>& nums)
{
unordered_set<int> hash;
for(auto ch : nums)
{
if(hash.count(ch)) return true;
else hash.insert(ch);
}
return false;
}
};
存在重复元素II
题目解析
满足两个条件即可返回true,否则返回false
算法原理
只要注意一个细节即可，前面的数对可以被覆盖（hash[nums[i]] = i），因为找i - j <= k,保证下标离得近
代码
class Solution
{
public:
bool containsNearbyDuplicate(vector<int>& nums, int k)
{
unordered_map<int,int> hash;// nums[i] i
int n = nums.size();
for(int i = 0;i < n;++i)
{
if(hash.count(nums[i]))
{
if(i - hash[nums[i]] <= k)
return true;
}
hash[nums[i]] = i;
}
return false;
}
};
字母异位词分组
题目解析
把字符串按ASCII码排序后的一样的分为一组
返回这样的二维数组
算法原理
- 先排序再分组(使用哈希表<string,string[]>)
第一个存字符串，第二个存字符串数组- 排好序的下标是一样的因此可以让tmp存下标（存排好序的下标），再把s加入到哈希表中（s保存的是排序前的字符串）
- 最后把结果给取出来
代码
class Solution
{
public:
vector<vector<string>> groupAnagrams(vector<string>& strs)
{
unordered_map<string,vector<string>> hash;
// 1. 把各个字符串分组
for(auto& s : strs)
{
string tmp = s;
sort(tmp.begin(),tmp.end());
hash[tmp].push_back(s);
}
// 2. 把结果取出来
vector<vector<string>> ret;
for(auto& [x,y] : hash)
{
// y -> vector<string>
// ret的每一行也是vector<string>
ret.push_back(y);
}
return ret;
}
};
原文地址：https://blog.csdn.net/2301_79722622/article/details/144239352
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！