Leetcode 149. Max Points on a Li

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

思路：
两次循环求每个点和其他点连线的斜率，斜率相同则在一条直线，最后统计斜率相同的最多的个数。
用斜率由于小数精度问题，有一些case会有bug，因此把斜率转化为分数形式，分子分母组成key。

public int maxPoints(Point[] points) {
    if (points == null) {
        return 0;
    }
    if (points.length <= 2) {
        return points.length;
    }

    int res = 0;
    for (int i = 0; i < points.length; i++) {
        HashMap<String, Integer> map = new HashMap<>();
        int cnt = 0, duplicate = 0;
        for (int j = i + 1; j < points.length; j++) {
            int diffy = points[j].y - points[i].y;
            int diffx = points[j].x - points[i].x;
            if (diffx == 0 && diffy == 0) {
                duplicate++;
                continue;
            }
            int gcd = getGCD(diffx, diffy);
            if (gcd!=0){
                diffx /= gcd;
                diffy /= gcd;
            }
            String key = String.valueOf(diffx) + "_" + String.valueOf(diffy);
            map.put(key, map.getOrDefault(key, 0) + 1);
            cnt = Math.max(cnt, map.get(key));
        }
        res = Math.max(res, duplicate + cnt + 1);
    }

    return res;
}

private int getGCD(int diffx, int diffy) {
    if (diffy == 0) {
        return diffx;
    }
    return getGCD(diffy, diffx % diffy);
}