forked from rpj911/LeetCode_algorithm
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathLine.java
More file actions
109 lines (85 loc) · 3.01 KB
/
Line.java
File metadata and controls
109 lines (85 loc) · 3.01 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
package Algorithms;
import java.util.Comparator;
import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.Queue;
public class Line {
/*
private Comparator<ListNode> ListNodeComparator = new Comparator<ListNode>() {
public int compare(ListNode left, ListNode right) {
if (left == null) {
return 1;
} else if (right == null) {
return -1;
}
return left.val - right.val;
}
};*/
public class ListNodeComparator implements Comparator<ListNode>{
public int compare(ListNode left, ListNode right) {
if (left == null) {
return 1;
} else if (right == null) {
return -1;
}
return left.val - right.val;
}
}
public static void main(String[] args) {
Line li = new Line();
Point p1 = new Point(2, 3);
Point p2 = new Point(3, 3);
Point p3 = new Point(-5, 3);
Point[] p = {p1, p2, p3};
li.maxPoints(p);
Line aa = new Line();
Queue<ListNode> heap = new PriorityQueue<ListNode>(2, aa.new ListNodeComparator());
}
public int maxPoints(Point[] points) {
if (points == null || points.length == 0) {
return 0;
}
Queue<ListNode> heap = new PriorityQueue<ListNode>(2, new ListNodeComparator());
double k;
int dup = 0;
int max = 0;
for (int i = 0; i < points.length; i++) {
HashMap<Double, Integer> map = new HashMap<Double, Integer>();
// the point itself.
dup = 1;
for (int j = i + 1; j < points.length; j++) {
if (points[j].y == points[i].y && points[i].x == points[j].x) {
// the same point with the point.
dup++;
continue;
}
// count the K.
if (points[j].x == points[i].x) {
k = Double.MAX_VALUE;
} else {
// because there is +0 and -0.... so add 0 to it.
k = (double)(points[j].y - points[i].y)/(double)(points[j].x - points[i].x);
if (k == 0) {
k = 1;
}
if (-0 == 0){
k = 1;
}
}
if (map.containsKey(k)) {
map.put(k, map.get(k) + 1);
} else {
// the line has at least 2 numbers.
map.put(k, 1);
}
}
for (int n: map.values()) {
if (n + dup > max) {
max = n + dup;
}
}
max = Math.max(max, dup);
}
return max;
}
}