由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - Leetcode 新题max points on a line
相关主题
讨论一下给定平面上n点,求在同一直线上最多点问题~~大家用double /float 类型作hash key么GOOGLE 第二轮电面
lc里面那个max points O(n3)的算法也不慢啊C++ Q83: 这个const_cast什么意思?
被简单题给虐了。发个论坛上某已经淡出隐牛的一道Google Onsite概率题
给一堆points, 找到所有给定长度的正方形Max Points on a Line 用c++map老是没法compile
报个上周L家的onsite,已挂。继续为第6个onsite准备Zenefits 电面1
Interview questions: points lie on same line大数据,机器学习公司就是狗屎啊
interview question:找包含点数最多的线段问个题目,好像以前有人问过~~~
Caeercup150 原题:Find a line passes most points再贴这道算法题,寻答案,有包子送
相关话题的讨论汇总
话题: point话题: int话题: line话题: return话题: points
1 (共1页)
D****6
发帖数: 278
1
这题怎么做?算slope和yintercept,再用个hashmap count.怎么count比较好?而且好
像同一个点不能只算一次,count起来比较复杂。有什么简单做法没?
z****e
发帖数: 54598
2
看题目就感觉要dp了
l*n
发帖数: 529
3
没有,不是dp,就是cc150的题。

【在 z****e 的大作中提到】
: 看题目就感觉要dp了
s********u
发帖数: 1109
4
struct Line{

double slope;
double intercept;


Line(Point p, Point q){

if(p.x == q.x){
slope = numeric_limits::max();
intercept = p.x;
}else{
slope = (double)(p.y - q.y)/(double)(p.x - q.x);
intercept = p.y - slope * p.x;
}
}
};
struct Comp{

static double eps;

bool operator()( const Line &l1, const Line &l2){

if( l1.slope - l2.slope < -eps )
return true;

if( l1.slope - l2.slope > eps)
return false;

return (l1.intercept - l2.intercept < -eps);

}

};
double Comp::eps = 0.000000001;
bool fitLine(const Point& p,const Line &line){

if( abs(line.slope - numeric_limits::max()) < 0.000000001 )
return p.x == (int)line.intercept;

return abs(p.x * line.slope + line.intercept - p.y) < 0.000000001;


}

class Solution {
public:
int maxPoints(vector &points) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.

if(points.empty()) return 0;

map table;

for(int i = 0; i < points.size(); i++)
for(int j = i+1; j < points.size();j++){

Line local(points[i],points[j]);
table[local]++;

}

int maxcnt = 1;

auto maxLine = table.begin();

for(auto it = table.begin(); it != table.end(); ++it )
if( it->second > maxcnt){
maxcnt = it->second;
maxLine = it;
}

maxcnt = 0;

for(int i = 0; i < points.size();i++){

if(fitLine(points[i],maxLine->first) )
maxcnt++;
}

return maxcnt;

}
};
h*********o
发帖数: 230
5
不要用slope 跟hashmap 做。。。耗了好多时间
用三点共线

【在 D****6 的大作中提到】
: 这题怎么做?算slope和yintercept,再用个hashmap count.怎么count比较好?而且好
: 像同一个点不能只算一次,count起来比较复杂。有什么简单做法没?

s********u
发帖数: 1109
6
我是找到那条线,然后再扫一遍,看在这条线上有多少个点。否则的话,比如单一个点
,就没法解决。因为有无限种可能。

【在 D****6 的大作中提到】
: 这题怎么做?算slope和yintercept,再用个hashmap count.怎么count比较好?而且好
: 像同一个点不能只算一次,count起来比较复杂。有什么简单做法没?

w*******s
发帖数: 96
7
牛人,居然用double的方法做出来了。能解释一下比较函数和思路吗?先找平行线?然
后看点是不是在那个上面?
struct Comp{

static double eps;

bool operator()( const Line &l1, const Line &l2){

if( l1.slope - l2.slope < -eps )
return true;

if( l1.slope - l2.slope > eps)
return false;

return (l1.intercept - l2.intercept < -eps);

}

};
l*n
发帖数: 529
8
我写的,利用输入为int,就拿dx & dy来标示直线了。
public int maxPoints(Point[] points) {
assert(points!=null);
if (points.length<2) return points.length;
int globalMax=0;
for (int i=0; i Point curr=points[i];
int max=0, repeat=1;
Map map=new HashMap();
for (int j=i+1; j Point other=points[j];
String b=null;
if (other.x==curr.x) {
if (other.y==curr.y) {
repeat++;
continue;
}
b=String.valueOf(Integer.MAX_VALUE);
} else if (other.y==curr.y) {
b=String.valueOf(0);
} else {
int gcd=gcd(other.y-curr.y, other.x-curr.x);
b=String.valueOf((other.y-curr.y)/gcd)+','+
String.valueOf((other.x-curr.x)/gcd);
}
if (!map.containsKey(b)) {
map.put(b, 1);
} else {
map.put(b, map.get(b)+1);
}
if (map.get(b)>max) max=map.get(b);
}
if (max+repeat>globalMax) globalMax=max+repeat;
}

return globalMax;
}

int gcd(int a, int b) {
return b==0?a:gcd(b, a%b);
}

【在 s********u 的大作中提到】
: struct Line{
:
: double slope;
: double intercept;
:
:
: Line(Point p, Point q){
:
: if(p.x == q.x){
: slope = numeric_limits::max();

s********u
发帖数: 1109
9
就是优先看斜率,再看截距。比较函数要注意严格弱序。只要定义了严格弱序,那么“
=”就相当于 非'a 我本来想用系统自带的epsilon,但可能太小了,反而失败了。就随便设了0.000001

【在 w*******s 的大作中提到】
: 牛人,居然用double的方法做出来了。能解释一下比较函数和思路吗?先找平行线?然
: 后看点是不是在那个上面?
: struct Comp{
:
: static double eps;
:
: bool operator()( const Line &l1, const Line &l2){
:
: if( l1.slope - l2.slope < -eps )
: return true;

m**********4
发帖数: 774
10
我们可以DEFINE一条线,用Y=KX+B, K和B 确定了Y就确定了。对于每个点,算其他
点跟它的线的K和B(中学代数,但要考虑K=无穷大的情况)。建立一个MAP,用K和B做
KEY。但问题是K和B都是DOUBLE怎么办呢?DOUBLE可以转换成INTVALUE,然后对素数求
模来计算HASHVALUE。用这条线的COUNT做VALUE。输出最大的那个就可以。这题还有一
个EDGE CASE 是如果有几个点都一样怎么办。
已经算过的点不能再算。所以我们LOOP的时候,
for (int i = 0; i < points.length; ++i)
for (int j = i+1; j < points.length; ++j)
底下有朋友贴了CODE我觉得不错。

【在 D****6 的大作中提到】
: 这题怎么做?算slope和yintercept,再用个hashmap count.怎么count比较好?而且好
: 像同一个点不能只算一次,count起来比较复杂。有什么简单做法没?

相关主题
Interview questions: points lie on same lineGOOGLE 第二轮电面
interview question:找包含点数最多的线段C++ Q83: 这个const_cast什么意思?
Caeercup150 原题:Find a line passes most points发个论坛上某已经淡出隐牛的一道Google Onsite概率题
d**********x
发帖数: 4083
11
k & b should not be expressed in double. just use number pairs.
they are rational numbers in this problem

且好

【在 m**********4 的大作中提到】
: 我们可以DEFINE一条线,用Y=KX+B, K和B 确定了Y就确定了。对于每个点,算其他
: 点跟它的线的K和B(中学代数,但要考虑K=无穷大的情况)。建立一个MAP,用K和B做
: KEY。但问题是K和B都是DOUBLE怎么办呢?DOUBLE可以转换成INTVALUE,然后对素数求
: 模来计算HASHVALUE。用这条线的COUNT做VALUE。输出最大的那个就可以。这题还有一
: 个EDGE CASE 是如果有几个点都一样怎么办。
: 已经算过的点不能再算。所以我们LOOP的时候,
: for (int i = 0; i < points.length; ++i)
: for (int j = i+1; j < points.length; ++j)
: 底下有朋友贴了CODE我觉得不错。

m**********4
发帖数: 774
12
You should be able to use doubles. Need to rewrite equals and hashcode
though. At least it is OK to pass OJ.

【在 d**********x 的大作中提到】
: k & b should not be expressed in double. just use number pairs.
: they are rational numbers in this problem
:
: 且好

D***0
发帖数: 138
13
不明白同一个点应该算两次?
Input: [(0,0),(0,0)]
Output: 1
Expected: 2
s*****p
发帖数: 108
14
重复的点肯定共线,所以都要算进去。

【在 D***0 的大作中提到】
: 不明白同一个点应该算两次?
: Input: [(0,0),(0,0)]
: Output: 1
: Expected: 2

D***0
发帖数: 138
15
我理解重复的点就算是一个点了,虽然在输入里给的是两个点,但是在坐标系里就是一
个点

【在 s*****p 的大作中提到】
: 重复的点肯定共线,所以都要算进去。
l****3
发帖数: 17
16
斜率这里可以用分数来表示,所有的斜率都化成最简分数,这样就不怕精度了
q****m
发帖数: 177
17
我的这个为什么超时了呢? 斜率我用一对整数(x, y)表示,而且让 x>= 0.斜率(0,y
)比其他的斜率都大。斜率(x1, y1) 比(x2, y2) 小的话意味着
y1/x1 < y2/x2, 转化成等价的形式 y1 * x2 < y2 * x1
/**
* Definition for a point.
* struct Point {
* int x;
* int y;
* Point() : x(0), y(0) {}
* Point(int a, int b) : x(a), y(b) {}
* };
*/
class Solution {
public:
static bool compare(const Point &a, const Point &b)
{
if(b.x == 0)
{
return true;
}
return a.y * b.x < a.x * b.y;
}
int maxPoints(vector &points) {
int cur = 0;
if(points.size() <= 2)
{
return points.size();
}
for(int i = 0; i < points.size() - 1; ++i)
{
vector v;
for(int j = i+ 1; j < points.size(); ++j)
{
Point tmp = Point(points[j].x - points[i].x, points[j].y -
points[i].y);
if(tmp.x < 0)
{
tmp.x = -tmp.x;
tmp.y = -tmp.y;
}
v.push_back(tmp);
}
sort(v.begin(), v.end(), compare);
for(int j = 0; j < v.size(); ++j)
{
int start = j;
while(start < v.size() && v[j].y * v[start].x == v[j].x * v[
start].y)
{
start ++;
}
cur = max(cur, start - j);
j = start - 1;
}
}
return cur + 1;
}
};

【在 l*n 的大作中提到】
: 我写的,利用输入为int,就拿dx & dy来标示直线了。
: public int maxPoints(Point[] points) {
: assert(points!=null);
: if (points.length<2) return points.length;
: int globalMax=0;
: for (int i=0; i: Point curr=points[i];
: int max=0, repeat=1;
: Map map=new HashMap();
: for (int j=i+1; j
1 (共1页)
相关主题
再贴这道算法题,寻答案,有包子送报个上周L家的onsite,已挂。继续为第6个onsite准备
尘埃落定里面的矩形题Interview questions: points lie on same line
MS bing onsite面经interview question:找包含点数最多的线段
storm8怎么样?Caeercup150 原题:Find a line passes most points
讨论一下给定平面上n点,求在同一直线上最多点问题~~大家用double /float 类型作hash key么GOOGLE 第二轮电面
lc里面那个max points O(n3)的算法也不慢啊C++ Q83: 这个const_cast什么意思?
被简单题给虐了。发个论坛上某已经淡出隐牛的一道Google Onsite概率题
给一堆points, 找到所有给定长度的正方形Max Points on a Line 用c++map老是没法compile
相关话题的讨论汇总
话题: point话题: int话题: line话题: return话题: points