# boards

JobHunting版 - Leetcode上面的题Max Points on a Line

Max points on a line如果你碰上一个很弱的面试官怎么办

Max Points on a Line 最优解法是哪个？Leetcode oj 的"scramble string"
leetcode container with most water刷题神器

 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 3Did 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 4ok, 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 6https://gist.github.com/zrqsmcx/7629207 这个比cc150 的解法好多了。
 1 (共1页)

F,G,M offer 及 面试经历Max Points on a Line 最优解法是哪个？
G家悲剧了leetcode container with most water

Max points on a line如果你碰上一个很弱的面试官怎么办