leetcode_day6

有效的字母异位词

哈希表新手题，不过可以直接排序再判断，剑走偏锋不用哈希

class Solution {
public:
    bool isAnagram(string s, string t) {
        if(s.size() != t.size()) return false;
        sort(s.begin(), s.end());
        sort(t.begin(), t.end());
        return s == t;
    }
};

两个数组的交集

这个也可以排序然后双指针，不用哈希，时间复杂度 \(O(mlogm+nlogn)\)，主要是排序的复杂度，空间复杂度 \(O(mlogm+nlogn)\) 也是排序造成的。

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());
        int len1 = nums1.size(), len2 = nums2.size();
        int index1 = 0, index2 = 0;
        vector<int> ans;
        while(index1 < len1 && index2 < len2) {
            if(nums1[index1] == nums2[index2]) {
                if(ans.size() == 0 || nums1[index1] != ans.back()) ans.push_back(nums1[index1]);
                index1++;
                index2++;
            }
            else if(nums1[index1] < nums2[index2]) index1++;
            else index2++;
        }
        return ans;
    }
};

快乐数

这题和环形链表II有点异曲同工之妙，笔者的做法是用一个set来记录每次计算的结果，重复就false，等于1就true。

但看过评论区后发现，这样只是走了int限制的捷径，有可能会爆栈，所以不能记录，而应该采取环形链表中检查环的方法——追及问题。

用快慢指针，不过指的是计算结果，如果fast最终等于slow，则有环，false，这样空间复杂度就成了\(O(1)\)

class Solution {
public:
    int bitSquareSum(int n) {
        int sum = 0;
        while(n > 0)
        {
            int bit = n % 10;
            sum += bit * bit;
            n = n / 10;
        }
        return sum;
    }
    
    bool isHappy(int n) {
        int slow = n, fast = n;
        do{
            slow = bitSquareSum(slow);
            fast = bitSquareSum(fast);
            fast = bitSquareSum(fast);
        }while(slow != fast);
        
        return slow == 1;
    }
};

该题解来源

两数之和

思路还记得，用哈希来记录target - x，利用set查找的O(1)复杂度来优化查找过程。

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

unordered_set

• 无序存储
• 元素独一无二，即键值key唯一

## 常用方法

• unorder_set<string> first容器定义
• first.empty()判断容器是否是空，是空返回true，反之为false
• first.size()返回容器大小
• first.maxsize()返回容器最大尺寸
• first.begin()返回迭代器开始
• first.end()返回迭代器结束
• first.find(value)返回value在迭代器的位置，没找到会返回end()
• first.count(key)返回key在容器的个数
• first.insert(value)将value插入到容器中
• first.erase(key)通过key删除
• first.clear()清空容器 详细文档