day06
242.有效的字母异位词349. 两个数组的交集202. 快乐数1. 两数之和
哈希表能解决什么问题呢？一般哈希表都是用来快速判断一个元素是否出现集合里。
242.有效的字母异位词
题目链接 解题思路： 题目的意思就是 判断两个字符串是否由相同字母组成。 字符a到字符z的ASCII是26个连续的数值，所以字符a映射为下标0，相应的字符z映射为下标25。 再遍历 字符串s的时候，只需要将 s[i] - ‘a’ 所在的元素做+1 操作即可，并不需要记住字符a的ASCII，只要求出一个相对数值就可以了。 这样就将字符串s中字符出现的次数，统计出来了。 同样在遍历字符串t的时候，对t中出现的字符映射哈希表索引上的数值再做-1的操作。 那么最后检查一下，record数组如果有的元素不为零0，说明字符串s和t一定是谁多了字符或者谁少了字符，return false。 最后如果record数组所有元素都为零0，说明字符串s和t是字母异位词，return true。
代码如下：
class Solution {
public:
bool isAnagram(string s, string t) {
int record[26] = {0};
for(int i = 0; i < s.size();i++){
record[s[i] - 'a']++;
}
for(int j = 0; j < t.size();j++){
record[t[j] - 'a']--;
}
for(int i = 0; i< 26; i++){
if(record[i] != 0){
return false;
}
}
return true;
}
};
349. 两个数组的交集
题目链接 解题思路：根据题目描述，需要进行去重，就想到了使用unordered_set 代码如下：
class Solution {
public:
vector
unordered_set
unordered_set
for(int num :nums2){
if(nums_set.find(num) != nums_set.end()){
result_set.insert(num);
}
}
return vector
}
};
202. 快乐数
题目链接 解题思路： 快速判断一个元素是否出现集合里的时候，就要考虑哈希法了。 题目中说了会无限循环，那么也就是说求和的过程中，sum会重复出现，判断sum是否重复出现就可以使用unordered_set。
class Solution {
public:
// 取数值各个位上的单数之和
int getSum(int n) {
int sum = 0;
while (n) {
sum += (n % 10) * (n % 10);
n /= 10;
}
return sum;
}
bool isHappy(int n) {
unordered_set
while(1) {
int sum = getSum(n);
if (sum == 1) {
return true;
}
// 如果这个sum曾经出现过，说明已经陷入了无限循环了，立刻return false
if (set.find(sum) != set.end()) {
return false;
} else {
set.insert(sum);
}
n = sum;
}
}
};
1. 两数之和
题目链接 解题思路： 这道题需要存放两个变量。需要使用 key value结构来存放，key来存元素，value来存下标，那么使用map正合适。 代码如下：
class Solution {
public:
vector
unordered_map
for(int i = 0; i < nums.size(); i++) {
// 遍历当前元素，并在map中寻找是否有匹配的key
auto iter = map.find(target - nums[i]);
if(iter != map.end()) {
return {iter->second, i};
}
// 如果没找到匹配对，就把访问过的元素和下标加入到map中
map.insert(pair
}
return {};
}
};
相关阅读
发表评论