Leetcode.149.Max Points on a Lin

题目

二维坐标上给定多个点, 输出最多有多少个点在一条直线上.

Input: [[1,1],[2,2],[3,3]]
Output: 3
Input: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4

思路

遍历计算两点的斜率, 运用gcd记录斜率, 然后求出最大值.

int gcd(int a, int b){
    return b == 0 ? a : gcd(b,a%b);
}

int maxPoints(vector<vector<int>>& points) {
    int n = (int)points.size();
    if (n < 3) return n;
    int res = 1;

    for (int i = 0; i < n-1; i++) {
        int temp = 1;
        unordered_map<string,int> map;
        for (int j = i+1; j < n; j++) {
            int x = points[i][0] - points[j][0];
            int y = points[i][1] - points[j][1];

            if (x == 0 && y == 0) {
                ++temp;
            }  else if (y == 0) {
                ++map["h"];
            }else if (x == 0) {
                ++map["v"];
            } else {
                int temp = abs(gcd(y,x));
                if (y < 0) temp *= -1;
                ++map[to_string(y/temp)+to_string(x/temp)];
            }
        }

        res = max(res,temp);
        for (auto i : map)
            res = max(res,i.second+temp);
    }

    return res;
}

总结

核心就是运用GCD计算斜率, 并保存起来. 熟练掌握GCD的最简写法.