Leetcode - Max Points on a Line

My code:

/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */
public class Solution {
    public int maxPoints(Point[] points) {
        if (points == null || points.length == 0) {
            return 0;
        }
        
        HashMap<Integer, Map<Integer, Integer>> map = new HashMap<Integer, Map<Integer, Integer>>();
        int result = 0;
        for (int i = 0; i < points.length; i++) {
            int max = 0;
            int overlap = 0;
            int pre_x = points[i].x;
            int pre_y = points[i].y;
            map.clear();
            for (int j = i + 1; j < points.length; j++) {
                int curr_x = points[j].x;
                int curr_y = points[j].y;
                if (pre_x == curr_x && pre_y == curr_y) {
                    overlap++;
                }
                else {
                    int delta_x = pre_x - curr_x;
                    int delta_y = pre_y - curr_y;
                    int gcd = getGCD(delta_x, delta_y);
                    if (gcd != 0) {
                        delta_x /= gcd;
                        delta_y /= gcd;
                    }
                    if (map.containsKey(delta_x)) {
                        if (map.get(delta_x).containsKey(delta_y)) {
                            map.get(delta_x).put(delta_y, map.get(delta_x).get(delta_y) + 1);
                        }
                        else {
                            map.get(delta_x).put(delta_y, 1);
                        }
                    }
                    else {
                        map.put(delta_x, new HashMap<Integer, Integer>());
                        map.get(delta_x).put(delta_y, 1);
                    }
                    max = Math.max(max, map.get(delta_x).get(delta_y));
                }
            }
            result = Math.max(result, max + overlap + 1);
        }
        return result;
    }
    
    private int getGCD(int a, int b) {
        if (b == 0) {
            return a;
        }
        else {
            return getGCD(b, a % b);
        }
    }
}

reference:
https://discuss.leetcode.com/topic/2979/a-java-solution-with-notes/2

这道题目没能做出来。是真的没想到 HashMap 还可以自动把点归成线。

假设 (x1, y1) (x2, y2) 在一条直线上 y = ax + b
y1 = ax1 + b
y2 = ax2 + b
=>
(y2 - y1) = a * (x2 - x1)
(y2 - y1) / (x2 - x1) = a, x2 - x1 != 0

所以如果给定三个点，(x1, y1) (x2, y2) (x3, y3)

算出：
k21 = gcd( (y2 - y1), (x2 - x1) );
k31 = gcd( (y3 - y1), (x3 - x1) );
===>
( y2 - y1 ) / k21 = ( y3 - y1 ) / k31 = delta_y
( x2 - x1 ) / k21 = ( x3 - x1 ) / k31 = delta_x
===>
我们以 (delta_x, delta_y) 为key， 来区分每一条线。
如果两个点在一条直线上，他们的 (delta_x, delta_y) 一定是固定的。

所以我们从以每个点为基准，然后遍历他之后的点。
算出在哪条直线上，点最多。
所以我们是两级 HashMap, 第二级的value，就是这条直线上点的个数。

当时我的以为是：
1 . 如果两个点，他们的 x,y 符号不同，会影响 delta_x, delta_y吗？这时候 delta_x, delta_y 对于特定的直线上的任意两点，还是固定的吗？做了几次实验后，发现是不变的。

2 . 如果 x2 - x1 = 0, 这个方法还管用吗？
gcd(0, 3) = 3
0/3 = 0;
3/3 = 1;
==>
(0,3) -> (0,1)
是不会有影响的。

下次做，很难有把握一次性做出来。
但是这个思路得记住。利用一些不变的东西来标志每条直线，以及在直线上的点的个数。
还有，记住如何求两个数的最大公约数。

Anyway, Good luck, Richardo! -- 09/22/2016