Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commite47947e

Browse files
committed
149 (1) finally breakthrough
1 parent11a0fde commite47947e

File tree

6 files changed

+597
-97
lines changed

6 files changed

+597
-97
lines changed
Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
/**
2+
*************************************************************************
3+
* Description:
4+
*
5+
* Given n points on a 2D plane, find the maximum number of points that
6+
* lie on the same straight line.
7+
*
8+
*************************************************************************
9+
* @tag : Hash Table; Math
10+
* {@link https://leetcode.com/problems/max-points-on-a-line/ }
11+
*/
12+
package_149_MaxPointsOnALine;
13+
14+
importcom.leetcode.Point;
15+
16+
/** see test {@link _149_MaxPointsOnALine.PracticeTest } */
17+
publicclassPractice {
18+
19+
publicintmaxPoints(Point[]points) {
20+
// TODO Auto-generated method stub
21+
return0;
22+
}
23+
24+
}
Lines changed: 28 additions & 80 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,5 @@
11
/**
2-
* Time : O(); Space : O()
2+
* Time : O(N^2); Space : O(N)
33
* @tag : Hash Table; Math
44
* @by : Steven Cooks
55
* @date: Jul 2, 2015
@@ -14,96 +14,44 @@
1414
*/
1515
package_149_MaxPointsOnALine;
1616

17-
importjava.util.ArrayList;
1817
importjava.util.HashMap;
19-
importjava.util.HashSet;
20-
importjava.util.List;
2118
importjava.util.Map;
22-
importjava.util.Set;
2319

2420
importcom.leetcode.Point;
2521

2622
/** see test {@link _149_MaxPointsOnALine.SolutionTest } */
2723
publicclassSolution {
28-
publicintmaxPoints(Point[]points) {
29-
if (points.length ==0) {
30-
return0;
31-
}
32-
Map<String,Set<String>>lineMap =newHashMap<>();
33-
34-
List<String>unique =newArrayList<>();
35-
Map<String,Integer>pointMap =newHashMap<>();
36-
// count the points
37-
for (Pointpoint :points) {
38-
intcount =1;
39-
StringpStr =pointToString(point);
40-
if (pointMap.containsKey(pStr)) {
41-
count =1 +pointMap.get(pStr);
42-
}else {
43-
unique.add(pStr);
44-
}
45-
pointMap.put(pStr,count);
46-
}
47-
// System.out.println(pointMap);
48-
if (pointMap.size() ==1) {
49-
returnpointMap.get(pointToString(points[0]));
50-
}
5124

52-
for (inti =0;i <unique.size();i++) {
53-
Pointp1 =strToPoint(unique.get(i));
54-
for (intj =i +1;j <unique.size();j++) {
55-
Pointp2 =strToPoint(unique.get(j));
56-
// calculate the <k, b> for each two points
57-
doublek =0;
58-
doubleb =0;
59-
if (p1.x ==p2.x) {
60-
k =Integer.MAX_VALUE;
61-
b =p1.x;
62-
}else {
63-
k = (p2.y -p1.y) / (p2.x -p1.x);
64-
b = (p2.x *p1.y -p1.x *p2.y) / (p2.x -p1.x);
25+
publicintmaxPoints(Point[]points) {
26+
intres =0;
27+
for (inti =0;i <points.length;i++) {
28+
// slope, count of points in this slop except those overlapping points with points[i]
29+
Map<Double,Integer>slopeMap =newHashMap<>();
30+
intsamePoint =1;// points at the same position
31+
intsameX =0;// points share the same x value except points at the
32+
// same position as points[i]
33+
for (intj =0;j <points.length;j++) {
34+
if (i !=j) {
35+
if (points[i].x ==points[j].x
36+
&&points[i].y ==points[j].y) {
37+
samePoint++;
38+
}elseif (points[i].x ==points[j].x) {
39+
sameX++;
40+
}else {
41+
doublek = (double) (points[j].y -points[i].y)
42+
/ (points[j].x -points[i].x);
43+
intcounts =1;
44+
if (slopeMap.containsKey(k)) {
45+
counts +=slopeMap.get(k);
46+
}
47+
slopeMap.put(k,counts);
48+
res =Math.max(res,counts +samePoint);
49+
}
6550
}
66-
Stringline =pointToString(k,b);
67-
Set<String>pSet =newHashSet<>();
68-
if (lineMap.containsKey(line)) {
69-
pSet =lineMap.get(line);
70-
}
71-
pSet.add(pointToString(p1));
72-
pSet.add(pointToString(p2));
73-
lineMap.put(line,pSet);
7451
}
52+
res =Math.max(res,samePoint +sameX);
7553
}
76-
// System.out.println(lineMap);
77-
78-
// find the result
79-
intresult =0;
80-
for (Stringline :lineMap.keySet()) {
81-
// System.out.println("-------------" + line + "-------------");
82-
intcount =0;
83-
Set<String>pointSet =lineMap.get(line);
84-
for (Stringp :pointSet) {
85-
// System.out.println(p + ", " + pointMap.get(p));
86-
count +=pointMap.get(p);
87-
}
88-
result =Math.max(result,count);
89-
}
90-
returnresult;
91-
}
92-
93-
privateStringpointToString(doublek,doubleb) {
94-
return"[" +k +"," +b +"]";
95-
}
96-
97-
privateStringpointToString(Pointp) {
98-
return"[" +p.x +"," +p.y +"]";
99-
}
100-
101-
privatePointstrToPoint(Stringstr) {
102-
intcommaIndex =str.indexOf(",");
103-
intx =Integer.parseInt(str.substring(1,commaIndex));
104-
inty =Integer.parseInt(str.substring(commaIndex +1,str.length() -1));
105-
Pointpoint =newPoint(x,y);
106-
returnpoint;
54+
returnres;
10755
}
10856

10957
}
Lines changed: 64 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,64 @@
1+
/**
2+
* Time : O(N^2); Space : O(N)
3+
* @tag : Hash Table; Math
4+
* @by : Steven Cooks
5+
* @date: Jul 2, 2015
6+
*************************************************************************
7+
* Description:
8+
*
9+
* Given n points on a 2D plane, find the maximum number of points that
10+
* lie on the same straight line.
11+
*
12+
*************************************************************************
13+
* {@link https://leetcode.com/problems/max-points-on-a-line/ }
14+
*/
15+
package_149_MaxPointsOnALine;
16+
17+
importjava.util.Arrays;
18+
importjava.util.Comparator;
19+
importjava.util.HashMap;
20+
importjava.util.Map;
21+
22+
importcom.leetcode.Point;
23+
24+
/** see test {@link _149_MaxPointsOnALine.SolutionSortTest } */
25+
publicclassSolutionSort {
26+
27+
// version2: sort points first, so that we can use loop for (int j = i + 1,
28+
// instead of for (int j = 0, ...
29+
publicintmaxPoints(Point[]points) {
30+
intres =0;
31+
32+
Arrays.sort(points,newComparator<Point>() {
33+
@Override
34+
publicintcompare(Pointp1,Pointp2) {
35+
returnp1.x !=p2.x ?p1.x -p2.x :p1.y -p2.y;
36+
}
37+
});
38+
39+
for (inti =0;i <points.length;i++) {
40+
Map<Double,Integer>slopeMap =newHashMap<>();
41+
intsamePoint =1;
42+
intsameX =0;
43+
for (intj =i +1;j <points.length;j++) {
44+
if (points[i].x ==points[j].x &&points[i].y ==points[j].y) {
45+
samePoint++;
46+
}elseif (points[i].x ==points[j].x) {
47+
sameX++;
48+
}else {
49+
doublek = (double) (points[j].y -points[i].y)
50+
/ (points[j].x -points[i].x);
51+
intcounts =1;
52+
if (slopeMap.containsKey(k)) {
53+
counts +=slopeMap.get(k);
54+
}
55+
slopeMap.put(k,counts);
56+
res =Math.max(res,counts +samePoint);
57+
}
58+
}
59+
res =Math.max(res,samePoint +sameX);
60+
}
61+
returnres;
62+
}
63+
64+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp