代码随想录算法训练营第六天

标签：set return int 训练营 随想录 第六天 vector sum unordered

今日刷题4道：先复习了哈希表理论基础，然后刷了4道题。242.有效的字母异位词，349. 两个数组的交集，202. 快乐数，1. 两数之和。

为什么没有第5天呢，因为周日休息！

ps:什么时候想到用哈希法，当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。 这句话很重要，大家在做哈希表题目都要思考这句话。

●  242.有效的字母异位词

题目链接/文章讲解/视频讲解： https://programmercarl.com/0242.%E6%9C%89%E6%95%88%E7%9A%84%E5%AD%97%E6%AF%8D%E5%BC%82%E4%BD%8D%E8%AF%8D.html

class Solution { public:     bool isAnagram(string s, string t) {         int hash[26] = {0};       //数组需要初始化为0         for(int i = 0; i < s.size(); i++){             hash[s[i] - 'a']++;          //减去字符a，得到的ASCII值就是0-25了         }         for(int j = 0; j < t.size(); j++){             hash[t[j] - 'a']--;         }         for(int k = 0; k < 26; k++){             if(hash[k] != 0) return false;         }         return true;     } };

●  349. 两个数组的交集

题目链接/文章讲解/视频讲解：https://programmercarl.com/0349.%E4%B8%A4%E4%B8%AA%E6%95%B0%E7%BB%84%E7%9A%84%E4%BA%A4%E9%9B%86.html

std::set和std::multiset底层实现都是红黑树，std::unordered_set的底层实现是哈希表， 使用unordered_set 读写效率是最高的，并不需要对数据进行排序，而且还不要让数据重复，所以选择unordered_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){             if(nums_set.find(num) != nums_set.end()){                 result_set.insert(num);             }         }         return vector<int>(result_set.begin(),result_set.end());     } };

 

 本题后面 力扣改了 题目描述 和 后台测试数据，增添了 数值范围：

所以就可以 使用数组来做哈希表了， 因为数组都是 1000以内的。

class Solution { public:     vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {         unordered_set<int> result_set;         int hash[1005] = {0};         for(int num : nums1){             cout << num << endl;             hash[num] = 1;         }         for(int num : nums2){             if(hash[num] == 1){                 result_set.insert(num);             }         }         return vector<int>(result_set.begin(),result_set.end());     } };

●  202. 快乐数

题目链接/文章讲解：https://programmercarl.com/0202.%E5%BF%AB%E4%B9%90%E6%95%B0.html

class Solution { public:     int getSum(int n){         int sum = 0;         while(n){             sum += (n % 10) * (n % 10);             n /= 10;         }         return sum;     }
    bool isHappy(int n) {         unordered_set<int> set;         while(1){             int sum = getSum(n);             if(sum == 1) return true;             if(set.find(sum) != set.end()){                 return false;             }             else{                 set.insert(sum);             }             n = sum;         }     } };

●  1. 两数之和

class Solution { public:     vector<int> twoSum(vector<int>& nums, int target) {         std::unordered_map <int,int> map;         for(int i = 0; i< nums.size(); i++){             auto iter = map.find(target - nums[i]);      //auto循环遍历             if(iter != map.end()){                 return {iter -> second, i};             }             map.insert(pair<int,int>(nums[i],i));         }         return {};     } };

标签：set,return,int,训练营,随想录,第六天,vector,sum,unordered
From： https://www.cnblogs.com/zzw0612/p/17019567.html