DAY5\Day6
1.熟悉哈希表的数据结构：数组、map和set，使用方法、使用场景
2.哈希表应用场景：解决给你一个元素，判断它在集合里是否出现过。
242.有效的字母异位词
本题用数组解决的。
class Solution {
public:
bool isAnagram(string s, string t) {
//通过ascii码表将26个字母映射到数组record
int record[26] = {0};
for(int i = 0; i < s.size(); i++){
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) return false;
}
return true;
}
};
有关类型转换，当char类型进行算术运算时，会发生如下转换：
在算术运算之前，char类型会被自动提升(promoted)为int类型
这种转换叫做"整型提升"(integral promotion)
所以两个char相减的结果直接就是int类型，不需要再进行类型转换了
349. 两个数组的交集
什么时候用set？1.数值很大；2.数值分布很散
若数值的大小上亿，数组无法解决且浪费空间，这种情况适合用set。
本题数组最大为1000，但是我们按照数值上亿的情况，也就是用set来做。
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> result_set;
unordered_set<int> nums_set(nums1.begin(), nums1.end());
// for(int num : nums2)
for(int i = 0; i < nums2.size(); i++)
{
int num = nums2[i];
if(nums_set.find(num) != nums_set.end()){
result_set.insert(num);
}
}
return vector<int>(result_set.begin(), result_set.end());
}
};
1.for(int num : nums2)的含义
遍历nums2中的数，并赋值给num
2.if(nums_set.find(num) != nums_set.end())的含义。
nums_set.end()是最后一个元素后面的位置，如果nums_set.find()没有找到num，就会返回nums_set.end()。
所以这个判断语句的意思是：if(nums_set中存在num)
3.return vector<int>(result_set.begin(), result_set.end()); 这里是一个强制类型转换吗
不是，是在调用 vector 的一个构造函数。这是 vector 类的一个特殊构造函数，它可以接收两个迭代器作为参数，然后创建一个新的 vector，包含这两个迭代器之间的所有元素。
这行代码做了以下事情：
创建一个新的 vector<int> 对象
使用 result_set 的开始迭代器（begin()）和结束迭代器（end()）
将 result_set 中的所有元素复制到这个新的 vector 中
202.快乐数
直接法：报错超时
class Solution {
public:
bool isHappy(int n) {
int res; //记录平方和
int tmp;
while(n > 3){
res = 0;
while(n){
tmp = n%10;
n /= 10;
res = res + tmp * tmp;
}
if(res == 1) return true;
n = res;
}
if(n == 1) return true;
return false;
}
};
题目描述：“也可能是 无限循环 但始终变不到 1”，直接法没有解决这个情况，所以发生了超时
那么如何判断发生了无限循环？
无限循环，那么也就是说求和的过程中，sum会重复出现。使用哈希法，来判断这个sum是否重复出现，如果重复了就是return false， 否则一直找到sum为1为止。
更正后的代码：
class Solution {
public:
bool isHappy(int n) {
int res; //记录平方和
int tmp;
unordered_set<int> set;
while(n > 3){
res = 0;
while(n){
tmp = n%10;
n /= 10;
res = res + tmp * tmp;
}
if(res == 1) return true;
if(set.find(res) != set.end()) return false;
else set.insert(res);
n = res;
}
if(n == 1) return true;
return false;
}
};
1. 两数之和
O(n^2)做法：
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int n = nums.size();
for (int i = 0; i < n; ++i){
for (int j = i + 1; j < n; ++j){
if (nums[i] + nums[j] == target) {
return {i, j};
}
}
}
return {};
}
};
用map解决：
思路：以target = 9为例，遍历到数组中的3的时候，去找哈希表里是否存在6，如果存在6，就返回它的下标。
所以，我们要知道是否存在这个元素的同时，还想知道这个元素的下标，只能用map（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 {iter->second, i};
}
map.insert(pair<int, int>(nums[i], i));
}
return {};
}
};
1.“auto iter = map.find(target - nums[i]);”中，auto关键字的作用？
auto用于自动推导变量的类型，map.find(target - nums[i])返回的是一个迭代器类型unordered_map<int,int>::iterator
具体来说：
1.如果找到了目标值：
返回指向找到的键值对的迭代器
通过这个迭代器，可以使用：
iter->first 访问键（key）
iter->second 访问值（value）
如果没找到目标值：
返回 map.end()，这是一个特殊的迭代器，表示到达容器的末尾
这就是为什么代码中要判断
if(iter != map.end())
2.“map.insert(pair<int, int>(nums[i], i));”中，pair是什么？
pair用于将两个字合成一个单元，pair<int, int>(nums[i], i)创造了一个键值对，然后插入到unordered_map中，作为映射关系。