代码随想录算法【Day5】

DAY5

1.熟悉哈希表的数据结构：数组、map和set，使用方法、使用场景

2.哈希表应用场景：解决给你一个元素，判断它在集合里是否出现过。

242.有效的字母异位词

本题用数组解决的。

class Solution {
public:bool isAnagram(string s, string t) {//通过ascii码表将26个字母映射到数组recordint 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类型进行算术运算时，会发生如下转换：

1. 在算术运算之前，char类型会被自动提升(promoted)为int类型

2. 这种转换叫做"整型提升"(integral promotion)

3. 所以两个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，包含这两个迭代器之间的所有元素。

这行代码做了以下事情：

1. 创建一个新的 vector<int> 对象

2. 使用 result_set 的开始迭代器（begin()）和结束迭代器（end()）

3. 将 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）

1. 如果没找到目标值：

• 返回 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中，作为映射关系。