由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - Leetcode上面的题Max Points on a Line
相关主题
用Python练习算法题冷冻期如何提高自己的解题水平?
大家怎么刷CC150leetcode OJ出新版了!
Max points on a line如果你碰上一个很弱的面试官怎么办
一道题:number of permutation是 for a total score你们不觉得leetcode的pass时间很诡异么,Java有这么慢么
请教一道题问下amazon的online test
哪里有cc150的testcase全集Leetcode的题能看到test cases么?
Max Points on a Line 最优解法是哪个?Leetcode oj 的"scramble string"
leetcode container with most water刷题神器
相关话题的讨论汇总
话题: point话题: maxcount话题: count话题: int话题: points
1 (共1页)
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
6
https://gist.github.com/zrqsmcx/7629207
这个比cc150 的解法好多了。
1 (共1页)
相关主题
刷题神器请教一道题
大家常说的cc150就是cracking code interview这本书吧?哪里有cc150的testcase全集
F,G,M offer 及 面试经历Max Points on a Line 最优解法是哪个?
G家悲剧了leetcode container with most water
用Python练习算法题冷冻期如何提高自己的解题水平?
大家怎么刷CC150leetcode OJ出新版了!
Max points on a line如果你碰上一个很弱的面试官怎么办
一道题:number of permutation是 for a total score你们不觉得leetcode的pass时间很诡异么,Java有这么慢么
相关话题的讨论汇总
话题: point话题: maxcount话题: count话题: int话题: points