作图网站都有哪些云南省建设厅网站怎么进不去
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类型进行算术运算时，会发生如下转换：
-
在算术运算之前，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中，作为映射关系。