解决思路

Map

一句话解释: 固定一点, 找其他点和这个点组成直线, 统计他们的斜率!

这里有一个重点: 求斜率.用两种方法

1. 用最大约数方法(gcd), 把他化成最简形式, 3/6 == 2/4 == 1/2
2. 除数(不太精确, 速度快!)

  public int gcd(int dy,int dx){
        if(dx == 0)
            return dy;
        else
            return gcd(dx,dy%dx);
    }
   public int maxPoints(int[][] points){
       int n = points.length;
       if(n==0) return 0;
       if(n==1) return 1;
       int res = 0;
       for(int i = 0;i<n-1;i++){
           Map<String,Integer> slope = new HashMap<>();
           int repeat = 0;
           int tmp_max = 0;
           for(int j = i+1;j<n;j++){
               int dy = points[i][1] - points[j][1];
               int dx = points[i][0] - points[j][0];
               if(dy == 0 && dx == 0)
               {
                   repeat++;
                   continue;
               }
               int g = gcd(dy,dx);
               if(g!=0){
                   dy /= g;
                   dx /= g;
               }
               String tmp = String.valueOf(dy) + "/" + String.valueOf(dx);
               slope.put(tmp,slope.getOrDefault(tmp,0)+1);
               tmp_max = Math.max(tmp_max,slope.get(tmp));
           }
           res = Math.max(res,repeat+tmp_max+1);
       }
       return res;
   }