149. Max Points on a Line

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

本题是比较难的题目，首先需要弄懂一点，就是最大公约数是最大的可整除数，也就是默认为k值（y=kx+b），然后用两个hashmap来存储（x，map），（y，number）值，再这里面要排除掉overlap的值，因此还需要用一个overlap的变量来记录相同的值。当然，本身的点也没有算进去，因此，总的result=max+1+overlap。代码如下：

 1 /**
 2  * Definition for a point.
 3  * class Point {
 4  *     int x;
 5  *     int y;
 6  *     Point() { x = 0; y = 0; }
 7  *     Point(int a, int b) { x = a; y = b; }
 8  * }
 9  */
10 public class Solution {
11     public int maxPoints(Point[] points) {
12         Map<Integer,Map<Integer,Integer>> map = new HashMap<>();
13         if(points==null) return 0;
14         int result = 0;
15         if(points.length<=2) return points.length;
16         for(int i=0;i<points.length;i++){
17             map.clear();
18             int max  =0;
19             int overlap = 0;
20             for(int j=i+1;j<points.length;j++){
21                 int x = points[j].x-points[i].x;
22                 int y = points[j].y-points[i].y;
23                 if(x==0&&y==0){
24                     overlap++;
25                     continue;
26                 } 
27                 int gcd = GCD(x,y);
28                 if(gcd!=0){
29                     x = x/gcd;
30                     y = y/gcd;   
31                 }
32                 if(map.containsKey(x)){
33                     if(map.get(x).containsKey(y)){
34                         map.get(x).put(y,map.get(x).get(y)+1);
35                     }else{
36                         map.get(x).put(y,1);
37                     }
38                 }else{
39                     Map<Integer,Integer> m = new HashMap<Integer,Integer>();
40                     m.put(y,1);
41                     map.put(x,m);
42                 }
43                 max = Math.max(max,map.get(x).get(y));
44             }
45             result = Math.max(result,max+1+overlap);
46         }
47         return result;
48     }
49     public int GCD(int a,int b){
50         if(b==0) return a;
51         return GCD(b,a%b);
52     }
53 }

做这道题目要注意gcd不能为0；还有x=0，y=0的时候就要跳出循环；