哈希表|242.有效的字母异位词 、349. 两个数组的交集、202. 快乐数、1. 两数之和
242.有效的字母异位词
自己审题思路
使用容器记录下字符串每个字母出现的次数
看完代码随想录题解后的收获
1.当遇到需要快速判断一个元素是否出现在集合里的时候，就首先想到哈希法；
2.数组、set、map都是哈希表；
3.容器内元素无序首先使用unordered_set、unordered_map，因为它们底层实现是哈希表，查询>和删减效率高(set、map、mutilset、mutilmap底层实现是红黑树)；当容器内元素要求有序使用>
set、map；当要求容器内元素可重复时，使用multiset、multimap。
使用map实现代码：
class Solution {
public:
bool isAnagram(string s, string t) {
unordered_map<char, int> ans;
for(auto& c : s) {
ans[c]++;
}
for(auto& c : t) {
ans[c]--;
}
for(auto& v : ans) {
if (v.second != 0) return false;
}
return true;
}
};
使用数组实现代码:
class Solution {
public:
bool isAnagram(string s, string t) {
int record[26] = {0};
for (int i = 0; i < s.size(); i++) {
// 并不需要记住字符a的ASCII，只要求出一个相对数值就可以了
record[s[i] - 'a']++;
}
for (int i = 0; i < t.size(); i++) {
record[t[i] - 'a']--;
}
for (int i = 0; i < 26; i++) {
if (record[i] != 0) {
// record数组如果有的元素不为零0，说明字符串s和t 一定是谁多了字符或者谁少了字符。
return false;
}
}
// record数组所有元素都为零0，说明字符串s和t是字母异位词
return true;
}
};
参考详解
349. 两个数组的交集
自己审题思路
审完题后不是很清晰，没明白具体要返回什么
看完代码随想录题解后的收获
1、明白是要返回两个数组重复的元素，并且不考虑顺序，并且输出结果是去重的。
2、如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费！
代码：
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());
}
};
把握什么时候使用数组，什么时候使用set
参考详解
202. 快乐数
自己审题思路
对取数值各个位上的单数操作不熟悉，卡了一会儿。
看完代码随想录题解后的收获
题目中说了会 无限循环，那么也就是说求和的过程中，sum会重复出现，这对解题很重要！
使用哈希法，来判断这个sum是否重复出现，如果重复了就是return false， 否则一直找到sum为1为止。
代码：
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;
}
// 如果这个sum曾经出现过，说明已经陷入了无限循环了，立刻return false
if (set.find(sum) != set.end()) {
return false;
} else {
set.insert(sum);
}
n = sum;
}
}
};
问题代码
#include <vector>
#include <string>
#include<iostream>
#include<set>
#include<unordered_set>
using namespace std;
class Solution {
public:
int getSum(int n) {
int sum = 0;
while(n) {
sum += (n % 10) * (n % 10);
n = n / 10;
}
return sum;
}
bool isHappy(int n) {
int sum = n;
unordered_set<int> ans;
while(1) {
int sum = getSum(sum); // 这里在代码运行过程中sum会被重置为0，不建议这么写，也不好理解
// sum = getSum(sum); // 这样写不会出错
if (sum == 1) {
return true;
}
if (ans.find(sum) != ans.end()) {
return false;
} else {
ans.insert(sum);
}
// n = sum;
}
}
};
上述错误，经过debug后发现：循环体外定义
int sum = n;后，在循环体内再定义int sum = getSum(sum),编译器会认为这个两个不同的变量（因为它们作用域不同），循环体内的sum每次循环都会被初始化为0（按理来说局部变量未初始化的值是未知的，值为0可能和编译器有关）。
参考详解
1. 两数之和
自己审题思路
返回的是数组的下标，计算需要用到数组中的值，考虑使用map
看完代码随想录题解后的收获
使用数组和set来做哈希法的局限。
数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。
set是一个集合，里面放的元素只能是一个key，而两数之和这道题目，不仅要判断y是否存在而且还要记录y的下标位置，因为要返回x 和 y的下标。所以set 也不能用。
此时就要选择另一种数据结构：map ，map是一种key value的存储结构，可以用key保存数值，用value再保存数值所在的下标。
代码：
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> map;
for (int i = 0; i < nums.size(); i++) {
auto iter = map.find(target - nums[i]);
if (iter != map.end()) {
return vector<int> {iter->second, i};
} else {
map.insert(pair<int, int>(nums[i], i));
//map[nums[i]] = i;
}
}
return vector<int> {};
}
};
参考详解
今日感悟：
1、遇到代码问题善用debug
2、哈希法的使用场景：当遇到需要快速判断一个元素是否出现在集合里的时候，就首先想到哈希法；
