Redian新闻
>
三哥也有行动派!(视频) (转载)
avatar
三哥也有行动派!(视频) (转载)# Joke - 肚皮舞运动
D*6
1
这题怎么做?算slope和yintercept,再用个hashmap count.怎么count比较好?而且好
像同一个点不能只算一次,count起来比较复杂。有什么简单做法没?
avatar
m*c
2
【 以下文字转载自 Military 讨论区 】
发信人: changbaihou (秋裤外穿), 信区: Military
标 题: 三哥也有行动派!(视频)
发信站: BBS 未名空间站 (Fri Aug 30 23:16:15 2013, 美东)
avatar
z*e
3
看题目就感觉要dp了
avatar
H*g
4
没ppt就失败了
avatar
l*n
5
没有,不是dp,就是cc150的题。

【在 z****e 的大作中提到】
: 看题目就感觉要dp了
avatar
t*3
6
三哥还是应该发挥他们的技术特点,直接强奸就搞定了
avatar
s*u
7
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;

}
};
avatar
h*o
8
不要用slope 跟hashmap 做。。。耗了好多时间
用三点共线

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

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

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

avatar
w*s
10
牛人,居然用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);

}

};
avatar
l*n
11
我写的,利用输入为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; iPoint curr=points[i];
int max=0, repeat=1;
Map map=new HashMap();
for (int j=i+1; jPoint 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();

avatar
s*u
12
就是优先看斜率,再看截距。比较函数要注意严格弱序。只要定义了严格弱序,那么“
=”就相当于 非'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;

avatar
m*4
13
我们可以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起来比较复杂。有什么简单做法没?

avatar
d*x
14
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我觉得不错。

avatar
m*4
15
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
:
: 且好

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

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

avatar
D*0
18
我理解重复的点就算是一个点了,虽然在输入里给的是两个点,但是在坐标系里就是一
个点

【在 s*****p 的大作中提到】
: 重复的点肯定共线,所以都要算进去。
avatar
l*3
19
斜率这里可以用分数来表示,所有的斜率都化成最简分数,这样就不怕精度了
avatar
q*m
20
我的这个为什么超时了呢? 斜率我用一对整数(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
相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。