「代码随想录算法训练营」第五天 | 哈希表 part1
242. 有效的字母异位词
题目链接:https://leetcode.cn/problems/valid-anagram/
题目难度:简单
文章讲解:https://programmercarl.com/0242.有效的字母异位词.html
视频讲解: https://www.bilibili.com/video/BV1YG411p7BA
题目状态:一次过,哈哈哈
个人思路:
之前在《剑指offer》中做过这个题目,思路就是直接创建两个26位的数组,分别存放两个字符串中出现的小写字母的个数,若最后这两个数组相等,则表示这两个字符串互为字母异位词。
实现代码:
class Solution {
public:
bool isAnagram(string s, string t) {
int sLen = s.size();
int tLen = t.size();
if(sLen != tLen) return false;
vector<int> sCount(26);
vector<int> tCount(26);
for(int i = 0; i < sLen; ++i) {
sCount[s[i] - 'a']++;
}
for(int i = 0; i < tLen; ++i) {
tCount[t[i] - 'a']++;
}
if(sCount != tCount) return false;
return true;
}
};
349. 两个数组的交集
题目链接:https://leetcode.cn/problems/intersection-of-two-arrays/
题目难度:简单
文章讲解:https://programmercarl.com/0349.两个数组的交集.html
视频讲解: https://www.bilibili.com/video/BV1ba411S7wu
题目状态:纠错后通过
个人思路:
- 创建两个
unordered_map<int, int>
类型的表分别存放两个数组中出现的数字和个数; - 创建一个
vector<int>
类型的数组res
用来存放交集; - 遍历第一个
map
,若在第二个map
中找到其键等于第一个map
中的键,将其添加到res
中; - 遍历完成后返回
res
。
实现代码:
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
vector<int> res;
unordered_map<int, int> One;
unordered_map<int, int> Two;
for(auto &num : nums1) {
One[num]++;
}
for(auto &num : nums2) {
Two[num]++;
}
for(auto &num: One) {
if(Two.find(num.first) != Two.end()) {
res.push_back(num.first);
}
}
return res;
}
};
看了代码随想录中的思路,可以用unordered_set
来实现,思路大致类似,但是写的比我好多了,突然发现我代码中的map
用的比较多余,而且不需要将两个数组都存入map
中,代码如下:
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> result_set; // 存放结果,之所以用set是为了给结果集去重
unordered_set<int> nums_set(nums1.begin(), nums1.end());
for (int num : nums2) {
// 发现nums2的元素 在nums_set里又出现过
if (nums_set.find(num) != nums_set.end()) {
result_set.insert(num);
}
}
return vector<int>(result_set.begin(), result_set.end());
}
};
202. 快乐数
题目链接:https://leetcode.cn/problems/happy-number/
题目难度:简单
文章讲解:https://programmercarl.com/0202.快乐数.html
题目状态:没有思路😭
思路:
通过while(1)
循环,反复计算每个位置上数的平方和,直到平方和为1
时结束,其中有一些细节:
定义一个unordered_set
用来存放每次计算出的平方和的结果,若在遍历中出现了之前存过的数,则表示会陷入无限循环,应该立即返回false
。
实现代码:
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<int> set;
while(1) {
int sum = getSum(n);
if(sum == 1) {
return true;
}
if(set.find(sum) != set.end()) {
return false;
} else {
set.insert(sum);
}
n = sum;
}
}
};
1. 两数之和
题目链接:https://leetcode.cn/problems/two-sum/
题目难度:简单
文章讲解:https://programmercarl.com/0001.两数之和.html
视频讲解:https://www.bilibili.com/video/BV1aT41177mK
题目状态:有人相爱,有人夜里开车看海,有人 leetcode 第一题都做不出来……
思路:
遍历数组nums
,并将其存入到一个unordered_map
类型中,其中键为数组数值,值为该数值的下标,在遍历的同时要执行下列操作:
- 判断
target - nums[i]
的值是否存在在unordered_map
中。若存在,则表示这两个数值之和就等于target
,返回这两个数值的下标即可; - 若不存在,则将
nums[i]
的值和下标存入到unordered_map
中。
实现代码:
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 {};
}
};