第五天|leetcode 242.有效的字母异位词 ，349. 两个数组的交集，202. 快乐数, 1. 两数之和
总结
是用数组还是用哈希表，要根据具体问题决定。而且刷题的时候要多举例子，多实验几下。
242.有效的字母异位词
今天主要是哈希表，但是这个题不需要使用unordered_set,这个题只需要存储小写字母的出现次数，所以只需要一个长度为26的数组进行存储字符出现的次数就好了，不过还要注意长度需要相等，否则也会出现问题。
class Solution {public: bool isAnagram(string s, string t) { //这里没有使用unordered_set //直接使用int[26]来保存 //长度不相等直接pass if(s.size()!=t.size()){ return 0; } int visit[26] = {0}; for(int i = 0;i < s.size();i++){ visit[int(s[i])-97]++; } for(int i = 0;i < t.size();i++){ if(visit[int(t[i]-97)] != 0){ visit[int(t[i]-97)]--; }else{ return 0; } } return 1; }};349. 两个数组的交集
利用set来存储已经存在的元素并进行比较，注意每当发现一个相同的元素，就要将对应哈希表中的元素删除。
class Solution {public: vector intersection(vector& nums1, vector& nums2) { vectorans; unordered_setst; for(int i = 0;i < nums1.size();i++){ st.insert(nums1[i]); } for(int i = 0;i < nums2.size();i++){ if(st.find(nums2[i])!=st.end()){ ans.push_back(nums2[i]); st.erase(nums2[i]); } } return ans; }};在构建set时，可以通过已有的数组进行构建。不需要通过for循环。
class Solution {public: vector intersection(vector& nums1, vector& nums2) { vectorans; unordered_setst(nums1.begin(),nums1.end()); for(int i = 0;i < nums2.size();i++){ if(st.find(nums2[i])!=st.end()){ ans.push_back(nums2[i]); st.erase(nums2[i]); } } return ans; }};202. 快乐数
这个题感觉有点难。主要的思想就是要知道如果这个数不是快乐数，它就会在求和的时候重复出现。
当然正常来说还有一种可能就是求和的过程中sum会无限增大，但是这种情况不会出现。可以举最大数的例子。
比如9-81-65-36+25=61-37-58-64+25=89.。。最大就是99
99-162-41.。。。。不会超过162
999-81*3=243.。。。。
9999-81*4=324.。。。。
所以一共只有两种情况
- 不断的求和直到结果为 1。
- 不断的求和后进入循环，所以就可以通过是否出现重复的数来判断是否是快乐数（这个好难想啊啊啊啊啊，所以要多举几个例子实验一下）。
- （不会出现所以不用考虑）不断的增加到无穷大。
代码如下：
class Solution {public: bool isHappy(int n) { int sum = 0; unordered_setunset; while(n!=1){ //这里可以写个函数求和 //可以通过除10取余的操作进行取个个位 string str = to_string(n); for(int i = 0;i < str.size();i++){ sum += (int(str[i])-48)*(int(str[i])-48); } //如果在哈希表中找到,就说明这个数出现了循环，就不是欢乐数 if(unset.find(sum)!=unset.end()){ return 0; } //否则将此数插入并更新n的值 unset.insert(sum); n = sum; sum = 0; } return 1; }};1. 两数之和
leetcode的第一题，真是印象深刻，不过利用map就能很好的实现，而且最主要的就是要一边存一边去找目标值。这个很重要。
class Solution {public: vector twoSum(vector& nums, int target) { vectorans; unordered_mapumap; for(int i = 0;i < nums.size();i++){ //优化，一边存一边比较 if(umap.find(target-nums[i])!=umap.end()){ ans.push_back(i); ans.push_back(umap[target-nums[i]]); return ans; }else{ umap[nums[i]] = i; } } return ans; }};
