美文网首页程序员
Leetcode刷题总结(3):哈希表问题

Leetcode刷题总结(3):哈希表问题

作者: 张慕晖 | 来源:发表于2018-04-09 14:14 被阅读52次

    447

    题意

    在平面上有n个整点,n<=500,在[-10000, +10000]范围内。求出下列三元组的个数:(i, j, k),其中点i到j和i到k的距离相等。(顺序相关)

    分析

    我最开始是想把每两个点的距离都求出来,排序,然后在距离相同的二元组里寻找相同的点。但是这样其实太复杂了,也保证不了复杂度。于是我看了看解析(https://leetcode.com/problems/number-of-boomerangs/discuss/92866/C++-clean-solution-O(n2).-Fully-commented-and-explained.),发现了一种好得多的做法:

    • 遍历每一个点
    • 对于每一个点,建立一个map:<该点到其他点的距离, 点的数量>,也就是说,把其他所有点和它的距离建成一个map。可以这样做的核心是,我们只需要同样距离的点的数量
    • 遍历这个map,得出以该点为开头的三元组共有多少个

    一点细节:距离的平方最大为20000^2*2=800000000,不会超过int。

    代码

    class Solution {
    public:
        int numberOfBoomerangs(vector<pair<int, int>>& points) {
            int ans = 0;
            
            for (int i = 0; i < points.size(); i++) {
                map<int, int> m;
                for (int j = 0; j < points.size(); j++) {
                    if (i == j)
                        continue;
                    int dis = (points[i].first - points[j].first) * (points[i].first - points[j].first) + (points[i].second - points[j].second) * (points[i].second - points[j].second);
                    m[dis]++;
                }
                
                for (map<int, int>::iterator iter = m.begin(); iter != m.end(); iter++) {
                    if (iter->second > 1)
                        ans += iter->second * (iter->second - 1);
                }
            }
            
            return ans;
        }
    };
    

    时间大约是17.78%。因为马上就要面试,所以最近心急了。

    560

    题意

    一个整数数组,长度<=20000,每个数的绝对值<=1000。给定数k,求出这个数组中全部值的和为k的子序列。

    分析

    十分简单。建立一个map,存放部分和。从第一个数开始累加,每得到一个部分和,就查看部分和-k在map中有几个;然后将该部分和存入map中。

    代码

    class Solution {
    public:
        int subarraySum(vector<int>& nums, int k) {
            int sum = 0;
            int ans = 0;
            map<int, int> m;
            m[0]++;
            for(int i = 0; i < nums.size(); i++) {
                sum += nums[i];
                ans += m[sum - k];
                m[sum]++;
            }
            return ans;
        }
    };
    

    时间是45.75%。

    336

    题意

    给你一个数组的词(词之间两两不同),要求找到所有这样的词对:两个词拼在一起是回文词。

    分析

    开始时的想法是:两个词拼在一起能回文,说明比较短的那个词翻转之后是长的词的后缀。那么,把词按长度排序,然后把较短的词翻转之后插入到一个map中。

    但这样似乎不好map。另一个想法是,把每个较短的词的前面的固定长度翻转之后进行map。但这样的话不好确定太短的词的长度。

    另一个有趣的想法是,把所有的词都加入到map中,然后按词的长度倒排序,计算出最长的词的每个翻转之后对应的缺失部分,然后在map中查看有没有这样的词。很合理。于是我就这样做了。然后我发现根本没有排序的必要,不过两侧都要翻转。

    有一些corner case,比如["a", ""],需要输出[[0, 1], [1, 0]]

    代码

    class Solution {
        
    public:
        vector<vector<int>> palindromePairs(vector<string>& words) {
            map<string, int> mmap;
            for (int i = 0; i < words.size(); i++) {
                mmap[words[i]] = i;
            }
            
            vector<pair<int, int>> ans;
            
            for (int i = 0; i < words.size(); i++) {
                // flip and find a word that has length <=
                string rev = words[i];
                reverse(rev.begin(), rev.end());
                
                // cout << words[i] << ' ' << rev << endl;
                
                // flip to right
                for (int j = 0; j < rev.size(); j++) {
                    if (j == 0 || words[i].substr(rev.size() - j, j) == rev.substr(0, j)) {
                        if (j != 0) {
                            // cout << words[i].substr(rev.size() - j, j) << ' ' << rev.substr(0, j) << endl;
                        }
                        if (mmap.count(rev.substr(j, rev.size() - j))) {
                            // cout << "right: " << j << ' ' << rev.substr(j, rev.size() - j) << endl;
                            int ind = mmap[rev.substr(j, rev.size() - j)];
                            if (ind != i)
                                ans.push_back(make_pair(i, ind));
                        }
                    }
                }
                
                // flip to left
                for (int j = 0; j < rev.size(); j++) {
                    if (j == 0 || rev.substr(rev.size() - j, j) == words[i].substr(0, j)) {
                        if (j != 0) {
                            // cout << rev.substr(rev.size() - j, j) << ' ' << words[i].substr(0, j) << endl;
                        }
                        if (mmap.count(rev.substr(0, rev.size() - j))) {
                            // cout << "left: " << j << ' ' << rev.substr(0, rev.size() - j) << endl;
                            int ind = mmap[rev.substr(0, rev.size() - j)];
                            if (ind != i)
                                ans.push_back(make_pair(ind, i));
                        }
                    }
                }
                
                if (words[i] == rev && words[i].size() > 0 && mmap.count("")) {
                    ans.push_back(make_pair(i, mmap[""]));
                    ans.push_back(make_pair(mmap[""], i));
                }
            }
            
            sort(ans.begin(), ans.end());
            vector<pair<int, int>>::iterator iter = unique(ans.begin(), ans.end());
            ans.erase(iter, ans.end());
            vector<vector<int>> ret;
            for (int i = 0; i < ans.size(); i++) {
                vector<int> x;
                x.push_back(ans[i].first);
                x.push_back(ans[i].second);
                ret.push_back(x);
            }
            
            return ret;
        }
    };
    

    时间是29.94%。

    相关文章

      网友评论

        本文标题:Leetcode刷题总结(3):哈希表问题

        本文链接:https://www.haomeiwen.com/subject/kvxlhftx.html