Hard
关于samePoints, max, res之间的关系：
image.png
这里还要介绍一下如何计算两个整数的最大公约数，也就是gcd, 这里用的是欧几里得算法：
- 基本的Euclidean algorithms， 求a,b的gcd, 就等于求较小数和大数减小数的差的gcd, 知道有一个数等于0，剩下的另一个不为零的数就是gcd;
- 扩展的Euclidean algorithms，求a,b的gcd， 这次不减去小数，而是除以小数取余数，直到取到余数等于0时。
public int gcd(int a, int b){
if (b == 0){
return a;
} else {
return gcd(b, a%b);
}
}
/**
* 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, Integer> map = new HashMap<>();
int res = 0;
for (int i = 0; i < points.length; i++){
map = new HashMap<>();
int samePoints = 1;
int max = 0;
for (int j = i + 1; j < points.length; j++){
if (points[j].y == points[i].y && points[j].x == points[i].x){
samePoints++;
continue;
}
int deltaY = points[j].y - points[i].y;
int deltaX = points[j].x - points[i].x;
int gcd = gcd(deltaY, deltaX);
deltaY /= gcd;
deltaX /= gcd;
String slope = deltaY+"/"+deltaX;
map.put(slope, map.getOrDefault(slope, 0) + 1);
max = Math.max(max, map.get(slope));
}
res = Math.max(res, max + samePoints);
}
return res;
}
private int gcd(int a, int b){
if (b == 0){
return a;
} else {
return gcd(b, a % b);
}
}
}
