[LeetCode OJ] Max Points on a Line

Submission Details

27 / 27 test cases passed.
Status:

Accepted

Runtime: 472 ms
Submitted: 0 minutes ago

Submitted Code

Language: java
  Edit 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; }
* }
*/
import java.util.HashMap;
import java.util.Map; public class Solution {
public int maxPoints(Point[] points) {
if (points == null || points.length == 0)
return 0;
int N = points.length;
if (N == 1)
return 1;
if (N == 2)
return 2; Map<String, Integer> dict = new HashMap<String, Integer>();
int maxOverall = 0;
for (int i = 0; i < N - 1; i++) {
int same = 1;
int max = 0;
for (int j = i + 1; j < N; j++) { int p1x = points[i].x;
int p1y = points[i].y;
int p2x = points[j].x;
int p2y = points[j].y; if (p1x == p2x && p1y == p2y) {
same++;
continue;
} int A = p2y - p1y;
int B = p1x - p2x; int GCD = gcd(A, B);
if (GCD != 0 && GCD != 1) {
A /= GCD;
B /= GCD;
}
if (A < 0) {
A = -A;
B = -B;
} String key = A + "," + B;
// System.out.println("round:" + i + " " + key);
int value = 1;
if (dict.containsKey(key)) {
value += dict.get(key);
}
dict.put(key, value);
max = max < value ? value : max;
} max += same;
maxOverall = maxOverall < max ? max : maxOverall;
dict.clear();
} return maxOverall;
} public int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
}
 
 
 
 
上一篇:超级简单却不知道:html标签的嵌套规则


下一篇:LeetCode: Max Points on a Line 解题报告