LeetCode: Max Points on a Line 解题报告

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.

LeetCode: Max Points on a Line 解题报告

SOLUTION 1:

全部的点扫一次,然后计算每一个点与其它点之间的斜率。

创建一个MAP, KEY-VALUE是 斜率:线上的点的数目。

另外,注意重合的点,每次都要累加到每一条线上。

注意:

1. k = 0 + (double)(points[i].y - points[j].y)/(double)(points[i].x - points[j].x);

使用这个公式来计算的原因是 (double)(points[i].y - points[j].y)/(double)(points[i].x - points[j].x) 有可能计算出0和-0

0+(-0)后,就会都变成0.

2. 用Dup来计算重合的点。

3. 如果某点开始所有的点都在一起,则至少Max = Math.max(max, duplicate)。

4. 注意每次换一个点计算时,map要重建。因为即使K相同,只代表线是平等,不代表会是同一条线。

 public class Solution {
public int maxPoints(Point[] points) {
int max = ; if (points == null) {
return ;
} int len = points.length; for (int i = ; i < len; i++) {
// Create a map to recode all the numbers of elements of every K.
HashMap<Double, Integer> map = new HashMap<Double, Integer>(); // ItSelf.
int dup = ; for (int j = i; j < len; j++) {
// the same point.
if (points[i].x == points[j].x && points[i].y == points[j].y) {
dup++;
continue;
} double k = Double.MAX_VALUE;
if (points[i].x != points[j].x) {
k = + (double)(points[i].y - points[j].y)/(double)(points[i].x - points[j].x);
} if (map.containsKey(k)) {
map.put(k, map.get(k) + );
} else {
map.put(k, );
}
} max = Math.max(max, dup);
for (int n: map.values()) {
max = Math.max(max, n + dup);
}
} return max;
}
}

主页君的GitHub:

https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/hash/MaxPoints.java

参考答案:

http://www.ninechapter.com/solutions/max-points-on-a-line/

上一篇:[LeetCode OJ] Max Points on a Line


下一篇:编译lua版本问题