My code:
/**
* Definition for a point.
* class Point {
* int x;
* int y;
* Point() { x = 0; y = 0; }
* Point(int a, int b) { x = a; y = b; }
* }
*/
public class Solution {
public int maxPoints(Point[] points) {
if (points == null || points.length == 0) {
return 0;
}
HashMap<Integer, Map<Integer, Integer>> map = new HashMap<Integer, Map<Integer, Integer>>();
int result = 0;
for (int i = 0; i < points.length; i++) {
int max = 0;
int overlap = 0;
int pre_x = points[i].x;
int pre_y = points[i].y;
map.clear();
for (int j = i + 1; j < points.length; j++) {
int curr_x = points[j].x;
int curr_y = points[j].y;
if (pre_x == curr_x && pre_y == curr_y) {
overlap++;
}
else {
int delta_x = pre_x - curr_x;
int delta_y = pre_y - curr_y;
int gcd = getGCD(delta_x, delta_y);
if (gcd != 0) {
delta_x /= gcd;
delta_y /= gcd;
}
if (map.containsKey(delta_x)) {
if (map.get(delta_x).containsKey(delta_y)) {
map.get(delta_x).put(delta_y, map.get(delta_x).get(delta_y) + 1);
}
else {
map.get(delta_x).put(delta_y, 1);
}
}
else {
map.put(delta_x, new HashMap<Integer, Integer>());
map.get(delta_x).put(delta_y, 1);
}
max = Math.max(max, map.get(delta_x).get(delta_y));
}
}
result = Math.max(result, max + overlap + 1);
}
return result;
}
private int getGCD(int a, int b) {
if (b == 0) {
return a;
}
else {
return getGCD(b, a % b);
}
}
}
reference:
https://discuss.leetcode.com/topic/2979/a-java-solution-with-notes/2
这道题目没能做出来。是真的没想到 HashMap 还可以自动把点归成线。
假设 (x1, y1) (x2, y2) 在一条直线上 y = ax + b
y1 = ax1 + b
y2 = ax2 + b
=>
(y2 - y1) = a * (x2 - x1)
(y2 - y1) / (x2 - x1) = a, x2 - x1 != 0
所以如果给定三个点，(x1, y1) (x2, y2) (x3, y3)
算出：
k21 = gcd( (y2 - y1), (x2 - x1) );
k31 = gcd( (y3 - y1), (x3 - x1) );
===>
( y2 - y1 ) / k21 = ( y3 - y1 ) / k31 = delta_y
( x2 - x1 ) / k21 = ( x3 - x1 ) / k31 = delta_x
===>
我们以 (delta_x, delta_y) 为key， 来区分每一条线。
如果两个点在一条直线上，他们的 (delta_x, delta_y) 一定是固定的。
所以我们从以每个点为基准，然后遍历他之后的点。
算出在哪条直线上，点最多。
所以我们是两级 HashMap, 第二级的value，就是这条直线上点的个数。
当时我的以为是：
1 . 如果两个点，他们的 x,y 符号不同，会影响 delta_x, delta_y吗？这时候 delta_x, delta_y 对于特定的直线上的任意两点，还是固定的吗？做了几次实验后，发现是不变的。
2 . 如果 x2 - x1 = 0, 这个方法还管用吗？
gcd(0, 3) = 3
0/3 = 0;
3/3 = 1;
==>
(0,3) -> (0,1)
是不会有影响的。
下次做，很难有把握一次性做出来。
但是这个思路得记住。利用一些不变的东西来标志每条直线，以及在直线上的点的个数。
还有，记住如何求两个数的最大公约数。
Anyway, Good luck, Richardo! -- 09/22/2016
