标签：LeetCode242 LeetCode349 set return int vector hash 两数 size

【算法训练营day6】LeetCode242. 有效的字母异位词 LeetCode349. 两个数组的交集 LeetCode202. 快乐数 LeetCode1. 两数之和

LeetCode242. 有效的字母异位词

题目链接：242. 有效的字母异位词

初次尝试

用一个初始化为0的数组储存字符出现的次数，数组下标为ASCII码表上小写字母对应的整数值，然后对s字符串的每个字符，每出现一次，对应的数组元素就加1；然后对t字符串的每个字符，每出现一次，对应的数组元素就减1，一旦出现值为负数的数组元素，说明有字符出现的次数不一样，就可以直接return false。以上前提是两个字符串长度相等，需要在开头检查。

class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.size() != t.size()) return false;
        vector<int> alphaTable(123, 0);

        for (int i = 0; i < s.size(); i++) {
            alphaTable[s[i]]++;
        }

        for (int i = 0; i < t.size(); i++) {
            alphaTable[t[i]]--;
            if (alphaTable[t[i]] < 0) {
                return false;
            }
        }

        return true;
    }
};

看完代码随想录后的想法

思路一样，但是代码细节还有可以优化的地方，比如不需要创建123长度的数组，只需要用s[i]-'a'这样的操作将数组索引标准化到[0, 25]的区间即可。

class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.size() != t.size()) return false;
        vector<int> alphaTable(26, 0);

        for (int i = 0; i < s.size(); i++) {
            alphaTable[s[i]-'a']++;
        }

        for (int i = 0; i < t.size(); i++) {
            alphaTable[t[i]-'a']--;
            if (alphaTable[t[i]-'a'] < 0) {
                return false;
            }
        }

        return true;
    }
};

---

LeetCode349. 两个数组的交集

题目链接：349. 两个数组的交集

初次尝试

使用了两个set，一个作为哈希表存放在nums1中出现的整数，另一个存放nums1中在nums2再次出现的整数，并且自带去重功能，后者最后转换为vector输出。

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        set<int> hash;
        set<int> ansSet;

        for (int i = 0; i < nums1.size(); i++) {
            hash.insert(nums1[i]);
        }

        for (int i = 0; i <nums2.size(); i++) {
            if (hash.count(nums2[i])) {
                ansSet.insert(nums2[i]);
            }
        }

        vector<int> ansVec(ansSet.begin(), ansSet.end());
        
        return ansVec;
    }
};

看完代码随想录后的想法

思路一样，但是语法层面上学到了很多：

1. 当集合不需要排序，并且有去重需求时，用unordered_set更好
2. set可以直接用一个vector初始化
3. 遍历vector时，int num : nums2，这样写简洁
4. set不仅有count成员函数，也有find成员函数，都可以用于检查元素是否存在于表中

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> hash(nums1.begin(), nums1.end());
        unordered_set<int> ansSet;

        for (int num : nums2) {
            if (hash.count(num)) {
                ansSet.insert(num);
            }
        }

        return vector<int>(ansSet.begin(), ansSet.end());
    }
};

---

LeetCode202. 快乐数

题目链接：202. 快乐数

初次尝试

没有想到解法，对于如何判断无限循环这一点存在疑惑。

看完代码随想录后的想法

应该意识到出现无限循环是因为出现了重复的情况，遇到了闭环，了解了这点后解题并不难。

class Solution {
public:
    int getSum(int n) {
        int nSum = 0;
        while (n) {
            nSum += (n % 10) * (n % 10);
            n = n / 10;
        }
        return nSum;
    }

    bool isHappy(int n) {
        unordered_set<int> hash;
        while (true) {
            if (n == 1) return true;
            else if (hash.count(n)) return false;
            hash.insert(n);
            n = getSum(n);
        }
    }
};

---

LeetCode1. 两数之和

题目链接：1. 两数之和

初次尝试

还不太会用map，正好看题解学一下。

看完代码随想录后的想法

解题思路没问题，语法层面需要看看工具书补一下C++ STL部分的知识。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hash;

        for (int i = 0; i < nums.size(); i++) {
            auto iter = hash.find(target - nums[i]);
            if (iter != hash.end()) {
                return {iter -> second, i};
            }
            hash.insert(pair<int, int>(nums[i], i));
        }
        
        return {};
    }
};

标签：LeetCode242,LeetCode349,set,return,int,vector,hash,两数,size
From： https://www.cnblogs.com/BarcelonaTong/p/16801235.html