h*******e
发帖数: 1377 | 1 rt
给定平面上n点，求在同一直线上最多点问题～～大家用double /float 类型作hash
key么？
判断两个double /float 类型相等～～～ 靠谱么 |
y***n
发帖数: 1594 | 2 不是可以设一个比较小的数， 0.0000001， 然后和这个数比较就可以吗？ |
h*******e
发帖数: 1377 | 3 找到一个链接，关于float做key
“HOWEVER, you should not be using a floating point for any part of a key in
any map -- for the same reason you shouldn't use them with == and !=
operators. Since floating points are approximations, they are unreliable as
keys.“
http://www.cplusplus.com/forum/beginner/56918/
【在 y***n 的大作中提到】
: 不是可以设一个比较小的数， 0.0000001， 然后和这个数比较就可以吗？
|
s**x
发帖数: 7506 | |
h*******e
发帖数: 1377 | 5 记不清了，能告诉一下第几章地几题么。
【在 s**x 的大作中提到】
: Cc150 介绍的非常清楚了吧？
|
j*****8
发帖数: 3635 | 6 正准备发个类似的问题，就在这里说了
有人面这题时因为用 double / float 作为 hashmap的key而被面试官说的吗？？ |
s**x
发帖数: 7506 | 7 自己查查
【在 h*******e 的大作中提到】
: 记不清了，能告诉一下第几章地几题么。
|
h*******e
发帖数: 1377 | 8 翻了一遍没找到，好久不看了。
你用第四版吧 我是第五版，
第四版10.6 找到了， java 可以自定义类型作为key的，c++ 就不行。
【在 s**x 的大作中提到】
: 自己查查
|
p****e
发帖数: 3548 | 9 可以取整，我就是这样做的
int slope = (int)(1000000.*float(p2.y-p1.y)/(p2.x-p1.x)); |
s**x
发帖数: 7506 | 10
第五版7.6
【在 h*******e 的大作中提到】
: 翻了一遍没找到，好久不看了。
: 你用第四版吧 我是第五版，
: 第四版10.6 找到了， java 可以自定义类型作为key的，c++ 就不行。
|
|
|
h*******e
发帖数: 1377 | 11 谢谢看到cc150给的方法了。觉得给的解法还是比较一般。。。计算几何里面很少用k
来决定点在一条直线上。k在靠近原点一小变很可能导致点在 距离原点远处一大变。
【在 s**x 的大作中提到】
:
: 第五版7.6
|
g*********e
发帖数: 14401 | 12 如果坐标是整数的话，斜率都是有理数。可以存pair
【在 h*******e 的大作中提到】
: rt
: 给定平面上n点，求在同一直线上最多点问题～～大家用double /float 类型作hash
: key么？
: 判断两个double /float 类型相等～～～ 靠谱么
|
h*******e
发帖数: 1377 | 13 如果是pair作为 key 的话自定义的hash 函数一般怎么写
在 c++ unordered_set, int> 大牛给讲一下哦。
【在 g*********e 的大作中提到】
: 如果坐标是整数的话，斜率都是有理数。可以存pair
|
g*********e
发帖数: 14401 | 14 你写的对
【在 h*******e 的大作中提到】
: 如果是pair作为 key 的话自定义的hash 函数一般怎么写
: 在 c++ unordered_set, int> 大牛给讲一下哦。
|
h*******e
发帖数: 1377 | 15 光是这个过不了leetcode的编译器阿，需要自定义hash 函数，和比较函数的似乎。
【在 g*********e 的大作中提到】
: 你写的对
|
P*******L
发帖数: 2637 | 16 这样做是最好的，但是还得找最大公约数，容易超时过不了 oj。
【在 g*********e 的大作中提到】
: 如果坐标是整数的话，斜率都是有理数。可以存pair
|
h*******e
发帖数: 1377 | 17 要自己加hash function的，我写了一个总算过了编译了
namespace std {
template <>
struct hash >
{
typedef std::size_t result_type;
result_type operator()(const pair & t) const
{
return t.first * 1000003 + t.second;
}
};
}
备注 (不过似乎不太好~~ 似乎 hash值 溢出了~~~ )但是也过了oj了。
有没有人写过这个hash, 这个似乎是c++ 0x/11新标准 ~~这个hash函数该怎么写才能
写得简单少冲突而又 不越界呢~~
gcd非常少的代码的。就是辗转相除一行代码就行。
【在 P*******L 的大作中提到】
: 这样做是最好的，但是还得找最大公约数，容易超时过不了 oj。
|
g*********e
发帖数: 14401 | 18 set, int>
这个直接就可以用啊
想过leetcode的话用floating的比较就足够了，但google面试的时候我用floating的斜
率 Interviewer就不让过 |
h*******e
发帖数: 1377 | 19 google 是要求pair 做斜率么？
google是要求精确在一条直线上， 还是要求近似的可以有些误差的点也算一条线阿。
请大牛给细说说g关于这道题的要求阿。
【在 g*********e 的大作中提到】
: set, int>
: 这个直接就可以用啊
: 想过leetcode的话用floating的比较就足够了，但google面试的时候我用floating的斜
: 率 Interviewer就不让过
|
g*********e
发帖数: 14401 | 20
要精确的 不能用epsilon这样去比。不过也看面试官吧
【在 h*******e 的大作中提到】
: google 是要求pair 做斜率么？
: google是要求精确在一条直线上， 还是要求近似的可以有些误差的点也算一条线阿。
: 请大牛给细说说g关于这道题的要求阿。
|
|
|
h*******e
发帖数: 1377 | 21 恩恩，多谢了。
【在 g*********e 的大作中提到】
:
: 要精确的 不能用epsilon这样去比。不过也看面试官吧
|
f*******5
发帖数: 52 | 22
有一个思路不知道对不对，用unordered_map, 因为点坐标是整数，所以
斜率可以表示成循环小数, 比如5/6=0.8(3)， 还没在leetcode上试，不知道能不能过
【在 h*******e 的大作中提到】
: 要自己加hash function的，我写了一个总算过了编译了
: namespace std {
: template <>
: struct hash >
: {
: typedef std::size_t result_type;
: result_type operator()(const pair & t) const
: {
: return t.first * 1000003 + t.second;
: }
|
s***5
发帖数: 2136 | 23 use hash of hash: unordered_map >
【在 h*******e 的大作中提到】
: 如果是pair作为 key 的话自定义的hash 函数一般怎么写
: 在 c++ unordered_set, int> 大牛给讲一下哦。
|
h*******e
发帖数: 1377 | 24 我之前用的map 把 pair 的两个 int 变成string 中间加上
" "然后再加上 string 变成一个长string 你的方法也是对的一个 无理数唯一对应
一个非循环，和循环部分的组合。就是这个求循环节的过程比较麻烦了，估计你数学功
底很好，可以很快求出来。
【在 f*******5 的大作中提到】
:
: 有一个思路不知道对不对，用unordered_map, 因为点坐标是整数，所以
: 斜率可以表示成循环小数, 比如5/6=0.8(3)， 还没在leetcode上试，不知道能不能过
|
h*******e
发帖数: 1377 | 25 是不是key value类型写反了，而且复杂的类型做key比较麻烦在leetcode 定义就不可
以，vs2010定义没问题，但是往里面map[key]= val 赋值时候就编译不过了。
【在 s***5 的大作中提到】
: use hash of hash: unordered_map >
|
f*******5
发帖数: 52 | 26
有个Google面试题是求整数除法的循环，是不断用余数做被除数，用一个bool arr[10]
记录被除数，当前被除数如果见过就表示循环
【在 h*******e 的大作中提到】
: 是不是key value类型写反了，而且复杂的类型做key比较麻烦在leetcode 定义就不可
: 以，vs2010定义没问题，但是往里面map[key]= val 赋值时候就编译不过了。
|
h*******e
发帖数: 1377 | 27 呵呵，估计写得好能小impress面试官一下，本想出一道难题，没成想面试者一口气完
成了两道难题。
10]
【在 f*******5 的大作中提到】
:
: 有个Google面试题是求整数除法的循环，是不断用余数做被除数，用一个bool arr[10]
: 记录被除数，当前被除数如果见过就表示循环
|
y***n
发帖数: 1594 | 28 那Sqrt 那个题可以用epsilon吗？
【在 g*********e 的大作中提到】
:
: 要精确的 不能用epsilon这样去比。不过也看面试官吧
|
g**e
发帖数: 6127 | 29 记得数学的算cross product
不记得的斜率公式转换一下变乘法，其实就是叉乘
【在 g*********e 的大作中提到】
: set, int>
: 这个直接就可以用啊
: 想过leetcode的话用floating的比较就足够了，但google面试的时候我用floating的斜
: 率 Interviewer就不让过
|
g*********e
发帖数: 14401 | 30 表示成2/7=0.[285714]
10]
【在 f*******5 的大作中提到】
:
: 有个Google面试题是求整数除法的循环，是不断用余数做被除数，用一个bool arr[10]
: 记录被除数，当前被除数如果见过就表示循环
|
|
|
g*********e
发帖数: 14401 | 31 可以
【在 y***n 的大作中提到】
: 那Sqrt 那个题可以用epsilon吗？
|
y***n
发帖数: 1594 | 32 你搞得那么细，以后可以写一本书。每个题写：
A. 基本解法。
A-1. Google解法。
A-2。Facebook 解法。
A-3。 Linkedin解法。
【在 h*******e 的大作中提到】
: google 是要求pair 做斜率么？
: google是要求精确在一条直线上， 还是要求近似的可以有些误差的点也算一条线阿。
: 请大牛给细说说g关于这道题的要求阿。
|
h*******e
发帖数: 1377 | 33 你多做些计算几何题就知道了，计算几何差一点就差很多， 比如三点共线的标准方法
就是叉乘面积近似为0，近似斜率做就引进边的长度误差，计算几何在严格一点的oj上都
是差之毫厘，失之千里的，过了leetcode的 oj的做法很多不一定就一定无懈可击，往
往面试难得不是原题，而是是要求改一点，比如这道题之前c++ 不支持 unordered_set
的时候就看过这道题，那要高效算法就只能手动写链表hash table实现hash~~ 这道题
glowinglake 的 follow up 也不是那么简单说海量数据情况下应该怎么变我还没细想
。
by the way 关于sqrt 那道题 虽然可以用 epsilon但是有不用 epsilon的精确解法，
不知道你能不能想出来。
【在 y***n 的大作中提到】
: 你搞得那么细，以后可以写一本书。每个题写：
: A. 基本解法。
: A-1. Google解法。
: A-2。Facebook 解法。
: A-3。 Linkedin解法。
|
h****t
发帖数: 184 | 34
这个能再多解释一下吗？
【在 g**e 的大作中提到】
: 记得数学的算cross product
: 不记得的斜率公式转换一下变乘法，其实就是叉乘
|
h****t
发帖数: 184 | 35
弱问一句：为什么只存 slope作为key呢， 不需要存和 y轴交点吗？
【在 h*******e 的大作中提到】
: 如果是pair作为 key 的话自定义的hash 函数一般怎么写
: 在 c++ unordered_set, int> 大牛给讲一下哦。
|
h*******e
发帖数: 1377 | 36 不同的2点确定一条直线，确定一个直线方程，确定一斜率。
【在 h****t 的大作中提到】
:
: 弱问一句：为什么只存 slope作为key呢， 不需要存和 y轴交点吗？
|
h****t
发帖数: 184 | 37 我的意思是 会存在2条不同的平行直线（相同斜率）。
只存斜率无法区分这2条不同直线。
【在 h*******e 的大作中提到】
: 不同的2点确定一条直线，确定一个直线方程，确定一斜率。
|
h*******e
发帖数: 1377 | 38 我感觉你对这道题的总体思路还没有概念，为了不spoil你刷题的乐趣，你可以尝试思
考并且做一下leetcode第三题。max points on a line.
【在 h****t 的大作中提到】
: 我的意思是 会存在2条不同的平行直线（相同斜率）。
: 只存斜率无法区分这2条不同直线。
|
h****t
发帖数: 184 | 39 不知道你的感觉从何而来。
2年前面世时就被问过这题并且答案通过。leetcode什么的其它不多说了，没刷过的人
现在不多了。
"总体思路还没有概念"，嘿嘿，嘿嘿。我一笑而过。
【在 h*******e 的大作中提到】
: 我感觉你对这道题的总体思路还没有概念，为了不spoil你刷题的乐趣，你可以尝试思
: 考并且做一下leetcode第三题。max points on a line.
|
y***n
发帖数: 1594 | 40 他应该不是用 slope作为key呢
【在 h****t 的大作中提到】
: 不知道你的感觉从何而来。
: 2年前面世时就被问过这题并且答案通过。leetcode什么的其它不多说了，没刷过的人
: 现在不多了。
: "总体思路还没有概念"，嘿嘿，嘿嘿。我一笑而过。
|
|
|
h*******e
发帖数: 1377 | 41 哦那就是你刷题和我们大多数人的思路很不同哦，不妨你也介绍一下你的做法，大家开
阔思路哦。
我们是算每点和其他点的斜率，用斜率为key做hashmap, 看和本点相连的其他点落在
每个斜率内的有几个。 然后枚举这个轴心点 这样算法复杂度O(N*N)
我们现在都是用斜率作key 整个帖子纠结的是斜率怎么存和相应的精确度的问题，看
你说似乎不是用斜率做key,
所以开始还以为你没做过呢。
【在 h****t 的大作中提到】
: 不知道你的感觉从何而来。
: 2年前面世时就被问过这题并且答案通过。leetcode什么的其它不多说了，没刷过的人
: 现在不多了。
: "总体思路还没有概念"，嘿嘿，嘿嘿。我一笑而过。
|
i******s
发帖数: 301 | 42 忍不住替habbit说一句，如果枚举所有点，并且每次内循环前用新的hashmap的话，可
以只存斜率，因为此时之前一点已经固定(外层循环确定起始点)，所以可以用斜率做
key。但是如果hashmap不是每次内循环前创建，而是在双重循序前创建，那么截距是一
定要的，光slope不够。还有这道题用slope有精度问题，
消除方法最简单就是换个直线表示方式，用Ax+By+C = 0。其中A, B和C都是整数，每两
个点构成的直线都这样表示，注意用gcd法保证A,B和C没有公约数，并且保证符号相
同(可以假设A永远是正)。而且这道题最大的trick是如何处理重复的点，一般没做过的
第一次做不一定想得到好办法。总体看之前的讨论无语了，跳出来说几句。
【在 h*******e 的大作中提到】
: 哦那就是你刷题和我们大多数人的思路很不同哦，不妨你也介绍一下你的做法，大家开
: 阔思路哦。
: 我们是算每点和其他点的斜率，用斜率为key做hashmap, 看和本点相连的其他点落在
: 每个斜率内的有几个。 然后枚举这个轴心点 这样算法复杂度O(N*N)
: 我们现在都是用斜率作key 整个帖子纠结的是斜率怎么存和相应的精确度的问题，看
: 你说似乎不是用斜率做key,
: 所以开始还以为你没做过呢。
|
h*******e
发帖数: 1377 | 43 namespace std {
template <>
struct hash >
{
typedef std::size_t result_type;
result_type operator()(const pair & t) const
{ return ((long)t.first * 1000003 + t.second )& (((long)1<<32 ) - 1);
}
};
}
class Solution {
public:
// suppose no two points are the same
int gcd(int a, int b)
{ return !b? a: gcd(b, a %b); }
pair getK(vector & points, int pointI, int pointJ)
{
int x1 = points[pointI].x, y1 = points[pointI].y,
x2 = points[pointJ].x, y2 = points[pointJ].y;
int diffy = y1 - y2, diffx = x1 - x2;
if(diffy == 0 || diffx == 0)
{
if(diffy == 0) diffx = 1;
if(diffx == 0) diffy = 1;
return make_pair(diffy, diffx);
}
if(diffy < 0)
{
diffy = -diffy;
diffx = -diffx;
}
int gcdVal = gcd(abs(diffy), abs(diffx));
return make_pair(diffy/gcdVal, diffx/gcdVal);
}
bool samePoint(vector & points, int pointI, int pointJ)
{ return points[pointI].x == points[pointJ].x && points[pointI].y ==
points[pointJ].y; }
/*
string intToStr(int val)
{
if(!val) return "0";
string str = "";
while(val)
{
str += val %10 + '0';
val /= 10;
}
reverse(str.begin(), str.end());
return str;
}
string pairToStr(pair & p)
{ return intToStr(p.first) + " " + intToStr(p.second);}
＊/
int maxPoints(vector &points) {
unordered_map, int > map;
int maxPoint = 0;
for(int pointI = 0; pointI < points.size(); ++ pointI)
{
map.clear();
int sameCnt = 1, diffMax = 0;
for(int pointJ = 0; pointJ < points.size(); ++ pointJ)
{
if(pointI == pointJ) continue;
if(samePoint(points, pointI, pointJ))
{
++ sameCnt;
continue;
}
pair kval = getK(points, pointI, pointJ);
if(map.find(kval) == map.end())
map[kval] = 1;
else
++map[kval];
diffMax = max(diffMax, map[kval]);
}
maxPoint = max(maxPoint, diffMax + sameCnt);
}
return maxPoint;
}
};
我贴个我的算法吧，你贴个你的标准答案，比一下就好了,咱们思路差太多。
【在 i******s 的大作中提到】
: 忍不住替habbit说一句，如果枚举所有点，并且每次内循环前用新的hashmap的话，可
: 以只存斜率，因为此时之前一点已经固定(外层循环确定起始点)，所以可以用斜率做
: key。但是如果hashmap不是每次内循环前创建，而是在双重循序前创建，那么截距是一
: 定要的，光slope不够。还有这道题用slope有精度问题，
: 消除方法最简单就是换个直线表示方式，用Ax+By+C = 0。其中A, B和C都是整数，每两
: 个点构成的直线都这样表示，注意用gcd法保证A,B和C没有公约数，并且保证符号相
: 同(可以假设A永远是正)。而且这道题最大的trick是如何处理重复的点，一般没做过的
: 第一次做不一定想得到好办法。总体看之前的讨论无语了，跳出来说几句。
|
i******s
发帖数: 301 | 44 之前回的有误，请看我更正后的解答，你这样行是因为每次内循环前都clear了map。如
果换一个实现，则一定要存截距。anyway，slope的精度问题如果面试官死扣，那就只
能换Ax+By+C的表示方式，如果让过就过了。我碰到过both。
);
【在 h*******e 的大作中提到】
: namespace std {
: template <>
: struct hash >
: {
: typedef std::size_t result_type;
: result_type operator()(const pair & t) const
: { return ((long)t.first * 1000003 + t.second )& (((long)1<<32 ) - 1);
: }
: };
: }
|
h*******e
发帖数: 1377 | 45 我的是check 了 Ａ＝０ Ｂ＝０的情况其实并不是严格意义上的斜率，垂直水平
是 ０， １ 和 １， ０ 一轴心点加上一方向自然能确定一条直线。
【在 i******s 的大作中提到】
: 之前回的有误，请看我更正后的解答，你这样行是因为每次内循环前都clear了map。如
: 果换一个实现，则一定要存截距。anyway，slope的精度问题如果面试官死扣，那就只
: 能换Ax+By+C的表示方式，如果让过就过了。我碰到过both。
:
: );
|
i******s
发帖数: 301 | 46 你的解法没问题，只是要记得为什么可以不保存截距，只用"斜率"就可以。有的面试官
会confuse，因为可能他们没有想过如果每次内循环前清了map(或者创建一个新的)，则
截距不是必须的。因为一个点在外循环是已确定。如果碰上绕不过的新手面试官，建议
保存截距以迎合他们的口味。。。
【在 h*******e 的大作中提到】
: 我的是check 了 Ａ＝０ Ｂ＝０的情况其实并不是严格意义上的斜率，垂直水平
: 是 ０， １ 和 １， ０ 一轴心点加上一方向自然能确定一条直线。
|
p****e
发帖数: 3548 | 47 A,B,C的解法更局限一点吧，因为只适用于整数情况
如果点是浮点的话，还是要考虑精度问题
【在 i******s 的大作中提到】
: 之前回的有误，请看我更正后的解答，你这样行是因为每次内循环前都clear了map。如
: 果换一个实现，则一定要存截距。anyway，slope的精度问题如果面试官死扣，那就只
: 能换Ax+By+C的表示方式，如果让过就过了。我碰到过both。
:
: );
|
i******s
发帖数: 301 | 48 well, 一般遇到的都是point是int x, int y。如果面试官扣这个，那就只有跟他聊聊
怎么解决精度问题了。但对于都是int的情况，ABC法比较好。
【在 p****e 的大作中提到】
: A,B,C的解法更局限一点吧，因为只适用于整数情况
: 如果点是浮点的话，还是要考虑精度问题
|
h*******e
发帖数: 1377 | 49 浮点要考虑精度问题的而且这时候要重写 unordered_map的equal函数了， 我现在还
没想清楚为什么这个 哈希函数一定要外面加个namespace std才能通过。
这种template我之前也没见过 搜了一下发现叫做全特化模板。
【在 p****e 的大作中提到】
: A,B,C的解法更局限一点吧，因为只适用于整数情况
: 如果点是浮点的话，还是要考虑精度问题
|
h*******e
发帖数: 1377 | 50 轴心点 pointI 给定了 知道了 Ａ Ｂ就能知道 C了所以两个值就够了
【在 i******s 的大作中提到】
: 之前回的有误，请看我更正后的解答，你这样行是因为每次内循环前都clear了map。如
: 果换一个实现，则一定要存截距。anyway，slope的精度问题如果面试官死扣，那就只
: 能换Ax+By+C的表示方式，如果让过就过了。我碰到过both。
:
: );
|
|
|
h*******e
发帖数: 1377 | 51 rt
给定平面上n点，求在同一直线上最多点问题～～大家用double /float 类型作hash
key么？
判断两个double /float 类型相等～～～ 靠谱么 |
y***n
发帖数: 1594 | 52 不是可以设一个比较小的数， 0.0000001， 然后和这个数比较就可以吗？ |
h*******e
发帖数: 1377 | 53 找到一个链接，关于float做key
“HOWEVER, you should not be using a floating point for any part of a key in
any map -- for the same reason you shouldn't use them with == and !=
operators. Since floating points are approximations, they are unreliable as
keys.“
http://www.cplusplus.com/forum/beginner/56918/
【在 y***n 的大作中提到】
: 不是可以设一个比较小的数， 0.0000001， 然后和这个数比较就可以吗？
|
s**x
发帖数: 7506 | |
h*******e
发帖数: 1377 | 55 记不清了，能告诉一下第几章地几题么。
【在 s**x 的大作中提到】
: Cc150 介绍的非常清楚了吧？
|
j*****8
发帖数: 3635 | 56 正准备发个类似的问题，就在这里说了
有人面这题时因为用 double / float 作为 hashmap的key而被面试官说的吗？？ |
s**x
发帖数: 7506 | 57 自己查查
【在 h*******e 的大作中提到】
: 记不清了，能告诉一下第几章地几题么。
|
h*******e
发帖数: 1377 | 58 翻了一遍没找到，好久不看了。
你用第四版吧 我是第五版，
第四版10.6 找到了， java 可以自定义类型作为key的，c++ 就不行。
【在 s**x 的大作中提到】
: 自己查查
|
p****e
发帖数: 3548 | 59 可以取整，我就是这样做的
int slope = (int)(1000000.*float(p2.y-p1.y)/(p2.x-p1.x)); |
s**x
发帖数: 7506 | 60
第五版7.6
【在 h*******e 的大作中提到】
: 翻了一遍没找到，好久不看了。
: 你用第四版吧 我是第五版，
: 第四版10.6 找到了， java 可以自定义类型作为key的，c++ 就不行。
|
|
|
h*******e
发帖数: 1377 | 61 谢谢看到cc150给的方法了。觉得给的解法还是比较一般。。。计算几何里面很少用k
来决定点在一条直线上。k在靠近原点一小变很可能导致点在 距离原点远处一大变。
【在 s**x 的大作中提到】
:
: 第五版7.6
|
g*********e
发帖数: 14401 | 62 如果坐标是整数的话，斜率都是有理数。可以存pair
【在 h*******e 的大作中提到】
: rt
: 给定平面上n点，求在同一直线上最多点问题～～大家用double /float 类型作hash
: key么？
: 判断两个double /float 类型相等～～～ 靠谱么
|
h*******e
发帖数: 1377 | 63 如果是pair作为 key 的话自定义的hash 函数一般怎么写
在 c++ unordered_set, int> 大牛给讲一下哦。
【在 g*********e 的大作中提到】
: 如果坐标是整数的话，斜率都是有理数。可以存pair
|
g*********e
发帖数: 14401 | 64 你写的对
【在 h*******e 的大作中提到】
: 如果是pair作为 key 的话自定义的hash 函数一般怎么写
: 在 c++ unordered_set, int> 大牛给讲一下哦。
|
h*******e
发帖数: 1377 | 65 光是这个过不了leetcode的编译器阿，需要自定义hash 函数，和比较函数的似乎。
【在 g*********e 的大作中提到】
: 你写的对
|
P*******L
发帖数: 2637 | 66 这样做是最好的，但是还得找最大公约数，容易超时过不了 oj。
【在 g*********e 的大作中提到】
: 如果坐标是整数的话，斜率都是有理数。可以存pair
|
h*******e
发帖数: 1377 | 67 要自己加hash function的，我写了一个总算过了编译了
namespace std {
template <>
struct hash >
{
typedef std::size_t result_type;
result_type operator()(const pair & t) const
{
return t.first * 1000003 + t.second;
}
};
}
备注 (不过似乎不太好~~ 似乎 hash值 溢出了~~~ )但是也过了oj了。
有没有人写过这个hash, 这个似乎是c++ 0x/11新标准 ~~这个hash函数该怎么写才能
写得简单少冲突而又 不越界呢~~
gcd非常少的代码的。就是辗转相除一行代码就行。
【在 P*******L 的大作中提到】
: 这样做是最好的，但是还得找最大公约数，容易超时过不了 oj。
|
g*********e
发帖数: 14401 | 68 set, int>
这个直接就可以用啊
想过leetcode的话用floating的比较就足够了，但google面试的时候我用floating的斜
率 Interviewer就不让过 |
h*******e
发帖数: 1377 | 69 google 是要求pair 做斜率么？
google是要求精确在一条直线上， 还是要求近似的可以有些误差的点也算一条线阿。
请大牛给细说说g关于这道题的要求阿。
【在 g*********e 的大作中提到】
: set, int>
: 这个直接就可以用啊
: 想过leetcode的话用floating的比较就足够了，但google面试的时候我用floating的斜
: 率 Interviewer就不让过
|
g*********e
发帖数: 14401 | 70
要精确的 不能用epsilon这样去比。不过也看面试官吧
【在 h*******e 的大作中提到】
: google 是要求pair 做斜率么？
: google是要求精确在一条直线上， 还是要求近似的可以有些误差的点也算一条线阿。
: 请大牛给细说说g关于这道题的要求阿。
|
|
|
h*******e
发帖数: 1377 | 71 恩恩，多谢了。
【在 g*********e 的大作中提到】
:
: 要精确的 不能用epsilon这样去比。不过也看面试官吧
|
f*******5
发帖数: 52 | 72
有一个思路不知道对不对，用unordered_map, 因为点坐标是整数，所以
斜率可以表示成循环小数, 比如5/6=0.8(3)， 还没在leetcode上试，不知道能不能过
【在 h*******e 的大作中提到】
: 要自己加hash function的，我写了一个总算过了编译了
: namespace std {
: template <>
: struct hash >
: {
: typedef std::size_t result_type;
: result_type operator()(const pair & t) const
: {
: return t.first * 1000003 + t.second;
: }
|
s***5
发帖数: 2136 | 73 use hash of hash: unordered_map >
【在 h*******e 的大作中提到】
: 如果是pair作为 key 的话自定义的hash 函数一般怎么写
: 在 c++ unordered_set, int> 大牛给讲一下哦。
|
h*******e
发帖数: 1377 | 74 我之前用的map 把 pair 的两个 int 变成string 中间加上
" "然后再加上 string 变成一个长string 你的方法也是对的一个 无理数唯一对应
一个非循环，和循环部分的组合。就是这个求循环节的过程比较麻烦了，估计你数学功
底很好，可以很快求出来。
【在 f*******5 的大作中提到】
:
: 有一个思路不知道对不对，用unordered_map, 因为点坐标是整数，所以
: 斜率可以表示成循环小数, 比如5/6=0.8(3)， 还没在leetcode上试，不知道能不能过
|
h*******e
发帖数: 1377 | 75 是不是key value类型写反了，而且复杂的类型做key比较麻烦在leetcode 定义就不可
以，vs2010定义没问题，但是往里面map[key]= val 赋值时候就编译不过了。
【在 s***5 的大作中提到】
: use hash of hash: unordered_map >
|
f*******5
发帖数: 52 | 76
有个Google面试题是求整数除法的循环，是不断用余数做被除数，用一个bool arr[10]
记录被除数，当前被除数如果见过就表示循环
【在 h*******e 的大作中提到】
: 是不是key value类型写反了，而且复杂的类型做key比较麻烦在leetcode 定义就不可
: 以，vs2010定义没问题，但是往里面map[key]= val 赋值时候就编译不过了。
|
h*******e
发帖数: 1377 | 77 呵呵，估计写得好能小impress面试官一下，本想出一道难题，没成想面试者一口气完
成了两道难题。
10]
【在 f*******5 的大作中提到】
:
: 有个Google面试题是求整数除法的循环，是不断用余数做被除数，用一个bool arr[10]
: 记录被除数，当前被除数如果见过就表示循环
|
y***n
发帖数: 1594 | 78 那Sqrt 那个题可以用epsilon吗？
【在 g*********e 的大作中提到】
:
: 要精确的 不能用epsilon这样去比。不过也看面试官吧
|
g**e
发帖数: 6127 | 79 记得数学的算cross product
不记得的斜率公式转换一下变乘法，其实就是叉乘
【在 g*********e 的大作中提到】
: set, int>
: 这个直接就可以用啊
: 想过leetcode的话用floating的比较就足够了，但google面试的时候我用floating的斜
: 率 Interviewer就不让过
|
g*********e
发帖数: 14401 | 80 表示成2/7=0.[285714]
10]
【在 f*******5 的大作中提到】
:
: 有个Google面试题是求整数除法的循环，是不断用余数做被除数，用一个bool arr[10]
: 记录被除数，当前被除数如果见过就表示循环
|
|
|
g*********e
发帖数: 14401 | 81 可以
【在 y***n 的大作中提到】
: 那Sqrt 那个题可以用epsilon吗？
|
y***n
发帖数: 1594 | 82 你搞得那么细，以后可以写一本书。每个题写：
A. 基本解法。
A-1. Google解法。
A-2。Facebook 解法。
A-3。 Linkedin解法。
【在 h*******e 的大作中提到】
: google 是要求pair 做斜率么？
: google是要求精确在一条直线上， 还是要求近似的可以有些误差的点也算一条线阿。
: 请大牛给细说说g关于这道题的要求阿。
|
h*******e
发帖数: 1377 | 83 你多做些计算几何题就知道了，计算几何差一点就差很多， 比如三点共线的标准方法
就是叉乘面积近似为0，近似斜率做就引进边的长度误差，计算几何在严格一点的oj上都
是差之毫厘，失之千里的，过了leetcode的 oj的做法很多不一定就一定无懈可击，往
往面试难得不是原题，而是是要求改一点，比如这道题之前c++ 不支持 unordered_set
的时候就看过这道题，那要高效算法就只能手动写链表hash table实现hash~~ 这道题
glowinglake 的 follow up 也不是那么简单说海量数据情况下应该怎么变我还没细想
。
by the way 关于sqrt 那道题 虽然可以用 epsilon但是有不用 epsilon的精确解法，
不知道你能不能想出来。
【在 y***n 的大作中提到】
: 你搞得那么细，以后可以写一本书。每个题写：
: A. 基本解法。
: A-1. Google解法。
: A-2。Facebook 解法。
: A-3。 Linkedin解法。
|
h****t
发帖数: 184 | 84
这个能再多解释一下吗？
【在 g**e 的大作中提到】
: 记得数学的算cross product
: 不记得的斜率公式转换一下变乘法，其实就是叉乘
|
h****t
发帖数: 184 | 85
弱问一句：为什么只存 slope作为key呢， 不需要存和 y轴交点吗？
【在 h*******e 的大作中提到】
: 如果是pair作为 key 的话自定义的hash 函数一般怎么写
: 在 c++ unordered_set, int> 大牛给讲一下哦。
|
h*******e
发帖数: 1377 | 86 不同的2点确定一条直线，确定一个直线方程，确定一斜率。
【在 h****t 的大作中提到】
:
: 弱问一句：为什么只存 slope作为key呢， 不需要存和 y轴交点吗？
|
h****t
发帖数: 184 | 87 我的意思是 会存在2条不同的平行直线（相同斜率）。
只存斜率无法区分这2条不同直线。
【在 h*******e 的大作中提到】
: 不同的2点确定一条直线，确定一个直线方程，确定一斜率。
|
h*******e
发帖数: 1377 | 88 我感觉你对这道题的总体思路还没有概念，为了不spoil你刷题的乐趣，你可以尝试思
考并且做一下leetcode第三题。max points on a line.
【在 h****t 的大作中提到】
: 我的意思是 会存在2条不同的平行直线（相同斜率）。
: 只存斜率无法区分这2条不同直线。
|
h****t
发帖数: 184 | 89 不知道你的感觉从何而来。
2年前面世时就被问过这题并且答案通过。leetcode什么的其它不多说了，没刷过的人
现在不多了。
"总体思路还没有概念"，嘿嘿，嘿嘿。我一笑而过。
【在 h*******e 的大作中提到】
: 我感觉你对这道题的总体思路还没有概念，为了不spoil你刷题的乐趣，你可以尝试思
: 考并且做一下leetcode第三题。max points on a line.
|
y***n
发帖数: 1594 | 90 他应该不是用 slope作为key呢
【在 h****t 的大作中提到】
: 不知道你的感觉从何而来。
: 2年前面世时就被问过这题并且答案通过。leetcode什么的其它不多说了，没刷过的人
: 现在不多了。
: "总体思路还没有概念"，嘿嘿，嘿嘿。我一笑而过。
|
|
|
h*******e
发帖数: 1377 | 91 哦那就是你刷题和我们大多数人的思路很不同哦，不妨你也介绍一下你的做法，大家开
阔思路哦。
我们是算每点和其他点的斜率，用斜率为key做hashmap, 看和本点相连的其他点落在
每个斜率内的有几个。 然后枚举这个轴心点 这样算法复杂度O(N*N)
我们现在都是用斜率作key 整个帖子纠结的是斜率怎么存和相应的精确度的问题，看
你说似乎不是用斜率做key,
所以开始还以为你没做过呢。
【在 h****t 的大作中提到】
: 不知道你的感觉从何而来。
: 2年前面世时就被问过这题并且答案通过。leetcode什么的其它不多说了，没刷过的人
: 现在不多了。
: "总体思路还没有概念"，嘿嘿，嘿嘿。我一笑而过。
|
i******s
发帖数: 301 | 92 忍不住替habbit说一句，如果枚举所有点，并且每次内循环前用新的hashmap的话，可
以只存斜率，因为此时之前一点已经固定(外层循环确定起始点)，所以可以用斜率做
key。但是如果hashmap不是每次内循环前创建，而是在双重循序前创建，那么截距是一
定要的，光slope不够。还有这道题用slope有精度问题，
消除方法最简单就是换个直线表示方式，用Ax+By+C = 0。其中A, B和C都是整数，每两
个点构成的直线都这样表示，注意用gcd法保证A,B和C没有公约数，并且保证符号相
同(可以假设A永远是正)。而且这道题最大的trick是如何处理重复的点，一般没做过的
第一次做不一定想得到好办法。总体看之前的讨论无语了，跳出来说几句。
【在 h*******e 的大作中提到】
: 哦那就是你刷题和我们大多数人的思路很不同哦，不妨你也介绍一下你的做法，大家开
: 阔思路哦。
: 我们是算每点和其他点的斜率，用斜率为key做hashmap, 看和本点相连的其他点落在
: 每个斜率内的有几个。 然后枚举这个轴心点 这样算法复杂度O(N*N)
: 我们现在都是用斜率作key 整个帖子纠结的是斜率怎么存和相应的精确度的问题，看
: 你说似乎不是用斜率做key,
: 所以开始还以为你没做过呢。
|
h*******e
发帖数: 1377 | 93 namespace std {
template <>
struct hash >
{
typedef std::size_t result_type;
result_type operator()(const pair & t) const
{ return ((long)t.first * 1000003 + t.second )& (((long)1<<32 ) - 1);
}
};
}
class Solution {
public:
// suppose no two points are the same
int gcd(int a, int b)
{ return !b? a: gcd(b, a %b); }
pair getK(vector & points, int pointI, int pointJ)
{
int x1 = points[pointI].x, y1 = points[pointI].y,
x2 = points[pointJ].x, y2 = points[pointJ].y;
int diffy = y1 - y2, diffx = x1 - x2;
if(diffy == 0 || diffx == 0)
{
if(diffy == 0) diffx = 1;
if(diffx == 0) diffy = 1;
return make_pair(diffy, diffx);
}
if(diffy < 0)
{
diffy = -diffy;
diffx = -diffx;
}
int gcdVal = gcd(abs(diffy), abs(diffx));
return make_pair(diffy/gcdVal, diffx/gcdVal);
}
bool samePoint(vector & points, int pointI, int pointJ)
{ return points[pointI].x == points[pointJ].x && points[pointI].y ==
points[pointJ].y; }
/*
string intToStr(int val)
{
if(!val) return "0";
string str = "";
while(val)
{
str += val %10 + '0';
val /= 10;
}
reverse(str.begin(), str.end());
return str;
}
string pairToStr(pair & p)
{ return intToStr(p.first) + " " + intToStr(p.second);}
＊/
int maxPoints(vector &points) {
unordered_map, int > map;
int maxPoint = 0;
for(int pointI = 0; pointI < points.size(); ++ pointI)
{
map.clear();
int sameCnt = 1, diffMax = 0;
for(int pointJ = 0; pointJ < points.size(); ++ pointJ)
{
if(pointI == pointJ) continue;
if(samePoint(points, pointI, pointJ))
{
++ sameCnt;
continue;
}
pair kval = getK(points, pointI, pointJ);
if(map.find(kval) == map.end())
map[kval] = 1;
else
++map[kval];
diffMax = max(diffMax, map[kval]);
}
maxPoint = max(maxPoint, diffMax + sameCnt);
}
return maxPoint;
}
};
我贴个我的算法吧，你贴个你的标准答案，比一下就好了,咱们思路差太多。
【在 i******s 的大作中提到】
: 忍不住替habbit说一句，如果枚举所有点，并且每次内循环前用新的hashmap的话，可
: 以只存斜率，因为此时之前一点已经固定(外层循环确定起始点)，所以可以用斜率做
: key。但是如果hashmap不是每次内循环前创建，而是在双重循序前创建，那么截距是一
: 定要的，光slope不够。还有这道题用slope有精度问题，
: 消除方法最简单就是换个直线表示方式，用Ax+By+C = 0。其中A, B和C都是整数，每两
: 个点构成的直线都这样表示，注意用gcd法保证A,B和C没有公约数，并且保证符号相
: 同(可以假设A永远是正)。而且这道题最大的trick是如何处理重复的点，一般没做过的
: 第一次做不一定想得到好办法。总体看之前的讨论无语了，跳出来说几句。
|
i******s
发帖数: 301 | 94 之前回的有误，请看我更正后的解答，你这样行是因为每次内循环前都clear了map。如
果换一个实现，则一定要存截距。anyway，slope的精度问题如果面试官死扣，那就只
能换Ax+By+C的表示方式，如果让过就过了。我碰到过both。
);
【在 h*******e 的大作中提到】
: namespace std {
: template <>
: struct hash >
: {
: typedef std::size_t result_type;
: result_type operator()(const pair & t) const
: { return ((long)t.first * 1000003 + t.second )& (((long)1<<32 ) - 1);
: }
: };
: }
|
h*******e
发帖数: 1377 | 95 我的是check 了 Ａ＝０ Ｂ＝０的情况其实并不是严格意义上的斜率，垂直水平
是 ０， １ 和 １， ０ 一轴心点加上一方向自然能确定一条直线。
【在 i******s 的大作中提到】
: 之前回的有误，请看我更正后的解答，你这样行是因为每次内循环前都clear了map。如
: 果换一个实现，则一定要存截距。anyway，slope的精度问题如果面试官死扣，那就只
: 能换Ax+By+C的表示方式，如果让过就过了。我碰到过both。
:
: );
|
i******s
发帖数: 301 | 96 你的解法没问题，只是要记得为什么可以不保存截距，只用"斜率"就可以。有的面试官
会confuse，因为可能他们没有想过如果每次内循环前清了map(或者创建一个新的)，则
截距不是必须的。因为一个点在外循环是已确定。如果碰上绕不过的新手面试官，建议
保存截距以迎合他们的口味。。。
【在 h*******e 的大作中提到】
: 我的是check 了 Ａ＝０ Ｂ＝０的情况其实并不是严格意义上的斜率，垂直水平
: 是 ０， １ 和 １， ０ 一轴心点加上一方向自然能确定一条直线。
|
p****e
发帖数: 3548 | 97 A,B,C的解法更局限一点吧，因为只适用于整数情况
如果点是浮点的话，还是要考虑精度问题
【在 i******s 的大作中提到】
: 之前回的有误，请看我更正后的解答，你这样行是因为每次内循环前都clear了map。如
: 果换一个实现，则一定要存截距。anyway，slope的精度问题如果面试官死扣，那就只
: 能换Ax+By+C的表示方式，如果让过就过了。我碰到过both。
:
: );
|
i******s
发帖数: 301 | 98 well, 一般遇到的都是point是int x, int y。如果面试官扣这个，那就只有跟他聊聊
怎么解决精度问题了。但对于都是int的情况，ABC法比较好。
【在 p****e 的大作中提到】
: A,B,C的解法更局限一点吧，因为只适用于整数情况
: 如果点是浮点的话，还是要考虑精度问题
|
h*******e
发帖数: 1377 | 99 浮点要考虑精度问题的而且这时候要重写 unordered_map的equal函数了， 我现在还
没想清楚为什么这个 哈希函数一定要外面加个namespace std才能通过。
这种template我之前也没见过 搜了一下发现叫做全特化模板。
【在 p****e 的大作中提到】
: A,B,C的解法更局限一点吧，因为只适用于整数情况
: 如果点是浮点的话，还是要考虑精度问题
|
h*******e
发帖数: 1377 | 100 轴心点 pointI 给定了 知道了 Ａ Ｂ就能知道 C了所以两个值就够了
【在 i******s 的大作中提到】
: 之前回的有误，请看我更正后的解答，你这样行是因为每次内循环前都clear了map。如
: 果换一个实现，则一定要存截距。anyway，slope的精度问题如果面试官死扣，那就只
: 能换Ax+By+C的表示方式，如果让过就过了。我碰到过both。
:
: );
|
|
|
f**********t
发帖数: 1001 | 101 struct Point {
int x;
int y;
Point() : x(0), y(0) {}
Point(int a, int b) : x(a), y(b) {}
};
class Solution {
static int gcd(int x, int y) {
while (y != 0) {
int temp = y;
y = x % y;
x = temp;
}
return x;
}
void Simplify(pair &pr) {
if (pr.first == 0 && pr.second == 0) {
return;
}
int z = Solution::gcd(pr.first, pr.second);
pr.first /= z;
pr.second /= z;
}
struct PairHash {
size_t operator() (const pair &pr) const {
return pr.first * 97 + pr.second;
}
};
public:
int maxPoints(vector &points) {
if (points.empty()) {
return 0;
}
int res = 0;
unordered_map, int, PairHash> um;
for (size_t i = 0; i + res < points.size(); ++i) {
for (size_t k = i + 1; k < points.size(); ++k) {
auto pr = make_pair(points[k].x - points[i].x,
points[k].y - points[i].y);
Simplify(pr);
++um[pr];
}
for (auto item : um) {
if (res < item.second) {
res = item.second;
}
}
um.clear();
}
return 1 + res;
}
}; |
w****a
发帖数: 710 | 102 这个用分数存key最好，但是要写个GCD做约分 |
w****a
发帖数: 710 | |
