给定二维平面上有 n 个点，求最多有多少点在同一条直线上。
详见：https://leetcode.com/problems/max-points-on-a-line/description/
Java实现：
/**
* 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);
}
}
}
参考：https://www.jianshu.com/p/0073d059687d