leetcode 149 --- Max Points on a line

（另外一种方法是把所有直线用A, B 两个参数来表示， 然后遍历所有直线，用HashMap计数）
我采用的是“定出发点，找斜率相同直线”的方法，思路类似。

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.         if (points == null) {
    
13.             return 0;
    
14.         }
    
15.         int maxPoints = 0;
    
16.         int n = points.length;
    
17.         // store the number of points on a particular
    
18.         HashMap<Double, Integer> map;
    
19.         for (int i = 0; i < n; ++i) {
    
20.             map = new HashMap<>();
    
21.             int samePoints = 0;
    
22.             int maxSameLines = 0;
    
23.             for (int j = i + 1; j < n; ++j) {
    
24.                 if (points[i].x == points[j].x && points[i].y == points[j].y) {
    
25.                     samePoints++;
    
26.                     continue;
    
27.                 }
    
28.                 double gradient = 0.0;
    
29.                 if (points[i].y != points[j].y)
    
30.                         gradient = points[i].x == points[j].x ? Double.MAX_VALUE : (double)(points[j].y - points[i].y) / (double)(points[j].x - points[i].x);
    
31. 
    
32.                 //use and update the map;
    
33.                 if (map.containsKey(gradient)) {
    
34.                     map.put(gradient, map.get(gradient) + 1);
    
35.                 } else {
    
36.                     map.put(gradient, 1);
    
37.                 }
    
38.                 maxSameLines = Math.max(maxSameLines, map.get(gradient));
    
39.             }
    
40.             maxPoints = Math.max(maxPoints, maxSameLines + samePoints + 1);
    
41.         }
    
42.         return maxPoints;
    
43.     }
    
44. }

复制代码