8000 refactor 149 · ridixi/Leetcode@6bd7690 · GitHub
[go: up one dir, main page]
Skip to co 8000 ntent

Commit 6bd7690

Browse files
fishercoder1534fishercoder1534
committed
refactor 149
1 parent 132a4e1 commit 6bd7690

File tree

2 files changed

+98
-68
lines changed

2 files changed

+98
-68
lines changed

‎src/main/java/com/fishercoder/solutions/_149.java

Lines changed: 74 additions & 68 deletions
Original file line numberDiff line numberDiff line change
@@ -1,85 +1,91 @@
11
package com.fishercoder.solutions;
22

33
import com.fishercoder.common.classes.Point;
4+
import java.util.HashMap;
5+
import java.util.Map;
46

57
/**
8+
* 149. Max Points on a Line
9+
*
610
* Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
11+
*
12+
* Example 1:
13+
* Input: [[1,1],[2,2],[3,3]]
14+
* Output: 3
15+
* Explanation:
16+
* ^
17+
* |
18+
* | o
19+
* | o
20+
* | o
21+
* +------------->
22+
* 0 1 2 3 4
23+
*
24+
* Example 2:
25+
* Input: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
26+
* Output: 4
27+
* Explanation:
28+
* ^
29+
* |
30+
* | o
31+
* | o o
32+
* | o
33+
* | o o
34+
* +------------------->
35+
* 0 1 2 3 4 5 6
36+
*
737
*/
838
public class _149 {
939

40+
public static class Solution1 {
41+
/**credit: https://leetcode.com/problems/max-points-on-a-line/discuss/47113/A-java-solution-with-notes*/
1042
public int maxPoints(Point[] points) {
11-
int max = 0;
12-
if (points.length == 0) {
13-
max = 0;
14-
} else if (points.length == 1) {
15-
max = 1;
16-
} else if (points.length == 2) {
17-
max = 2;
18-
} else if (points.length == 3) {
19-
max = 2;
20-
if ((points[0].x - points[1].x) * (points[1].y - points[2].y) == (points[0].y - points[1].y)
21-
* (points[1].x - points[2].x)) {
22-
max++;
23-
}
24-
} else {
25-
int[][] maxPoints = new int[points.length][points.length];
26-
for (int i = 0; i < points.length; i++) {
27-
for (int j = 0; j < points.length && j != i; j++) {
28-
maxPoints[i][j] = 2;
29-
// System.out.print(maxPoints[i][j] + " ");
30-
}
31-
}
43+
if (points == null) return 0;
44+
if (points.length <= 2) return points.length;
3245

33-
for (int i = 0; i < points.length; i++) {
34-
for (int j = 0; (j < points.length) && (j != i); j++) {
35-
if (((points[i].x == points[j].x) && (points[i].y == points[j].y))) {
36-
for (int k = 0; (k < points.length); k++) {
37-
if ((k != i) && (k != j)) {
38-
if (((points[k].x == points[i].x) && (points[k].y == points[i].y))) {
39-
maxPoints[i][j]++;
40-
}
41-
}
42-
}
43-
} else {
44-
for (int k = 0; (k < points.length); k++) {
45-
/*
46-
* Here, I must put the judgment (k!=i) && (k!=j) in the
47-
* if statement instead of in the for, otherwise, when k
48-
* equals i or j, it will stop traversing the rest of
49-
* the points that k represents!
50-
*
51-
* This is the key to solving this problem and Siyuan
52-
* Song helped me spot this error!
53-
*
54-
* It took me an hour and couldn't find any clue!
55-
*/
56-
if ((k != i) && (k != j)) {
57-
if (((points[k].x == points[i].x) && (points[k].y == points[i].y))) {
58-
maxPoints[i][j]++;
59-
} else if (((points[k].x == points[j].x) && (points[k].y == po 67F4 ints[j].y))) {
60-
maxPoints[i][j]++;
61-
} else if ((points[i].x - points[j].x)
62-
* (points[k].y - points[j].y) == (points[i].y - points[j].y)
63-
* (points[k].x - points[j].x)) {
64-
maxPoints[i][j]++;
46+
Map<Integer, Map<Integer, Integer>> map = new HashMap<>();
47+
int result = 0;
48+
for (int i = 0; i < points.length; i++) {
49+
map.clear();
50+
int overlap = 0, max = 0;
51+
for (int j = i + 1; j < points.length; j++) {
52+
int x = points[j].x - points[i].x;
53+
int y = points[j].y - points[i].y;
54+
if (x == 0 && y == 0) {
55+
overlap++;
56+
continue;
57+
}
58+
int gcd = generateGCD(x, y);
59+
if (gcd != 0) {
60+
x /= gcd;
61+
y /= gcd;
62+
}
6563

66-
}
67-
}
68-
}
69-
}
70-
}
71-
}
72-
for (int m = 0; m < points.length; m++) {
73-
for (int n = 0; n < points.length; n++) {
74-
if (maxPoints[m][n] > max) {
75-
// System.out.print("maxPoints[" + m + "][" + n +"]:" +
76-
// maxPoints[m][n] + "\t");
77-
max = maxPoints[m][n];
78-
}
79-
}
64+
if (map.containsKey(x)) {
65+
if (map.get(x).containsKey(y)) {
66+
map.get(x).put(y, map.get(x).get(y) + 1);
67+
} else {
68+
map.get(x).put(y, 1);
8069
}
70+
} else {
71+
Map<Integer, Integer> m = new HashMap<>();
72+
m.put(y, 1);
73+
map.put(x, m);
74+
}
75+
max = Math.max(max, map.get(x).get(y));
8176
}
82-
return max;
77+
result = Math.max(result, max + overlap + 1);
78+
}
79+
return result;
8380
}
8481

82+
private int generateGCD(int a, int b) {
83+
84+
if (b == 0) {
85+
return a;
86+
} else {
87+
return generateGCD(b, a % b);
88+
}
89+
}
90+
}
8591
}

‎src/test/java/com/fishercoder/_149Test.java

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
package com.fishercoder;
2+
3+
import com.fishercoder.common.classes.Point;
4+
import com.fishercoder.solutions._149;
5+
import org.junit.BeforeClass;
6+
import org.junit.Test;
7+
8+
import static org.junit.Assert.assertEquals;
9+
10+
public class _149Test {
11+
private static _149.Solution1 solution1;
12+
private static Point[] points;
13+
14+
@BeforeClass
15+
public static void setup() {
16+
solution1 = new _149.Solution1();
17+
}
18+
19+
@Test
20+
public void test1() {
21+
points = new Point[] {new Point(0, 0), new Point(1, 65536), new Point(65536, 0)};
22+
assertEquals(2, solution1.maxPoints(points));
23+
}
24+
}

0 commit comments

Comments
 (0)
0