算法训练营Day 6

242. 有效的字母异位词

题目链接：https://leetcode.cn/problems/valid-anagram/
文章讲解：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#_242-%E6%9C%89%E6%95%88%E7%9A%84%E5%AD%97%E6%AF%8D%E5%BC%82%E4%BD%8D%E8%AF%8D
视频讲解：https://www.bilibili.com/video/BV1YG411p7BA

考察点：哈希表

本题直接使用数组模拟哈希表

class Solution {
public:
    bool isAnagram(string s, string t) {
        int tmp[26] = {0};
        for(auto a: s){
            tmp[a-'a']++;
        }
        for(auto b: t){
            tmp[b-'a']--;
        }
        for(auto x: tmp){
            if(x!=0){
                return false;
            }
        }
        return true;
    }
};

349. 两个数组的交集

题目链接：https://leetcode.cn/problems/intersection-of-two-arrays/
文章讲解：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
视频讲解：https://www.bilibili.com/video/BV1ba411S7wu

考察点：哈希表

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> us1;
        unordered_set<int> us2;
        vector<int> res;
        for(auto a: nums1){
            us1.insert(a);
        }
        for(auto b: nums2){
            us2.insert(b);
        }
        unordered_set<int> :: iterator itr;
        for (itr = us1.begin(); itr != us1.end(); itr++){
            if(us2.find(*itr)!=us2.end()){
                res.push_back(*itr);
            }
        }
        return res;
    }
};

202.快乐数

题目链接：https://leetcode.cn/problems/happy-number/
文章讲解：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;
            }
            // 如果这个sum曾经出现过，说明已经陷入了无限循环了，立刻return false
            if (set.find(sum) != set.end()) {
                return false;
            } else {
                set.insert(sum);
            }
            n = sum;
        }
    }
};

1. 两数之和

题目链接：https://leetcode.cn/problems/two-sum/
文章讲解：https://programmercarl.com/0001.%E4%B8%A4%E6%95%B0%E4%B9%8B%E5%92%8C.html
视频讲解：https://www.bilibili.com/video/BV1aT41177mK

考察点：哈希表

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> hash_map; 
        for(int i=0;i<nums.size();++i){
            auto res = hash_map.find(target-nums[i]);
            if (res!=hash_map.end()){
                return {res->second,i};
            }
            hash_map.insert(make_pair(nums[i],i));
        }
        return {0, 0};
    }
};