LeetBook传送门

LeetCode最近一次更新中更新了大量高质量的LeetBook，做起来很舒心，于是打算开一些博文来记录我刷Book的经历。

集合set的使用

t1两个数组的交集

求两个集合的交集，重复元素计算一次。

思路很简单，C++里set元素具有唯一性，所以用两个set给两个数组去重再求交集即可。

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        set<int>set1;
        set<int>set2;
        vector<int> ans;

        for(int i = 0; i < nums1.size(); i++)
            set1.insert(nums1[i]);
        for(int i = 0; i < nums2.size(); i++)
            set2.insert(nums2[i]);

        set_intersection(set1.begin(), set1.end(), set2.begin(), set2.end(), back_inserter(ans));
        return ans;
    }
};

t2快乐数

题目定义了一种数，当且仅当一个数进行一系列逐位平方和计算后能得到1时，它被称为快乐数。一个数如果不是快乐数，他一定无法通过逐位计算平方和最后得到1.

根据题目定义去计算平方和，把每一次的答案扔进一个set里，每次计算完后查询当前值是否之前计算得到过，如果是，那么可以直接return false。循环边界是当前数字为1.

class Solution {
public:
    bool isHappy(int n) {
        set<int>ss;
        while(1)
        {
            if(n == 1) 
                return true;
            int res = 0;
            while(n > 0)
            {
                int tmp = n % 10;
                res += tmp * tmp;
                n /= 10;
                if(ss.count(res)) 
                    return false;
                ss.insert(res);
                n = res;
            }
        }
    }
};

t3存在重复元素

给定一个序列，判断它内部是否存在重复的元素。

没什么难度，最水的一道，用一个set来存序列，每次计算判断当前元素是否在之前出现过就行。

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int>ss;
        int n = nums.size();

        for(int i = 0; i < n; i++)
        {
            if(ss.count(nums[i])) return true;
            ss.insert(nums[i]);
        }

        return false;
    }
};

字典dict的使用

t1两个数组的交集II

求两个数组的交集，重复元素多次计算。

跟set里的那道题很像，但这次用map来辅助判断出现次数。

用map记录第一个数组中出现过的每个元素的次数，再去遍历第二个数组。每次遍历判断当前数字在第一个数组中是否出现过，如果是就把当前数字添加到答案，并减去一个次数。若次数耗尽就在map中移除这个数字。

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
            vector<int>ans;
            map<int, int>mp;
            for(auto el: nums1)
                mp[el]++;
            
            for(auto el: nums2)
            {
                if(mp.count(el)) 
                {
                    ans.push_back(el);
                    mp[el]--;
                    if(!mp[el])
                        mp.erase(el);
                }
            }

            return ans;
    }
};

t2有效的字母异位词

给出两个单词，判断它们是否互为异位词。异位词是指两个单词组成字母完全相同，只是排布顺序不同。

跟上一题有异曲同工的地方。用一个map记录第一个单词中所有字母出现的次数，再去遍历第二个单词，出现一个相同字母就消耗一个次数，没有次数就在map中移除这个单词。最后判断匹配成功的次数是否同时等于两个单词的长度。

class Solution {
public:
    bool isAnagram(string s, string t) {
        map<char, int>mp;

        for(int i = 0; i < s.length(); i++)
            mp[s[i]]++;

        int cmp = 0;
        for(int i = 0; i < t.length(); i++)
        {
            if(mp.count(t[i]))
            {
                cmp++;
                mp[t[i]]--;
                if(!mp[t[i]])
                    mp.erase(t[i]);
            }
        }

        return (cmp == s.length()) && (s.length() == t.length());
    }
};

t3同构字符串

给出两个字符串，判断它们是否是同构地。同构字符串是指两个字符串的组成形式一致，如“egg”与“pdd”都是“122”形式。

有两种做法。第一种是用map保存当前字母在单词中第一次出现的下标位置，然后创造一个变型串，在变型串中把原串的每个字母替换成map中保存的下标，即将“pdd”转化成“122”，最后比较两个单词的变型串，以此为依据来得到答案。

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        set<char>ss;
        map<char, int>mp;
        string s1, t1;
        int key;

        if(s.length() != t.length()) return false;

        ss.clear();
        mp.clear();
        key = 1;
        for(int i = 0; i < s.length(); i++)
        {
            if(!ss.count(s[i]))
            {
                mp[s[i]] = key;
                ss.insert(s[i]);
                key++;
            }
            s1 += to_string(mp[s[i]]);
        }

        ss.clear();
        mp.clear();
        key = 1;
        for(int i = 0; i < t.length(); i++)
        {
            if(!ss.count(t[i]))
            {
                mp[t[i]] = key;
                ss.insert(t[i]);
                key++;
            }
            t1 += to_string(mp[t[i]]);
        }
        //cout << s1 << endl << t1 << endl;
        return t1 == s1;
    }
};

这个代码中的set其实可以不用，map本身也可以起到判断存在的作用。

第二种做法是在学习题解中学会的，很简洁巧妙，思路也是同源地。对于两个互为同构串的单词，他们的形态是一致地，那么对于两个同构串中位于同一个下标上的每个字母，它们上一次出现的下标也一定是一致地。根据这个点就可以得到第二种代码：

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        map<char, int>mp1;
        map<char, int>mp2;

        for(int i = 0; i < s.length(); i++)
        {
            if(mp1[s[i]] != mp2[t[i]]) return false;
            mp1[s[i]] = i;
            mp2[t[i]] = i;
        }

        return true;
    }
};

两个map分别保存两个单词中每一位字母上一次出现的位置。这个做法相当巧妙。

t4根据字符出现频率排序

给定一个字符串，根据字母出现的频率重新给单词排序。相同字母要出现在一起，如“aaccca”不可重排为“acacac”，而应该排成“aaaccc”或“cccaaa”。

用一个map存单词中每个字母出现的次数，再对map以次数为关键字排序，从头取出每个字母组成一个新的单词即可。

class Solution {
public:
    static bool cmp(const pair<char, int>& a, const pair<char, int>& b) 
    {
        return a.second > b.second;
    }

    string frequencySort(string s) {
        string ans = "";
        map<char, int>mp;

        for(auto ch: s) mp[ch]++;

        vector<pair<char, int>>arr(mp.begin(), mp.end());
        sort(arr.begin(), arr.end(), cmp);

        for(auto el: arr)
            while(el.second--) 
                ans += el.first;
        
        return ans;
    }
};

查找表与求和问题

t1两数之和

给定一个数组与一个目标值，在数组中找到两个数使得他们之和等于目标值，返回这两个数的下标。

用map保存每个数的下标，遍历时检测(目标值-当前数)是否存在在数组中，若存在则可以返回答案。

保存时选择下标+1作为数据，防止处理下标为0的情况。

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

        for(int i = 0; i < nums.size(); i++)
        {
            //防止自己加自己
            if(mp[target - nums[i]] && mp[target-nums[i]] != i + 1)
            {
                ans.push_back(i);
                ans.push_back(mp[target-nums[i]]-1);
                return ans;
            }
            mp[nums[i]] = i + 1;
        }

        return ans;
    }
};

t2三数之和

给定一个数组，找出所有和为零的三元组。

这题给超时超傻了，最后看了题解。先讲我自己的做法吧，313个cases过了311个，要不是无序集合不能存tuple估计我就过了。只能说这道题确实不太适合用hash来做。

目标是寻找符合要求的三元组，显然直接三重循环是会爆t的，所以选择定一动二，即使用两重循环枚举第一个与第二个数，在内重循环计算0-(i+j)。这样可以吧时间复杂度降到O(n²)。

用一个map来记录数组中出现过的数、一个set来给三元组们去重。每次计算时检测0-(i+j)是否在数组中，若在且该三元组并未在之前出现过，那么将它加入答案。

值得注意的是，C++中{-1,0,1}与{-1,1,0}被视为两个不同的元组，即使他们组成成员是相同的。所以为了确保同一个元组在作为答案时存在唯一性，需要用一个方法来保证每个元组被计算得到时是有序的，这样才能起到去重作用。

//311/313 cases passed
class Solution {
public:
    //元组排序方法
    inline static tuple<int, int, int> tSort(tuple<int,int,int>tt)
    {
        int a = get<0>(tt), b = get<1>(tt), c = get<2>(tt); 
        int maxn = max(a, max(b, c));
        int mini = min(a, min(b, c));
        int mid = (a + b + c) - (maxn + mini);

        return {mini, mid, maxn};
    }

    vector<vector<int>> threeSum(vector<int>& nums) {
        set<tuple<int,int,int>> mys;
        vector<vector<int>> ans;
        const int n = nums.size();
        
        for(int i = 0; i < n; i++)
        {
            unordered_map<int, int> mp;
            for(int j = i+1; j < n; j++)
            {
                int tmp = 0 - (nums[i] + nums[j]);
                tuple<int, int, int> tt(nums[i], nums[j], tmp);
                tt = tSort(tt);
                if((mp[tmp]) && (!mys.count(tt)))
                {
                    //printf("%d,%d,%d\n", get<0>(tt), get<1>(tt), get<2>(tt));
                    ans.push_back({get<0>(tt), get<1>(tt), get<2>(tt)});
                    mys.insert(tt);
                    mp[tmp]--;
                }
                else mp[nums[j]]++;
            }
        }

        return ans;
    }
};

这样做几乎快通过了，但还是差两个点，于是用了法2。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>>ans;
        const int n = nums.size();

        sort(nums.begin(), nums.end());

        for(int i = 0; i < n; i++)
        {
            if(nums[i] > 0) continue;
            if(i > 0 && nums[i] == nums[i-1]) continue;

            unordered_set<int>mys;
            for(int j = i+1; j < n; j++)
            {
                if(j > i+2 && nums[j] == nums[j-1] && nums[j-1] == nums[j-2]) continue;
                int tmp = 0 - (nums[i] + nums[j]);
                if(mys.count(tmp))
                {
                    ans.push_back({nums[i], nums[j], tmp});
                    mys.erase(tmp);
                }
                else mys.insert(nums[j]);
            }
        }

        return ans;
    }
};

t3四数之和

思路跟二三数之和完全一致，但数据规模的提升使得C++语言下不再适合使用hash来解答，不符合我专题训练的目的，遂跳之。事实上二三四数之和用排序+双指针都能获得较之hash法近十倍优秀的效率，实际运用时并不推荐用hash做此类题目，在此仅作练习目的。

灵活选择键值

t1四数相加 II

给定四个数组，每个数组中选择一个元素，统计元素和为零的四元组个数。

思路也很简单。因为有四个成员，显然不可能直接枚举，所以定二动二。
用两重循环枚举Ai+Bj，把它存入map，然后再用另外的两重循环枚举0-Ci-Dj是否在map中，若是则累加器累加上其出现的次数，最后就是答案。

class Solution {
public:
    int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
        int ans = 0;
        map<int, int>mp;

        for(int i = 0; i < A.size(); i++)
            for(int j = 0; j < B.size(); j++)
                mp[A[i] + B[j]]++;
        
        for(int i = 0; i < C.size(); i++)
            for(int j = 0; j < D.size(); j++)
                if(mp[0 - C[i] - D[j]])
                    ans += mp[0 - C[i] - D[j]];
        
        return ans;
    }
};

t2字母异位词分组

给出一系列单词，把同属于一类异位词的单词分到一组。异位词是指字母组成相同，但位置不一定相同的一系列单词。

这里的键值设置有一些巧妙。用一个map，键设置为string，值为string的vector。

每次读入一个string，将它排序。根据定义，异位词的组成字母一定是一样的，所以同属一类的异位词在排序后一定都是同一个单词，然后将这同一类的单词压入当前键值所映射的vector中。最后在挨个把每个vector压入答案中即可。

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        map<string, vector<string>> mp;
        vector<vector<string>> ans;

        for(string s: strs)
        {
            string tmp = s;
            sort(tmp.begin(), tmp.end());
            mp[tmp].push_back(s);
        }

        for(auto el: mp)
            ans.push_back(el.second);

        return ans;
    }
};

t3回旋镖的数量

给出若干个二维点，定义一个三元组为回旋镖，当且仅当组成它的三个点中有一个点到另外两个点的距离相等，找出这组二维点中回旋镖的数量。

定一动一。对于每个点i，枚举计算每个点j到它的距离，以这个距离为键，以其值为累加器计算距离为|(i,j)|的线段的个数，统计这个个数即为答案。

class Solution {
public:
    int numberOfBoomerangs(vector<vector<int>>& points) {
        int ans = 0;
        const int n = points.size();

        for(int i = 0; i < n; i++)
        {
            map<int, int> mp;
            for(int j = 0; j < n; j++)
            {
                int dx = points[i][0] - points[j][0];
                int dy = points[i][1] - points[j][1];

                mp[dx * dx + dy * dy]++;
            }

            for(auto el: mp)
                ans += el.second * (el.second - 1);
        }

        return ans;
    }
};

t4直线上最多的点数

给定一系列二维点，求最多有多少个共线的点。

这是一道hard，但其实没那么难，因为题设有个隐藏设定：平行也算作共线。

所以我们可以直接用斜率做map的键，值做累加器来统计同在一条直线上的点。

具体来讲就是两重循环定一动一去枚举所有的点，以斜率为键来记录同在一条直线上的点的个数，最后统计最大值就可以了。

需要注意的点有两个。第一个是这题有一个数据存在精度问题，所以不能用double做键表示斜率，我采用的是string；第二个是处理原点的问题，我选择的是单独用一个累加变量，检测到0直接++然后continue就行了。

class Solution {
public:
    int maxPoints(vector<vector<int>>& points) {
        int ans = 0;
        const int n = points.size();

        if(n < 3) return n;

        for(int i = 0; i < n; i++)
        {
            int cnt = 0;
            int curMax = 0;
            map<string, int>mp;
            for(int j = i+1; j < n; j++)
            {
                if(points[i][0] == points[j][0] 
                && points[i][1] == points[j][1])
                {
                    cnt++;
                    continue;
                }

                int dx = points[j][0] - points[i][0];
                int dy = points[j][1] - points[i][1];
                int tmp = gcd(dx, dy);

                string key = to_string(dx / tmp) + "/" + to_string(dy / tmp);
                //cout << key << endl;
                mp[key]++;
                curMax = max(curMax, mp[key]);
            }

            ans = max(ans, curMax + cnt + 1);
        }

        return ans;
    }
private:
    int gcd(int a, int b)
    {
        if (b == 0)
            return a;

        return gcd(b, a % b);
    }
};

查找表和滑动窗口

t1存在重复元素II

给定一个数组，找出其中两个下标之差不超过k并且值相等的元素。

这题时间卡的很死，O(n²)必超，所以采用滑动窗口。

用一个set记录当前存在的元素，每次遍历检测当前元素是否存在。为了切合题意，维护set的size为k，即当set.size()>k时，erase掉nums[i-k]就行了。

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_set<int> mys;
        const int n = nums.size();

        for(int i = 0; i < n; i++)
        {
            if(mys.count(nums[i])) return true;
            mys.insert(nums[i]);
            if(mys.size() > k) mys.erase(nums[i - k]);
        }

        return false;
    }
};

t2存在重复元素 III

跟上一题很像，但这题要找的是满足一个大小区间的数。

思路也很清晰，在上一题滑动窗口的基础上思考题设要求：

“使得 nums [i] 和 nums [j] 的差的绝对值小于等于 t” 其实就是指“nums[i]-t<=nums[j]<=nums[i]+t”。可以利用set的有序性，二分查找第一个大于等于nums[i]-t的值，再判断它是否小于等于nums[i]+t即可。

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        set<long long> mys;

        for(int i = 0; i < nums.size(); i++)
        {
            auto el = mys.lower_bound((long long)nums[i] - t);

            if(el != mys.end() && (*el) <= (long long)nums[i] + t)
                return true;
            mys.insert(nums[i]);

            if(mys.size() > k)
                mys.erase(nums[i-k]);
        }

        return false;
    }
};

总结