signed

QiShunwang

“诚信为本、客户至上”

LeetCode 149. 直线上最多的点数

2021/6/24 22:13:41   来源:

难度:困难。
标签:几何,哈希表,数学。

开始通过斜率计算,计算每两个点组成的线段的斜率,共有 n ∗ ( n − 1 ) / 2 n*(n - 1) / 2 n(n1)/2条不同的线段,将线段的斜率作为key,线段个数作为value,根据线段个数的最大值max,可计算出点的个数。
这种思路只比较斜率是否相同,没有固定点,点在同一条直线,不仅要斜率相同,还要经过同一个点。因此,得到了错误的答案。

错误解法:

class Solution {
public:
    int maxPoints(vector<vector<int>>& points) {
        int n = points.size();
        unordered_map<float, int> maps;
        unordered_map<int, int> extra_map_x;
        unordered_map<int, int> extra_map_y;
        int num = 0;
        for(int i = 0; i < n - 1; ++i){
            for(int j = i + 1; j < n; ++j){
                // cout << "zuhe: " << i << " " << j << endl;
                if(points[i][0] == points[j][0]){
                    // cout << "1. k:  inf   x: " << points[i][0] << endl; 
                    extra_map_x[points[i][0]]++;
                    num = max(num, extra_map_x[points[i][0]]);
                }
                else if(points[i][1] == points[j][1]){
                    // cout << "2. k:  0   y: " << points[i][1] << endl; 
                    extra_map_y[points[i][1]]++;
                    num = max(num, extra_map_y[points[i][1]]);
                }
                else{
                    float k = (float)(points[i][1] - points[j][1]) / (float)(points[i][0] - points[j][0]);
                    // cout << "3. k: " << k << endl;
                    maps[k]++;
                    num = max(num, maps[k]);
                }
            }
        }
        // cout << num << endl;
        int res = 1;
        while(num > 0){
            num -= res;
            res++;
        }
        return res;
    }
};

错误用例:

[[0,0],[4,5],[7,8],[8,9],[5,6],[3,4],[1,1]]

应该固定一个点来计算,每次固定一个点,计算其他所有点与该点的斜率,此时记出现做多次斜率的个数为m,则答案为m+1。
我真是傻了。

class Solution {
public:
    int maxPoints(vector<vector<int>>& points) {
        int n = points.size();
        if(n <= 2)return n;
        int res = 0;
        for(int i = 0; i < n - 1; ++i){
            if(res >= n - i || res > n / 2)break;
            unordered_map<float, int> maps;
            int kx = 1;
            for(int j = i + 1; j < n; ++j){
                int x = points[i][0]- points[j][0], y = points[i][1] - points[j][1];
                // cout << "zuhe: " << i << " " << j << endl;
                if(x == 0){
                    // cout << "1. k:  inf   x: " << points[i][0] << endl; 
                    kx++;
                }
                else{
                    float k = (float)y / x;
                    // cout << "3. k: " << k << endl;
                    maps[k]++;
                }
            }
            for (auto& [_, res] : maps) {
                kx = max(kx, res + 1);
            }
            res = max(res, kx);
        }
        return res;
    }
};

结果:
在这里插入图片描述