242.有效的字母异位词
虽然今天的主题是哈希表，但我第一个想到的做法其实是用sort，感觉这样更直观。
class Solution {
public:
bool isAnagram(string s, string t) {
if(s.length() != t.length())
return false;
sort(s.begin(), s.end());
sort(t.begin(), t.end());
for(int i=0; i<s.length(); i++){
if(s[i] != t[i]){
return false;
}
}
return true;
}
};
用了我最初想的比较直接的哈希表做法来做这道题，首先遍历了s，然后遍历t，遍历两个string的同时在哈希表里进行增减操作，如有增减异常就返回false。我以为这种方法比上面那种更耗费资源，结果并没有。这回是10 ms 7.3 MB，而第一种办法反而是用了16 ms 7.5 MB。
class Solution {
public:
bool isAnagram(string s, string t) {
if(s.length() != t.length())
return false;
unordered_map<char,int> umap;
for(int i=0; i<s.length();i++){
auto it = umap.find(s[i]);
if(it != umap.end()){
it->second = it->second + 1;
}
else{
umap.emplace(make_pair(s[i],1));
}
}
for(int i=0; i<t.length();i++){
auto it = umap.find(t[i]);
if(it != umap.end()){
it->second = it->second - 1;
if(it->second < 0)
return false;
}
else{
return false;
}
}
return true;
}
};
自己写完之后看了Carl的讲解，发现Carl原本根本就没有哈希表来做，哈哈。他是用了一个长度为26的数组来记录增减的，用这种方法来模拟哈希表。太聪明了。
349. 两个数组的交集
这道题还是比较轻松的就做出来了。需要注意的就是有的时候，hashmap的修改时会有笔误：本来应该是uset.insert(),但有的时候我会写成it.insert()。
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> uset;
vector<int> res;
for(int i=0; i<nums1.size(); i++){
auto it = uset.find(nums1[i]);
if(it == uset.end()){
uset.insert(nums1[i]);
}
}
for(int i=0; i<nums2.size(); i++){
auto it = uset.find(nums2[i]);
if(it != uset.end()){
res.push_back(nums2[i]);
uset.erase(it);
}
}
return res;
}
};
202. 快乐数
和俊淑想了半天，试着找到快乐数的规律。中途我已经不去思考了，去做了杯拿铁给她。还帮她回忆起了编程里的除和mod。最后我看了Carl在每日训练里的提示，写出来了一个比较基础的解法。
class Solution {
public:
bool isHappy(int n) {
unordered_set<int> uset;
bool found = false;
while(!found){
string num_in_str = to_string(n);
int sum = 0;
for(int i=0; i<num_in_str.length(); i++){
char ch = num_in_str[i];
int cur_num = ch - '0';
sum = sum + pow(cur_num,2);
}
if(sum == 1)
return true;
else{
auto it = uset.find(sum);
if(it != uset.end()){
found = true;
}
else{
uset.insert(sum);
n = sum;
}
}
}
return false;
}
};
看了Carl的解法，发现思路差不多，但是在数字的处理上更厉害一些，没进行int to string然后 string to int的转换。
while(n){
sum = sum + (n%10)*(n%10);
n = n/10;
}
1. 两数之和
马上就有思路做了，看来写代码还是有点进步的。但是一直报错，原来是因为我加入哈希表的应该是目前的数，而不是和target的差值。马虎了。
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> res;
unordered_map<int,int> umap;
for(int i=0; i<nums.size(); i++){
int need = target - nums[i];
auto it = umap.find(need);
if(it != umap.end()){
res.push_back(i);
res.push_back(it->second);
break;
}
else{
umap.emplace(make_pair(nums[i],i));
}
}
return res;
}
};
