几个易错点149. Max Points on a Line

• gcd的计算
  记忆，gcd(a,b) = gcd(b, a%b) if (b == 0) return a写的话记一下就好了：

    int gcd(int a, int b){
      if (b == 0){
        return a;
      } else {
        return gcd(b, a%b);
      }
    }

• samePoints遇到如何处理，为何初始化为1
  因为我们统计samePoints是从points[i]开始的，也就是outer loop. 所以我们可以想得到用到它来更新res肯定是每一轮outer for loop结束的时候。一开始初始化为1，是因为我们在计算max的时候没有计算points[i]，在选定i循环j的时候遇到与points[i]共点的情况我们就会increment maxPoints.所以最后更新res的时候我们要用max + samePoints来表示现在这个点出发所能找到的最多共线点。

• max为何初始化为0， 并且为何在inner for loop更新
  max指的是选定出发点points[i]之后，所能找到的最多共线点。（不包括出发点points[i],所以初始化为零。 在inner loop更新是因为我们找max是在确定出发点points[i]的基础上，看看后面这些j > i的points[j]最多能在哪条斜率上出现共线最多的情况，所以只在内部循环更新。

• res为何在outer for loop更新
  因为每一次更新res的时候，一定是我们计算出了当前点为出发点所能共线的最多的点，又因为出发点实际上是outer loop的i, 所以我们要在outer loop更新最后的结果。核心就是搞清楚找到最多的共线点实际上就是找到以某个点作为出发点所能共线的最多点，也就是找到那个出发点。

• map为何每更换一个点需要重建
  因为每一次我们记录同一个斜率所涉及到的共线点，都是从不同的点出发才开始统计的。因为如果不这样，我们可能会遇到两组点，斜率相同，但完全不共线。如果不重新建map的话，就会发现这个斜率的共线点特别多，但事实又完全不是。

image.png

/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */
class Solution {
    public int maxPoints(Point[] points) {
        if (points == null || points.length == 0){
            return 0;
        }
        Map<String, List<Point>> slopes = new HashMap<>();
        int res = 0;
        for (int i = 0; i < points.length; i++){
            //starting from different points, could be same slope but they are not in a line
            slopes = new HashMap<String, List<Point>>();
            int samePoints = 1;
            int max = 0;
            for (int j = i + 1; j < points.length; j++){
                int deltaY = points[j].y - points[i].y;
                int deltaX = points[j].x - points[i].x;
                if (deltaY == 0 && deltaX == 0){
                    samePoints++;
                    continue;
                }
                int gcd = getGCD(deltaX, deltaY);
                deltaY /= gcd;
                deltaX /= gcd;
                String slope = deltaY + ":" + deltaX;
                if (!slopes.containsKey(slope)){
                    slopes.put(slope, new ArrayList<Point>());
                }
                slopes.get(slope).add(points[j]);
                max = Math.max(max, slopes.get(slope).size());
            }
            res = Math.max(res, max + samePoints);
        }
        return res;
    }

    private int getGCD(int a, int b){
        if (b == 0){
            return a;
        } else {
            return getGCD(b, a % b);
        }
    }
}