o****i
发帖数: 1706 | 1 我写的是
/**
* Definition for a point.
* class Point {
* int x;
* int y;
* Point() { x = 0; y = 0; }
* Point(int a, int b) { x = a; y = b; }
* }
*/
public class Solution {
public int maxPoints(Point[] points) {
Point p1 = new Point();
Point p2 = new Point();
int maxCount = 0;
if(points.length == 1){
return 1;
}
for(int i=0;i
boolean isSame = true;
p1 = points[i];
for(int j=i+1;j
int count = 2;
p2 = points[j];
if(p1.x==p2.x && p1.y==p2.y){//skip if at same point
if(isSame){
for(int l=0; l
points are same
if(l!=i && l!=j){
Point checkP = points[l];
if(checkP.x == p1.x && checkP.y==p1.y){
count++;
}
}
if(count==points.length) return count;
isSame = false;
}
}
if(count>maxCount) maxCount = count;
continue;
}
else if(p1.x==p2.x){//x=p1.x
for(int l=0; l
if(l!=i && l!=j){
Point checkP = points[l];
if(checkP.x == p1.x){
count++;
}
}
}
if(count>maxCount) maxCount = count;
}
else if(p1.y==p2.y){//y=p1.y
for(int l=0; l
if(l!=i && l!=j){
Point checkP = points[l];
if(checkP.y == p1.y){
count++;
}
}
}
if(count>maxCount) maxCount = count;
}
else{
double k = (double)(p2.y-p1.y)/(p2.x-p1.x);//slope rate
double b = (double)p1.y-(double)k*p1.x;
for(int l=0; l
if(l!=i && l!=j){
Point checkP = points[l];
if(checkP.y == (k*checkP.x+b)){
count++;
}
}
}
if(count>maxCount) maxCount = count;
}
}
}
return maxCount;
}
}
出现错误
Input: [(-54,-297),(-36,-222),(3,-2),(30,53),(-5,1),(-36,-222),(0,2),(1,
3),(6,-47),(0,4),(2,3),(5,0),(48,128),(24,28),(0,-5),(48,128),(-12,-122),(-
54,-297),(-42,-247),(-5,0),(2,4),(0,0),(54,153),(-30,-197),(4,5),(4,3),(-42,
-247),(6,-47),(-60,-322),(-4,-2),(-18,-147),(6,-47),(60,178),(30,53),(-5,3),
(-42,-247),(2,-2),(12,-22),(24,28),(0,-72),(3,-4),(-60,-322),(48,128),(0,-72
),(-5,3),(5,5),(-24,-172),(-48,-272),(36,78),(-3,3)]
Output: 27
Expected: 30
有人可以帮我看看问题出在哪吗？ | n******n
发帖数: 12088 | 2 自己debug
【在 o****i 的大作中提到】
: 我写的是
: /**
: * Definition for a point.
: * class Point {
: * int x;
: * int y;
: * Point() { x = 0; y = 0; }
: * Point(int a, int b) { x = a; y = b; }
: * }
: */
| s**x
发帖数: 7506 | 3 Did you try the solution from cc150? That book has this question.
You are finding a line, then check all other points on this line or not, I
think the complexity is too high.
I think the key is to hash a line to a hashmap, then calculate number of
lines in each hash entry,
Special treat for vertical lines, no need to check duplicate points, it
should be automatically covered.
The code should not be that long. | o****i
发帖数: 1706 | 4 ok, thanks
【在 s**x 的大作中提到】
: Did you try the solution from cc150? That book has this question.
: You are finding a line, then check all other points on this line or not, I
: think the complexity is too high.
: I think the key is to hash a line to a hashmap, then calculate number of
: lines in each hash entry,
: Special treat for vertical lines, no need to check duplicate points, it
: should be automatically covered.
: The code should not be that long.
| c**********y
发帖数: 38 | 5 楼主，我没看你代码只看了testcase，我发现case里面有两组重复的点，两个（-36，-
222），三个（48,128），正好重复的少了3个结果，如果我猜的没错你应该是没有把重
复的点当同一个点处理了，这个题同样坐标的点算两个点，因为求的是testcase里面在
一条线上点的个数而不是画完图后在一条线上点的个数，给楼主参考下。 | s**x
发帖数: 7506 | |
|
