代码随想录|day6|哈希表篇-- 242.有效的字母异位词 、349. 两个数组的交集 、202. 快乐数、1. 两数之和

总链接https://docs.qq.com/doc/DUEtFSGdreWRuR2p4?u=329948d2f0044f34b7cbe72503f0b572

242.有效的字母异位词

链接：代码随想录

 

class Solution {
public:bool isAnagram(string s, string t) {//两种做法，一种是int f[26]的数组,一种是map
/*第一种，麻烦unordered_map<int,int>my_map;for(auto ch:s){my_map[ch]++;}for(auto ch:t){if(my_map.find(ch)==my_map.end()){return false;}else{my_map[ch]--;}}for(auto k:my_map){if(k.second!=0){return false;}}return true;
*///第二种，int f[26]int f[26]={0};for(auto ch:s){f[ch-'a']++;}// s 和 t 中每个字符出现的次数都相同for(auto ch:t){if(f[ch-'a']>0){f[ch-'a']--;}else{return false;}}for(int i=0;i<26;i++){if(f[i]!=0){return false;}}return true;}
};

 349. 两个数组的交集 

链接：代码随想录

 

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {//由于0 <= nums1[i], nums2[i] <= 1000，类似哈希表//想了构建两个set，或者两个vector，都不够简洁，看了代码随想录，这种解法是最优的vector<int>v(1001,0);for(auto num :nums1){v[num]=1;//代表这个元素出现过 }vector<int> res;for(auto num :nums2){if(v[num]){res.push_back(num);v[num]=0;}}return res;}
};

202. 快乐数

链接：代码随想录

建议：这道题目也是set的应用，其实和上一题差不多，就是 套在快乐数一个壳子

 

class Solution {
public:
//int有 31位有效数字，最大值是2^31-1 ，也是最多10个9，所以不用担心每位数位数上的平方和最大值越界//有个无限循环，怎么判断呢？-----思考，这道题之所以用哈希表，至少说明出现了重复值，即环，则利用哈希表find重复值的性质bool isHappy(int n) {unordered_set<int>my_set;int res=n;while(my_set.find(res)==my_set.end()){my_set.insert(res);res=caculate_sum(res);if(res==1){return true; }}return false;}//写一个函数，计算一个数各位数之和int caculate_sum(int n){int sum=0;while(n>0){int r=n%10;sum+=r*r;n=n/10;}return sum;}
};

1. 两数之和

链接：代码随想录

 

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {//每种输入只会对应一个答案。------找到一个答案就行//但是，数组中同一个元素在答案里不能重复出现。-------找到的index不能是它本身// 数组中元素可以重复？可以重复吗，我觉得不可以。。，因为这样就不会对应一个答案了。unordered_map<int,int>m;int index=0;for(auto num : nums){if(m.find(target-num)!=m.end())//找到这个数{return {m[target-num],index};}else{m[num]=index++;}}return {-1,-1};}
};