1. Leetcode 242有效的字母异位词
（1）解析
Leetcode242
参考文章
（2）思路
采用哈希表映射的思路
（3）代码
class Solution {
public:
bool isAnagram(string s, string t) {
int maplist[26] = {0};
for(int i = 0; i < s.size(); ++i)
maplist[s[i]- 'a'] += 1;
for(int i = 0; i < t.size(); ++i)
--maplist[t[i] - 'a'];
for(int i = 0; i < 26; ++i)
{
if(maplist[i] != 0)
return false;
}
return true;
}
};
（4）总结
字母数量有限，考虑到用数组做哈希表
2. Leetcode 349两个数组的交集
（1）解析
Leetcode349
参考文章
（2）思路
这道题目没有限制数值的大小，就无法使用数组来做哈希表了，
如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费， 使用unordered_set 读写效率是最高的，并不需要对数据进行排序，可以对数据去重，所以选择unordered_set
（3）代码
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> res_set;
unordered_set<int> nums1_set(nums1.begin(), nums1.end());
for(int num : nums2)
{
if(nums1_set.find(num) != nums1_set.end())
res_set.insert(num);
}
vector<int> res_vec(res_set.begin(), res_set.end());
return res_vec;
}
};
（4）总结
数值是否有限来判断采用哪种形式的哈希表，unordered_set可以去重
3. Leetcode 202快乐数
（1）解析
Leetcode202
参考文章
（2）思路
无限循环，那么也就是说求和的过程中，sum会重复出现，这对解题很重要，当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法了，判断sum是否重复出现就可以使用unordered_set
（3）代码
class Solution {
public:
int getNum(int n)
{
int sum = 0;
while(n)
{
sum += (n%10) * (n%10);
n = n/10;
}
return sum;
}
bool isHappy(int n) {
int num = getNum(n);
unordered_set<int> numset;
while(1)
{
if(num == 1)
return true;
num = getNum(num);
if(numset.find(num) != numset.end())
return false;
numset.insert(num);
}
}
};
（4）总结
只有判断新生成的sum没有重复出现，才能insert到numset集合中
|