logo
Redian新闻
>未名空间
>pets - 心有所宠
>
小美女奶昔——视察新家，多图~~
avatar
小美女奶昔——视察新家，多图~~# pets - 心有所宠
h*e
1 楼
rt
给定平面上n点，求在同一直线上最多点问题～～大家用double　/float 类型作hash
key么？
判断两个double /float 类型相等～～～　靠谱么
avatar
f*s
2 楼
以前搜索citation的时候无意中在一个数据库看到了我在中国的专利，都被翻译过来了
，而且格式也很规范。有谁知道是哪个数据库吗？或者哪个数据库的中国专利格式比较
规范的，麻烦分享一下。有包子答谢。
avatar
H*7
3 楼
慢慢的会知道的42件事
佛经上181条做人的道理
人生成熟的四个重要标志
人生应该记住的16句话
佛家经典禅语语录句子
改变人生的16个妙方
人生就要悟
感悟生活的真谛
11个笑话让你领悟人生
人一生要读的60本书（经典读书计划
女人一生的精彩
经典人生感悟生活感悟(推荐)
年轻时应该知道的道理
世界上最美丽的英文——人生短篇
编织人生：人生三十六字诀
成功秘诀
人生成功的21个信念
塑造阳光心态
成大事必备9种能力、9种手段、9种
我们工作到底为了什么--强烈推荐
如何正确的进行人生规划
改变你人生的50种方法
每天读一遍这7句话，让你更加自信
十七条黄金定律(拿破仑·希尔)
哈佛成功金言
自我激励的20个方法
年轻人应该谨记的十点
人生成败关键在于心态
成功人士的二十个习惯
时间管理101招
战胜自我就是成功
avatar
R*0
4 楼
自上周一与猫爸猫妈亲密接触以后，奶昔饮食正常，情绪稳(fanfu)定(wuchang)，曾经
被当成砂盆的南瓜窝也变成了好地方~~
每天晚饭时间，可乐和雪碧被邀请到包厢享受大餐，奶昔闻着俩陌生喵的味道淡去，小
心地踱到门外，四处张望
坐得好累，趴一会，翻过来，又翻过去，似乎真的没有什么危险了
这个黑黑的大盒子是什么东西，上去看看
啊，这里看起来很隐蔽，是个休息的好地方
没人看我吧，我去那边开阔地带转转
不好！有人来了！赶紧找机会回去！
就这样，奶昔每天在外面晃悠的时间越来越长，直到有一天，在被猫妈试图抚摸未果的
几分钟后勇敢地攻击了猫妈，为自己好好出了口气，然后，被关小黑屋三天。。。再然
后，被强迫剪了所有指甲。。。各种血泪描述详见以下回帖
http://www.mitbbs.com/article_t1/pets/32759971_0_2.html
http://www.mitbbs.com/article_t/pets/32759665.html
奶昔是不是自此就痛定思痛，决心重新做喵了呢？究竟什么时候可乐雪碧才可以安全见
到这位美若冰霜的小妹妹呢？让我们怀着最美好的期待吧~~
avatar
y*n
5 楼
不是可以设一个比较小的数， 0.0000001， 然后和这个数比较就可以吗？
avatar
z*i
6 楼
点播三：人生成熟的四个重要标志
我觉得这个应该最短

慢慢的会知道的42件事
佛经上181条做人的道理
人生成熟的四个重要标志
人生应该记住的16句话
佛家经典禅语语录句子
改变人生的16个妙方
人生就要悟
感悟生活的真谛
11个笑话让你领悟人生
人一生要读的60本书（经典读书计划
女人一生的精彩
经典人生感悟生活感悟(推荐)
年轻时应该知道的道理
世界上最美丽的英文——人生短篇
编织人生：人生三十六字诀
成功秘诀
人生成功的21个信念
塑造阳光心态
成大事必备9种能力、9种手段、9种
我们工作到底为了什么--强烈推荐
如何正确的进行人生规划
改变你人生的50种方法
每天读一遍这7句话，让你更加自信
十七条黄金定律(拿破仑·希尔)
哈佛成功金言
自我激励的20个方法
年轻人应该谨记的十点
人生成败关键在于心态
成功人士的二十个习惯
时间管理101招
战胜自我就是成功

【在 H******7 的大作中提到】
: 慢慢的会知道的42件事
: 佛经上181条做人的道理
: 人生成熟的四个重要标志
: 人生应该记住的16句话
: 佛家经典禅语语录句子
: 改变人生的16个妙方
: 人生就要悟
: 感悟生活的真谛
: 11个笑话让你领悟人生
: 人一生要读的60本书（经典读书计划
avatar
K*a
7 楼
赞多图！！！！奶昔太美了，看起来自在了不少啊。希望尽快和谐！！
avatar
h*e
8 楼
找到一个链接，关于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， 然后和这个数比较就可以吗？
avatar
H*g
9 楼
哈佛成功金言 跟哈图十五有什么关系吗？
avatar
R*0
10 楼
啊，酥酥妈，你这也太神速了~~昨晚把硬壳carrier放进奶昔的房间了，让她先熟悉熟
悉，看她什么时候愿意进去了，就跟可乐雪碧见一面看看

【在 K***a 的大作中提到】
: 赞多图！！！！奶昔太美了，看起来自在了不少啊。希望尽快和谐！！
avatar
s*x
11 楼
Cc150 介绍的非常清楚了吧？
avatar
R*a
12 楼

就是四个部位长毛了

【在 z***i 的大作中提到】
: 点播三：人生成熟的四个重要标志
: 我觉得这个应该最短
:
: 慢慢的会知道的42件事
: 佛经上181条做人的道理
: 人生成熟的四个重要标志
: 人生应该记住的16句话
: 佛家经典禅语语录句子
: 改变人生的16个妙方
: 人生就要悟
avatar
m*u
13 楼
赞美女
avatar
h*e
14 楼
记不清了，能告诉一下第几章地几题么。

【在 s**x 的大作中提到】
: Cc150 介绍的非常清楚了吧？
avatar
m*d
15 楼
第一个标志是熟记哈佛校训十二亿条

【在 z***i 的大作中提到】
: 点播三：人生成熟的四个重要标志
: 我觉得这个应该最短
:
: 慢慢的会知道的42件事
: 佛经上181条做人的道理
: 人生成熟的四个重要标志
: 人生应该记住的16句话
: 佛家经典禅语语录句子
: 改变人生的16个妙方
: 人生就要悟
avatar
c*y
16 楼
奶昔太漂亮了太漂亮了 而且手感一定很好~~~
可喜可贺啊都出来玩儿了
到时候是不是要跟原住民分别会面啊？不然她会不会以为那俩合伙欺负她。。。。
avatar
j*8
17 楼
正准备发个类似的问题，就在这里说了
有人面这题时因为用 double / float 作为 hashmap的key而被面试官说的吗？？
avatar
H*g
18 楼
大波， 励志
avatar
q*6
19 楼
奶昔还是越看越爱啊。。。看到你们一家帮她剪指甲那段我也不厚道的笑了。。。。
奶昔和两个原住民会不会变成郭芙和大武，小武的关系啊，哈哈啊哈

【在 R******0 的大作中提到】
: 自上周一与猫爸猫妈亲密接触以后，奶昔饮食正常，情绪稳(fanfu)定(wuchang)，曾经
: 被当成砂盆的南瓜窝也变成了好地方~~
: 每天晚饭时间，可乐和雪碧被邀请到包厢享受大餐，奶昔闻着俩陌生喵的味道淡去，小
: 心地踱到门外，四处张望
: 坐得好累，趴一会，翻过来，又翻过去，似乎真的没有什么危险了
: 这个黑黑的大盒子是什么东西，上去看看
: 啊，这里看起来很隐蔽，是个休息的好地方
: 没人看我吧，我去那边开阔地带转转
: 不好！有人来了！赶紧找机会回去！
: 就这样，奶昔每天在外面晃悠的时间越来越长，直到有一天，在被猫妈试图抚摸未果的
avatar
s*x
20 楼
自己查查

【在 h*******e 的大作中提到】
: 记不清了，能告诉一下第几章地几题么。
avatar
l*o
21 楼
有谁知道鸡汤喝多了什么后果？
avatar
R*0
22 楼
谢谢~~

【在 m*******u 的大作中提到】
: 赞美女
avatar
h*e
23 楼
翻了一遍没找到，好久不看了。
你用第四版吧 我是第五版，
第四版10.6 找到了， java 可以自定义类型作为key的，c++ 就不行。

【在 s**x 的大作中提到】
: 自己查查
avatar
H*g
24 楼
尿频得跟静芬一样

【在 l*****o 的大作中提到】
: 有谁知道鸡汤喝多了什么后果？
avatar
R*0
25 楼
哈哈，手感确实不错啊，就是短期内不敢再摸，实在是有阴影。。。你这个担心确实有
道理呐，到时候让可乐和雪碧分别出现吧，多少能减少一点紧张吧

【在 c******y 的大作中提到】
: 奶昔太漂亮了太漂亮了 而且手感一定很好~~~
: 可喜可贺啊都出来玩儿了
: 到时候是不是要跟原住民分别会面啊？不然她会不会以为那俩合伙欺负她。。。。
avatar
p*e
26 楼
可以取整，我就是这样做的
int slope = (int)(1000000.*float(p2.y-p1.y)/(p2.x-p1.x));
avatar
K*a
27 楼
哈哈哈，我当时picture了一下他们穿的厚厚的样子真心笑得不行了。MM总是特别有想
象力LOL

【在 q***6 的大作中提到】
: 奶昔还是越看越爱啊。。。看到你们一家帮她剪指甲那段我也不厚道的笑了。。。。
: 奶昔和两个原住民会不会变成郭芙和大武，小武的关系啊，哈哈啊哈
avatar
s*x
28 楼

第五版7.6

【在 h*******e 的大作中提到】
: 翻了一遍没找到，好久不看了。
: 你用第四版吧 我是第五版，
: 第四版10.6 找到了， java 可以自定义类型作为key的，c++ 就不行。
avatar
R*0
29 楼
凌乱了。。。可乐也是小女猫。。。我倒是想过和谐以后，奶昔会让可乐雪碧更黏糊一
点，现在俩猫都不会一起抱着睡觉互相舔毛什么的

【在 q***6 的大作中提到】
: 奶昔还是越看越爱啊。。。看到你们一家帮她剪指甲那段我也不厚道的笑了。。。。
: 奶昔和两个原住民会不会变成郭芙和大武，小武的关系啊，哈哈啊哈
avatar
h*e
30 楼
谢谢看到cc150给的方法了。觉得给的解法还是比较一般。。。计算几何里面很少用k
来决定点在一条直线上。k在靠近原点一小变很可能导致点在 距离原点远处一大变。

【在 s**x 的大作中提到】
:
: 第五版7.6
avatar
c*y
31 楼
奶昔尾巴还垂着 这娃戒心有多重啊。。。。。。
碰玩具不？喜欢catnip不？大鸟玩不玩？
avatar
g*e
32 楼
如果坐标是整数的话，斜率都是有理数。可以存pair


【在 h*******e 的大作中提到】
: rt
: 给定平面上n点，求在同一直线上最多点问题～～大家用double　/float 类型作hash
: key么？
: 判断两个double /float 类型相等～～～　靠谱么
avatar
g*y
33 楼
有的猫猫很需要耐心啊。。 我养了10年的猫，搬到新家也是藏床底下几个月。。。。
基本上我门回家才出来转悠一小会儿。。

【在 R******0 的大作中提到】
: 自上周一与猫爸猫妈亲密接触以后，奶昔饮食正常，情绪稳(fanfu)定(wuchang)，曾经
: 被当成砂盆的南瓜窝也变成了好地方~~
: 每天晚饭时间，可乐和雪碧被邀请到包厢享受大餐，奶昔闻着俩陌生喵的味道淡去，小
: 心地踱到门外，四处张望
: 坐得好累，趴一会，翻过来，又翻过去，似乎真的没有什么危险了
: 这个黑黑的大盒子是什么东西，上去看看
: 啊，这里看起来很隐蔽，是个休息的好地方
: 没人看我吧，我去那边开阔地带转转
: 不好！有人来了！赶紧找机会回去！
: 就这样，奶昔每天在外面晃悠的时间越来越长，直到有一天，在被猫妈试图抚摸未果的
avatar
h*e
34 楼
如果是pair作为 key 的话自定义的hash 函数一般怎么写
在 c++ unordered_set, int> 大牛给讲一下哦。

【在 g*********e 的大作中提到】
: 如果坐标是整数的话，斜率都是有理数。可以存pair


avatar
w*2
35 楼
哈哈，小美妞出来了，慢慢地会占领每一间房
avatar
g*e
36 楼
你写的对

【在 h*******e 的大作中提到】
: 如果是pair作为 key 的话自定义的hash 函数一般怎么写
: 在 c++ unordered_set, int> 大牛给讲一下哦。
avatar
R*0
37 楼
就是就是，想象力超越一切世俗的禁锢~~

【在 K***a 的大作中提到】
: 哈哈哈，我当时picture了一下他们穿的厚厚的样子真心笑得不行了。MM总是特别有想
: 象力LOL
avatar
h*e
38 楼
光是这个过不了leetcode的编译器阿，需要自定义hash 函数，和比较函数的似乎。

【在 g*********e 的大作中提到】
: 你写的对
avatar
I*e
39 楼
出了口气马上被关三天，LOL..
美猫！

【在 R******0 的大作中提到】
: 自上周一与猫爸猫妈亲密接触以后，奶昔饮食正常，情绪稳(fanfu)定(wuchang)，曾经
: 被当成砂盆的南瓜窝也变成了好地方~~
: 每天晚饭时间，可乐和雪碧被邀请到包厢享受大餐，奶昔闻着俩陌生喵的味道淡去，小
: 心地踱到门外，四处张望
: 坐得好累，趴一会，翻过来，又翻过去，似乎真的没有什么危险了
: 这个黑黑的大盒子是什么东西，上去看看
: 啊，这里看起来很隐蔽，是个休息的好地方
: 没人看我吧，我去那边开阔地带转转
: 不好！有人来了！赶紧找机会回去！
: 就这样，奶昔每天在外面晃悠的时间越来越长，直到有一天，在被猫妈试图抚摸未果的
avatar
P*L
40 楼
这样做是最好的，但是还得找最大公约数，容易超时过不了 oj。

【在 g*********e 的大作中提到】
: 如果坐标是整数的话，斜率都是有理数。可以存pair


avatar
z*e
41 楼
赞组图！很有real journalism的味道！
avatar
h*e
42 楼
要自己加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。
avatar
R*0
43 楼
是呀，典型的defensive aggression。。。
就在我被攻击之前的半小时左右，我们就在玩激光笔和大鸟，她会去扑，但比较缓慢，
估计还是有所保留，比如只往房间的一个方向扑，如果激光笔指到另一边就不去了。
现在看她这么出来逛游，我是真的有心理阴影，她一离我不到两米，我就紧张地要躲，
尤其是她快速向我靠近的时候。。。她也怕我，一有动静就立即努力贴着地往自己的房
间奔

【在 c******y 的大作中提到】
: 奶昔尾巴还垂着 这娃戒心有多重啊。。。。。。
: 碰玩具不？喜欢catnip不？大鸟玩不玩？
avatar
g*e
44 楼
set, int>
这个直接就可以用啊
想过leetcode的话用floating的比较就足够了，但google面试的时候我用floating的斜
率 Interviewer就不让过
avatar
R*0
45 楼
原来跟熟悉的人一起换环境也会这样啊，那我就再多加点耐心吧

【在 g*****y 的大作中提到】
: 有的猫猫很需要耐心啊。。 我养了10年的猫，搬到新家也是藏床底下几个月。。。。
: 基本上我门回家才出来转悠一小会儿。。
avatar
h*e
46 楼
google 是要求pair 做斜率么？
google是要求精确在一条直线上， 还是要求近似的可以有些误差的点也算一条线阿。
请大牛给细说说g关于这道题的要求阿。

【在 g*********e 的大作中提到】
: set, int>
: 这个直接就可以用啊
: 想过leetcode的话用floating的比较就足够了，但google面试的时候我用floating的斜
: 率 Interviewer就不让过
avatar
R*0
47 楼
希望这个过程不要太久，现在她还只觉得那个小卫生间是她自己最舒服最安全的地方

【在 w****2 的大作中提到】
: 哈哈，小美妞出来了，慢慢地会占领每一间房
avatar
g*e
48 楼

要精确的 不能用epsilon这样去比。不过也看面试官吧

【在 h*******e 的大作中提到】
: google 是要求pair 做斜率么？
: google是要求精确在一条直线上， 还是要求近似的可以有些误差的点也算一条线阿。
: 请大牛给细说说g关于这道题的要求阿。
avatar
Y*Y
49 楼
奶昔看来是狠角色啊！
avatar
h*e
50 楼
恩恩，多谢了。

【在 g*********e 的大作中提到】
:
: 要精确的 不能用epsilon这样去比。不过也看面试官吧
avatar
R*0
51 楼
是呀，后妈很过分~~当时查了一些关于aggressive猫猫的应对，很多就是建议先让猫猫
冷静下来，减少接触，适当饥饿，让她重新把我们跟美好的食物联系起来~~

【在 I********e 的大作中提到】
: 出了口气马上被关三天，LOL..
: 美猫！
avatar
f*5
52 楼

有一个思路不知道对不对，用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;
: }
avatar
R*0
53 楼
哈哈，虽然不敢当，但还是让后妈再乐一阵吧~~

【在 z*****e 的大作中提到】
: 赞组图！很有real journalism的味道！
avatar
s*5
54 楼
use hash of hash: unordered_map >

【在 h*******e 的大作中提到】
: 如果是pair作为 key 的话自定义的hash 函数一般怎么写
: 在 c++ unordered_set, int> 大牛给讲一下哦。
avatar
R*0
55 楼
正是，不能等闲视之啊

【在 Y******Y 的大作中提到】
: 奶昔看来是狠角色啊！
avatar
h*e
56 楼
我之前用的map 把 pair 的两个 int 变成string 中间加上
" "然后再加上 string 变成一个长string 你的方法也是对的一个 无理数唯一对应
一个非循环，和循环部分的组合。就是这个求循环节的过程比较麻烦了，估计你数学功
底很好，可以很快求出来。

【在 f*******5 的大作中提到】
:
: 有一个思路不知道对不对，用unordered_map, 因为点坐标是整数，所以
: 斜率可以表示成循环小数, 比如5/6=0.8(3)， 还没在leetcode上试，不知道能不能过
avatar
c*y
57 楼
肯出来转圈巡视总是个不小的进步！
猫奴不好当诶。。
唉只委屈了可乐雪碧 他俩招谁惹谁了就被限制活动范围了。。。

【在 R******0 的大作中提到】
: 是呀，典型的defensive aggression。。。
: 就在我被攻击之前的半小时左右，我们就在玩激光笔和大鸟，她会去扑，但比较缓慢，
: 估计还是有所保留，比如只往房间的一个方向扑，如果激光笔指到另一边就不去了。
: 现在看她这么出来逛游，我是真的有心理阴影，她一离我不到两米，我就紧张地要躲，
: 尤其是她快速向我靠近的时候。。。她也怕我，一有动静就立即努力贴着地往自己的房
: 间奔
avatar
h*e
58 楼
是不是key value类型写反了，而且复杂的类型做key比较麻烦在leetcode 定义就不可
以，vs2010定义没问题，但是往里面map[key]= val 赋值时候就编译不过了。

【在 s***5 的大作中提到】
: use hash of hash: unordered_map >
avatar
R*0
59 楼
是，肯出来已经不错了，最开始是开着门好几个小时也蹲在池子底下一动不动。可乐雪
碧的话，希望他们足够没心没肺吧，或者他们已经互相商量过也理解是怎么回事了，哈
哈~一天奶昔顶多出来两三个小时，应该还好。最希望的还是他们能尽早结束隔离啊

【在 c******y 的大作中提到】
: 肯出来转圈巡视总是个不小的进步！
: 猫奴不好当诶。。
: 唉只委屈了可乐雪碧 他俩招谁惹谁了就被限制活动范围了。。。
avatar
f*5
60 楼

有个Google面试题是求整数除法的循环，是不断用余数做被除数，用一个bool arr[10]
记录被除数，当前被除数如果见过就表示循环

【在 h*******e 的大作中提到】
: 是不是key value类型写反了，而且复杂的类型做key比较麻烦在leetcode 定义就不可
: 以，vs2010定义没问题，但是往里面map[key]= val 赋值时候就编译不过了。
avatar
k*e
61 楼
美貌的一般脾气都有点大～
你不理她几天估计她就会主动靠近你啦

【在 R******0 的大作中提到】
: 自上周一与猫爸猫妈亲密接触以后，奶昔饮食正常，情绪稳(fanfu)定(wuchang)，曾经
: 被当成砂盆的南瓜窝也变成了好地方~~
: 每天晚饭时间，可乐和雪碧被邀请到包厢享受大餐，奶昔闻着俩陌生喵的味道淡去，小
: 心地踱到门外，四处张望
: 坐得好累，趴一会，翻过来，又翻过去，似乎真的没有什么危险了
: 这个黑黑的大盒子是什么东西，上去看看
: 啊，这里看起来很隐蔽，是个休息的好地方
: 没人看我吧，我去那边开阔地带转转
: 不好！有人来了！赶紧找机会回去！
: 就这样，奶昔每天在外面晃悠的时间越来越长，直到有一天，在被猫妈试图抚摸未果的
avatar
h*e
62 楼
呵呵，估计写得好能小impress面试官一下，本想出一道难题，没成想面试者一口气完
成了两道难题。

10]

【在 f*******5 的大作中提到】
:
: 有个Google面试题是求整数除法的循环，是不断用余数做被除数，用一个bool arr[10]
: 记录被除数，当前被除数如果见过就表示循环
avatar
c*y
63 楼
他们互相安慰希望没事
道路曲折了点儿但前途一定很光明啦！
也给个大馅儿包子安慰安慰

【在 R******0 的大作中提到】
: 是，肯出来已经不错了，最开始是开着门好几个小时也蹲在池子底下一动不动。可乐雪
: 碧的话，希望他们足够没心没肺吧，或者他们已经互相商量过也理解是怎么回事了，哈
: 哈~一天奶昔顶多出来两三个小时，应该还好。最希望的还是他们能尽早结束隔离啊
avatar
y*n
64 楼
那Sqrt 那个题可以用epsilon吗？

【在 g*********e 的大作中提到】
:
: 要精确的 不能用epsilon这样去比。不过也看面试官吧
avatar
N*t
65 楼
终于出来了阿，不错不错，有进步～
奶昔在以前的家里是不是从很小开始独猫养的？我见过俩狠角色都是这样，玛雅，压力
山大，赞mm勇气可嘉
avatar
g*e
66 楼
记得数学的算cross product
不记得的斜率公式转换一下变乘法，其实就是叉乘

【在 g*********e 的大作中提到】
: set, int>
: 这个直接就可以用啊
: 想过leetcode的话用floating的比较就足够了，但google面试的时候我用floating的斜
: 率 Interviewer就不让过
avatar
R*0
67 楼
还真是这样的，关了三天小黑屋以后感觉奶昔更乖了，开门也不hiss了，反而是很温柔
喵喵地叫，还疑似翻肚皮，隔着门叫她名字，她也喵喵地回应，不知道是不是真的想亲
近，还是跟她的外表一样容易蛊惑人啊~~

【在 k*******e 的大作中提到】
: 美貌的一般脾气都有点大～
: 你不理她几天估计她就会主动靠近你啦
avatar
g*e
68 楼
表示成2/7=0.[285714]

10]

【在 f*******5 的大作中提到】
:
: 有个Google面试题是求整数除法的循环，是不断用余数做被除数，用一个bool arr[10]
: 记录被除数，当前被除数如果见过就表示循环
avatar
R*0
69 楼
谢谢猫糖~~大包子真好吃~~~

【在 c******y 的大作中提到】
: 他们互相安慰希望没事
: 道路曲折了点儿但前途一定很光明啦！
: 也给个大馅儿包子安慰安慰
avatar
g*e
70 楼
可以

【在 y***n 的大作中提到】
: 那Sqrt 那个题可以用epsilon吗？
avatar
R*0
71 楼
没错没错，就是四周大从shelter去了前主人家，9个月被我领回来，一直是一只喵在家
，只有隔壁一只outdoor的壮男brown tabby时不时地来看她，我们去领奶昔的时候还见
到这个大男猫在门口守着，听说也没有正式接触过，奶昔一见对方就躲进里屋。
我们全家都是被那两张照片迷失了心智啊，没想到独猫rehome是这个样子的，嘿嘿~~你
见过的那俩狠角色是什么情况啊

【在 N******t 的大作中提到】
: 终于出来了阿，不错不错，有进步～
: 奶昔在以前的家里是不是从很小开始独猫养的？我见过俩狠角色都是这样，玛雅，压力
: 山大，赞mm勇气可嘉
avatar
y*n
72 楼
你搞得那么细，以后可以写一本书。每个题写：
A. 基本解法。
A-1. Google解法。
A-2。Facebook 解法。
A-3。 Linkedin解法。

【在 h*******e 的大作中提到】
: google 是要求pair 做斜率么？
: google是要求精确在一条直线上， 还是要求近似的可以有些误差的点也算一条线阿。
: 请大牛给细说说g关于这道题的要求阿。
avatar
N*t
73 楼
我见过的那俩，一个我cat sit过N次包括过夜，一个在我家呆了好几天，俩我都没摸到
过一根毛阿，在他们附近走路都是拿东西挡着腿 T_T 我承认我心理脆弱
不过他们跟各自的妈都是亲的不得了，mm应该很快会守得云开见月明～

【在 R******0 的大作中提到】
: 没错没错，就是四周大从shelter去了前主人家，9个月被我领回来，一直是一只喵在家
: ，只有隔壁一只outdoor的壮男brown tabby时不时地来看她，我们去领奶昔的时候还见
: 到这个大男猫在门口守着，听说也没有正式接触过，奶昔一见对方就躲进里屋。
: 我们全家都是被那两张照片迷失了心智啊，没想到独猫rehome是这个样子的，嘿嘿~~你
: 见过的那俩狠角色是什么情况啊
avatar
h*e
74 楼
你多做些计算几何题就知道了，计算几何差一点就差很多， 比如三点共线的标准方法
就是叉乘面积近似为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解法。
avatar
z*e
75 楼
别介~猫猫心思敏感，看你躲她，说不定更 confused了呢~这时一定要拿出正牌猫奴的
架势把她给镇住。嗯~

【在 R******0 的大作中提到】
: 是呀，典型的defensive aggression。。。
: 就在我被攻击之前的半小时左右，我们就在玩激光笔和大鸟，她会去扑，但比较缓慢，
: 估计还是有所保留，比如只往房间的一个方向扑，如果激光笔指到另一边就不去了。
: 现在看她这么出来逛游，我是真的有心理阴影，她一离我不到两米，我就紧张地要躲，
: 尤其是她快速向我靠近的时候。。。她也怕我，一有动静就立即努力贴着地往自己的房
: 间奔
avatar
h*t
76 楼

这个能再多解释一下吗？

【在 g**e 的大作中提到】
: 记得数学的算cross product
: 不记得的斜率公式转换一下变乘法，其实就是叉乘
avatar
K*a
77 楼
拿东西挡着腿。。。。笑S了

【在 N******t 的大作中提到】
: 我见过的那俩，一个我cat sit过N次包括过夜，一个在我家呆了好几天，俩我都没摸到
: 过一根毛阿，在他们附近走路都是拿东西挡着腿 T_T 我承认我心理脆弱
: 不过他们跟各自的妈都是亲的不得了，mm应该很快会守得云开见月明～
avatar
h*t
78 楼

弱问一句：为什么只存 slope作为key呢， 不需要存和 y轴交点吗？

【在 h*******e 的大作中提到】
: 如果是pair作为 key 的话自定义的hash 函数一般怎么写
: 在 c++ unordered_set, int> 大牛给讲一下哦。
avatar
R*0
79 楼
“在他们附近走路都是拿东西挡着腿”，我现在差不多就想这样，太理解了~~希望奶昔
早点认我作亲妈~~

【在 N******t 的大作中提到】
: 我见过的那俩，一个我cat sit过N次包括过夜，一个在我家呆了好几天，俩我都没摸到
: 过一根毛阿，在他们附近走路都是拿东西挡着腿 T_T 我承认我心理脆弱
: 不过他们跟各自的妈都是亲的不得了，mm应该很快会守得云开见月明～
avatar
h*e
80 楼
不同的2点确定一条直线，确定一个直线方程，确定一斜率。

【在 h****t 的大作中提到】
:
: 弱问一句：为什么只存 slope作为key呢， 不需要存和 y轴交点吗？
avatar
R*0
81 楼
好难啊~这真的需要无比强大的心理~~
短期内我就先多穿点好了，再拿出正牌猫奴的架势，哈！

【在 z*****e 的大作中提到】
: 别介~猫猫心思敏感，看你躲她，说不定更 confused了呢~这时一定要拿出正牌猫奴的
: 架势把她给镇住。嗯~
avatar
h*t
82 楼
我的意思是 会存在2条不同的平行直线（相同斜率）。
只存斜率无法区分这2条不同直线。

【在 h*******e 的大作中提到】
: 不同的2点确定一条直线，确定一个直线方程，确定一斜率。
avatar
R*0
83 楼
真事啊，照片里那个红灰相见的beanbag chair就经常被我们拿来挡着。。。

【在 K***a 的大作中提到】
: 拿东西挡着腿。。。。笑S了
avatar
h*e
84 楼
我感觉你对这道题的总体思路还没有概念，为了不spoil你刷题的乐趣，你可以尝试思
考并且做一下leetcode第三题。max points on a line.

【在 h****t 的大作中提到】
: 我的意思是 会存在2条不同的平行直线（相同斜率）。
: 只存斜率无法区分这2条不同直线。
avatar
H*o
85 楼
小美女好有性格啊，这么看起来lz我碰到的猫脾气都很好很好啊。。。。
有朋友家的猫放我家寄养。来了以后就四处视察，见到我的猫炸毛也无所谓。看到人就
翻肚皮求吃的。。。。
有我家二毛，来了以后隔离在厕所，听到我的声音，隔着厕所门都能听见她打呼噜的咕
咕声音。见到我亲的就像见到了娘。只要放出厕所，立刻上蹿下跳。把家里大猫搞得不
能安生。。。
avatar
h*t
86 楼
不知道你的感觉从何而来。
2年前面世时就被问过这题并且答案通过。leetcode什么的其它不多说了，没刷过的人
现在不多了。
"总体思路还没有概念"，嘿嘿，嘿嘿。我一笑而过。

【在 h*******e 的大作中提到】
: 我感觉你对这道题的总体思路还没有概念，为了不spoil你刷题的乐趣，你可以尝试思
: 考并且做一下leetcode第三题。max points on a line.
avatar
b*e
87 楼
指甲剪掉强抱是王道，俺最近就收拾了一只，三两天就主动爬上肚子了

【在 R******0 的大作中提到】
: “在他们附近走路都是拿东西挡着腿”，我现在差不多就想这样，太理解了~~希望奶昔
: 早点认我作亲妈~~
avatar
y*n
88 楼
他应该不是用 slope作为key呢

【在 h****t 的大作中提到】
: 不知道你的感觉从何而来。
: 2年前面世时就被问过这题并且答案通过。leetcode什么的其它不多说了，没刷过的人
: 现在不多了。
: "总体思路还没有概念"，嘿嘿，嘿嘿。我一笑而过。
avatar
N*t
89 楼
真的会突然尖叫着冲上来攻击阿。。。吓死我的小心肝了

【在 K***a 的大作中提到】
: 拿东西挡着腿。。。。笑S了
avatar
h*e
90 楼
哦那就是你刷题和我们大多数人的思路很不同哦，不妨你也介绍一下你的做法，大家开
阔思路哦。
我们是算每点和其他点的斜率，用斜率为key做hashmap,　看和本点相连的其他点落在
每个斜率内的有几个。　然后枚举这个轴心点　这样算法复杂度O(N*N)
我们现在都是用斜率作key　整个帖子纠结的是斜率怎么存和相应的精确度的问题，看
你说似乎不是用斜率做key,
所以开始还以为你没做过呢。

【在 h****t 的大作中提到】
: 不知道你的感觉从何而来。
: 2年前面世时就被问过这题并且答案通过。leetcode什么的其它不多说了，没刷过的人
: 现在不多了。
: "总体思路还没有概念"，嘿嘿，嘿嘿。我一笑而过。
avatar
B*A
91 楼
美女！
avatar
i*s
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,
: 所以开始还以为你没做过呢。
avatar
L*3
93 楼
哈哈哈，美女果然有脾气！

【在 R******0 的大作中提到】
: “在他们附近走路都是拿东西挡着腿”，我现在差不多就想这样，太理解了~~希望奶昔
: 早点认我作亲妈~~
avatar
h*e
94 楼
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是如何处理重复的点，一般没做过的
: 第一次做不一定想得到好办法。总体看之前的讨论无语了，跳出来说几句。
avatar
R*0
95 楼
是啊，我之前自己家的朋友家的再加上shelter volunteer见过的，也不少猫了，从来
没想过小猫咪能这么凶这么有杀伤力。。。以前总觉得my cat from hell离自己很遥远
。。。

【在 H******o 的大作中提到】
: 小美女好有性格啊，这么看起来lz我碰到的猫脾气都很好很好啊。。。。
: 有朋友家的猫放我家寄养。来了以后就四处视察，见到我的猫炸毛也无所谓。看到人就
: 翻肚皮求吃的。。。。
: 有我家二毛，来了以后隔离在厕所，听到我的声音，隔着厕所门都能听见她打呼噜的咕
: 咕声音。见到我亲的就像见到了娘。只要放出厕所，立刻上蹿下跳。把家里大猫搞得不
: 能安生。。。
avatar
i*s
96 楼
之前回的有误，请看我更正后的解答，你这样行是因为每次内循环前都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);
: }
: };
: }
avatar
R*0
97 楼
指甲前天晚上虐猫一般地剪掉了，强抱是绝对不敢的，欢迎来我家尝试。。。

【在 b*****e 的大作中提到】
: 指甲剪掉强抱是王道，俺最近就收拾了一只，三两天就主动爬上肚子了
avatar
h*e
98 楼
我的是check　了　Ａ＝０　　Ｂ＝０的情况其实并不是严格意义上的斜率，垂直水平
是　０，　１　和　１，　０　一轴心点加上一方向自然能确定一条直线。

【在 i******s 的大作中提到】
: 之前回的有误，请看我更正后的解答，你这样行是因为每次内循环前都clear了map。如
: 果换一个实现，则一定要存截距。anyway，slope的精度问题如果面试官死扣，那就只
: 能换Ax+By+C的表示方式，如果让过就过了。我碰到过both。
:
: );
avatar
R*0
99 楼
含泪握手。。。真的是这样的。。。

【在 N******t 的大作中提到】
: 真的会突然尖叫着冲上来攻击阿。。。吓死我的小心肝了
avatar
i*s
100 楼
你的解法没问题，只是要记得为什么可以不保存截距，只用"斜率"就可以。有的面试官
会confuse，因为可能他们没有想过如果每次内循环前清了map(或者创建一个新的)，则
截距不是必须的。因为一个点在外循环是已确定。如果碰上绕不过的新手面试官，建议
保存截距以迎合他们的口味。。。

【在 h*******e 的大作中提到】
: 我的是check　了　Ａ＝０　　Ｂ＝０的情况其实并不是严格意义上的斜率，垂直水平
: 是　０，　１　和　１，　０　一轴心点加上一方向自然能确定一条直线。
avatar
R*0
101 楼
谢谢！这就是我目前最大的安慰了~~

【在 B**********A 的大作中提到】
: 美女！
avatar
p*e
102 楼
A,B,C的解法更局限一点吧，因为只适用于整数情况
如果点是浮点的话，还是要考虑精度问题

【在 i******s 的大作中提到】
: 之前回的有误，请看我更正后的解答，你这样行是因为每次内循环前都clear了map。如
: 果换一个实现，则一定要存截距。anyway，slope的精度问题如果面试官死扣，那就只
: 能换Ax+By+C的表示方式，如果让过就过了。我碰到过both。
:
: );
avatar
b*e
103 楼
给个地址吧，俺知道你也在猴子屯，让俺来教你怎么强抱猫

【在 R******0 的大作中提到】
: 指甲前天晚上虐猫一般地剪掉了，强抱是绝对不敢的，欢迎来我家尝试。。。
avatar
i*s
104 楼
well, 一般遇到的都是point是int x, int y。如果面试官扣这个，那就只有跟他聊聊
怎么解决精度问题了。但对于都是int的情况，ABC法比较好。

【在 p****e 的大作中提到】
: A,B,C的解法更局限一点吧，因为只适用于整数情况
: 如果点是浮点的话，还是要考虑精度问题
avatar
R*0
105 楼
是啊，有时候看奶昔那么漂亮趴在那就想，怎么能这么凶呢？太迷惑人了

【在 L*********3 的大作中提到】
: 哈哈哈，美女果然有脾气！
avatar
h*e
106 楼
浮点要考虑精度问题的而且这时候要重写 unordered_map的equal函数了，　我现在还
没想清楚为什么这个 哈希函数一定要外面加个namespace std才能通过。
这种template我之前也没见过　搜了一下发现叫做全特化模板。

【在 p****e 的大作中提到】
: A,B,C的解法更局限一点吧，因为只适用于整数情况
: 如果点是浮点的话，还是要考虑精度问题
avatar
N*t
107 楼
其实猫还是很可怜阿，他们攻击也是因为太害怕了，觉得实在被逼的走投无路了。问题
是跟他示好他也不领情。。。我觉得可能还是冷处理，晾着他比较好

【在 R******0 的大作中提到】
: 含泪握手。。。真的是这样的。。。
avatar
h*e
108 楼
轴心点　pointI 给定了　知道了　Ａ　Ｂ就能知道　　C了所以两个值就够了

【在 i******s 的大作中提到】
: 之前回的有误，请看我更正后的解答，你这样行是因为每次内循环前都clear了map。如
: 果换一个实现，则一定要存截距。anyway，slope的精度问题如果面试官死扣，那就只
: 能换Ax+By+C的表示方式，如果让过就过了。我碰到过both。
:
: );
avatar
R*0
109 楼
就是这样啊，其实很想让她知道我们一点都不可怕。。。所以我想要不要早点让可乐雪
碧跟奶昔见面，告诉她我们都是好人~~要等奶昔对我们完全放下戒备再让他们仨见面的
话，不知道还要多久啊

【在 N******t 的大作中提到】
: 其实猫还是很可怜阿，他们攻击也是因为太害怕了，觉得实在被逼的走投无路了。问题
: 是跟他示好他也不领情。。。我觉得可能还是冷处理，晾着他比较好
avatar
h*e
110 楼
rt
给定平面上n点，求在同一直线上最多点问题～～大家用double　/float 类型作hash
key么？
判断两个double /float 类型相等～～～　靠谱么
avatar
g*y
111 楼
我养老二的时候被攻击过多次，整个手臂伤痕累累。 直到半年多，还会时不时hiss一
下。 2年后开始亲人，现在10年了，温柔的不行。。。。 漫长的过程。

【在 R******0 的大作中提到】
: 含泪握手。。。真的是这样的。。。
avatar
y*n
112 楼
不是可以设一个比较小的数， 0.0000001， 然后和这个数比较就可以吗？
avatar
R*0
113 楼
啊，我真是倍受鼓舞啊！看来我之前开玩笑说的一年期限还真有必要。。。

【在 g*****y 的大作中提到】
: 我养老二的时候被攻击过多次，整个手臂伤痕累累。 直到半年多，还会时不时hiss一
: 下。 2年后开始亲人，现在10年了，温柔的不行。。。。 漫长的过程。
avatar
h*e
114 楼
找到一个链接，关于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， 然后和这个数比较就可以吗？
avatar
x*a
115 楼
美得无法自拔...

【在 R******0 的大作中提到】
: 自上周一与猫爸猫妈亲密接触以后，奶昔饮食正常，情绪稳(fanfu)定(wuchang)，曾经
: 被当成砂盆的南瓜窝也变成了好地方~~
: 每天晚饭时间，可乐和雪碧被邀请到包厢享受大餐，奶昔闻着俩陌生喵的味道淡去，小
: 心地踱到门外，四处张望
: 坐得好累，趴一会，翻过来，又翻过去，似乎真的没有什么危险了
: 这个黑黑的大盒子是什么东西，上去看看
: 啊，这里看起来很隐蔽，是个休息的好地方
: 没人看我吧，我去那边开阔地带转转
: 不好！有人来了！赶紧找机会回去！
: 就这样，奶昔每天在外面晃悠的时间越来越长，直到有一天，在被猫妈试图抚摸未果的
avatar
s*x
116 楼
Cc150 介绍的非常清楚了吧？
avatar
P*D
117 楼
最近去你家那只？这么刺激啊，早知道就竞争一下了

★ 发自iPhone App: ChineseWeb 7.8

【在 N******t 的大作中提到】
: 真的会突然尖叫着冲上来攻击阿。。。吓死我的小心肝了
avatar
h*e
118 楼
记不清了，能告诉一下第几章地几题么。

【在 s**x 的大作中提到】
: Cc150 介绍的非常清楚了吧？
avatar
R*0
119 楼
太荣幸了~~

【在 x*********a 的大作中提到】
: 美得无法自拔...
avatar
j*8
120 楼
正准备发个类似的问题，就在这里说了
有人面这题时因为用 double / float 作为 hashmap的key而被面试官说的吗？？
avatar
l*y
121 楼
惜惜太美貌了，抱来亲亲。 赞妹妹和家人！都好有爱心和耐心！
avatar
s*x
122 楼
自己查查

【在 h*******e 的大作中提到】
: 记不清了，能告诉一下第几章地几题么。
avatar
w*i
123 楼
太美了 摸摸
avatar
h*e
124 楼
翻了一遍没找到，好久不看了。
你用第四版吧 我是第五版，
第四版10.6 找到了， java 可以自定义类型作为key的，c++ 就不行。

【在 s**x 的大作中提到】
: 自己查查
avatar
R*0
125 楼
争取能早点抱着亲亲啊~~好久没见Abby了，现在怎么样啊

【在 l*********y 的大作中提到】
: 惜惜太美貌了，抱来亲亲。 赞妹妹和家人！都好有爱心和耐心！
avatar
p*e
126 楼
可以取整，我就是这样做的
int slope = (int)(1000000.*float(p2.y-p1.y)/(p2.x-p1.x));
avatar
R*0
127 楼
目前在脑门啊下巴啊脖子附近摸摸都还比较安全。。。

【在 w******i 的大作中提到】
: 太美了 摸摸
avatar
s*x
128 楼

第五版7.6

【在 h*******e 的大作中提到】
: 翻了一遍没找到，好久不看了。
: 你用第四版吧 我是第五版，
: 第四版10.6 找到了， java 可以自定义类型作为key的，c++ 就不行。
avatar
w*i
129 楼
笑死了 我家的也随时发作阿 有时候一边purr一边冲上来攻击

【在 R******0 的大作中提到】
: 目前在脑门啊下巴啊脖子附近摸摸都还比较安全。。。
avatar
h*e
130 楼
谢谢看到cc150给的方法了。觉得给的解法还是比较一般。。。计算几何里面很少用k
来决定点在一条直线上。k在靠近原点一小变很可能导致点在 距离原点远处一大变。

【在 s**x 的大作中提到】
:
: 第五版7.6
avatar
l*y
131 楼
Abby依旧是个乖孩子，见到谁到我家了，也不管人不认识就往人家身上蹭和闻，绝对是
个狗狗猫，呵呵。 他现在都快12磅了。

【在 R******0 的大作中提到】
: 争取能早点抱着亲亲啊~~好久没见Abby了，现在怎么样啊
avatar
g*e
132 楼
如果坐标是整数的话，斜率都是有理数。可以存pair


【在 h*******e 的大作中提到】
: rt
: 给定平面上n点，求在同一直线上最多点问题～～大家用double　/float 类型作hash
: key么？
: 判断两个double /float 类型相等～～～　靠谱么
avatar
R*0
133 楼
看来美猫真是会脾气大一些啊，一点点不爽都要表现出来~~~

【在 w******i 的大作中提到】
: 笑死了 我家的也随时发作阿 有时候一边purr一边冲上来攻击
avatar
h*e
134 楼
如果是pair作为 key 的话自定义的hash 函数一般怎么写
在 c++ unordered_set, int> 大牛给讲一下哦。

【在 g*********e 的大作中提到】
: 如果坐标是整数的话，斜率都是有理数。可以存pair


avatar
R*0
135 楼
一直在茁壮成长啊！雪碧彻底停在11磅了，8个月没变过了。。。可乐雪碧见客人也是
可大方了，希望能给奶昔带个好榜样~~

【在 l*********y 的大作中提到】
: Abby依旧是个乖孩子，见到谁到我家了，也不管人不认识就往人家身上蹭和闻，绝对是
: 个狗狗猫，呵呵。 他现在都快12磅了。
avatar
g*e
136 楼
你写的对

【在 h*******e 的大作中提到】
: 如果是pair作为 key 的话自定义的hash 函数一般怎么写
: 在 c++ unordered_set, int> 大牛给讲一下哦。
avatar
l*y
137 楼
说实话abby真不是吃过，我上周试着把肉塞到他嘴里，让他尝一下，想着说不定就喜欢
吃了，结果这货直接给我吐出来了。雪碧对奶昔没问题，估计可乐会有点小心眼，呵呵

【在 R******0 的大作中提到】
: 一直在茁壮成长啊！雪碧彻底停在11磅了，8个月没变过了。。。可乐雪碧见客人也是
: 可大方了，希望能给奶昔带个好榜样~~
avatar
h*e
138 楼
光是这个过不了leetcode的编译器阿，需要自定义hash 函数，和比较函数的似乎。

【在 g*********e 的大作中提到】
: 你写的对
avatar
s*a
139 楼
太美了

【在 R******0 的大作中提到】
: 自上周一与猫爸猫妈亲密接触以后，奶昔饮食正常，情绪稳(fanfu)定(wuchang)，曾经
: 被当成砂盆的南瓜窝也变成了好地方~~
: 每天晚饭时间，可乐和雪碧被邀请到包厢享受大餐，奶昔闻着俩陌生喵的味道淡去，小
: 心地踱到门外，四处张望
: 坐得好累，趴一会，翻过来，又翻过去，似乎真的没有什么危险了
: 这个黑黑的大盒子是什么东西，上去看看
: 啊，这里看起来很隐蔽，是个休息的好地方
: 没人看我吧，我去那边开阔地带转转
: 不好！有人来了！赶紧找机会回去！
: 就这样，奶昔每天在外面晃悠的时间越来越长，直到有一天，在被猫妈试图抚摸未果的
avatar
P*L
140 楼
这样做是最好的，但是还得找最大公约数，容易超时过不了 oj。

【在 g*********e 的大作中提到】
: 如果坐标是整数的话，斜率都是有理数。可以存pair


avatar
f*a
141 楼
小奶昔太美了!!! 好俏丽啊
avatar
h*e
142 楼
要自己加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。
avatar
g*e
143 楼
set, int>
这个直接就可以用啊
想过leetcode的话用floating的比较就足够了，但google面试的时候我用floating的斜
率 Interviewer就不让过
avatar
h*e
144 楼
google 是要求pair 做斜率么？
google是要求精确在一条直线上， 还是要求近似的可以有些误差的点也算一条线阿。
请大牛给细说说g关于这道题的要求阿。

【在 g*********e 的大作中提到】
: set, int>
: 这个直接就可以用啊
: 想过leetcode的话用floating的比较就足够了，但google面试的时候我用floating的斜
: 率 Interviewer就不让过
avatar
g*e
145 楼

要精确的 不能用epsilon这样去比。不过也看面试官吧

【在 h*******e 的大作中提到】
: google 是要求pair 做斜率么？
: google是要求精确在一条直线上， 还是要求近似的可以有些误差的点也算一条线阿。
: 请大牛给细说说g关于这道题的要求阿。
avatar
h*e
146 楼
恩恩，多谢了。

【在 g*********e 的大作中提到】
:
: 要精确的 不能用epsilon这样去比。不过也看面试官吧
avatar
f*5
147 楼

有一个思路不知道对不对，用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;
: }
avatar
s*5
148 楼
use hash of hash: unordered_map >

【在 h*******e 的大作中提到】
: 如果是pair作为 key 的话自定义的hash 函数一般怎么写
: 在 c++ unordered_set, int> 大牛给讲一下哦。
avatar
h*e
149 楼
我之前用的map 把 pair 的两个 int 变成string 中间加上
" "然后再加上 string 变成一个长string 你的方法也是对的一个 无理数唯一对应
一个非循环，和循环部分的组合。就是这个求循环节的过程比较麻烦了，估计你数学功
底很好，可以很快求出来。

【在 f*******5 的大作中提到】
:
: 有一个思路不知道对不对，用unordered_map, 因为点坐标是整数，所以
: 斜率可以表示成循环小数, 比如5/6=0.8(3)， 还没在leetcode上试，不知道能不能过
avatar
h*e
150 楼
是不是key value类型写反了，而且复杂的类型做key比较麻烦在leetcode 定义就不可
以，vs2010定义没问题，但是往里面map[key]= val 赋值时候就编译不过了。

【在 s***5 的大作中提到】
: use hash of hash: unordered_map >
avatar
f*5
151 楼

有个Google面试题是求整数除法的循环，是不断用余数做被除数，用一个bool arr[10]
记录被除数，当前被除数如果见过就表示循环

【在 h*******e 的大作中提到】
: 是不是key value类型写反了，而且复杂的类型做key比较麻烦在leetcode 定义就不可
: 以，vs2010定义没问题，但是往里面map[key]= val 赋值时候就编译不过了。
avatar
h*e
152 楼
呵呵，估计写得好能小impress面试官一下，本想出一道难题，没成想面试者一口气完
成了两道难题。

10]

【在 f*******5 的大作中提到】
:
: 有个Google面试题是求整数除法的循环，是不断用余数做被除数，用一个bool arr[10]
: 记录被除数，当前被除数如果见过就表示循环
avatar
y*n
153 楼
那Sqrt 那个题可以用epsilon吗？

【在 g*********e 的大作中提到】
:
: 要精确的 不能用epsilon这样去比。不过也看面试官吧
avatar
g*e
154 楼
记得数学的算cross product
不记得的斜率公式转换一下变乘法，其实就是叉乘

【在 g*********e 的大作中提到】
: set, int>
: 这个直接就可以用啊
: 想过leetcode的话用floating的比较就足够了，但google面试的时候我用floating的斜
: 率 Interviewer就不让过
avatar
g*e
155 楼
表示成2/7=0.[285714]

10]

【在 f*******5 的大作中提到】
:
: 有个Google面试题是求整数除法的循环，是不断用余数做被除数，用一个bool arr[10]
: 记录被除数，当前被除数如果见过就表示循环
avatar
g*e
156 楼
可以

【在 y***n 的大作中提到】
: 那Sqrt 那个题可以用epsilon吗？
avatar
y*n
157 楼
你搞得那么细，以后可以写一本书。每个题写：
A. 基本解法。
A-1. Google解法。
A-2。Facebook 解法。
A-3。 Linkedin解法。

【在 h*******e 的大作中提到】
: google 是要求pair 做斜率么？
: google是要求精确在一条直线上， 还是要求近似的可以有些误差的点也算一条线阿。
: 请大牛给细说说g关于这道题的要求阿。
avatar
h*e
158 楼
你多做些计算几何题就知道了，计算几何差一点就差很多， 比如三点共线的标准方法
就是叉乘面积近似为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解法。
avatar
h*t
159 楼

这个能再多解释一下吗？

【在 g**e 的大作中提到】
: 记得数学的算cross product
: 不记得的斜率公式转换一下变乘法，其实就是叉乘
avatar
h*t
160 楼

弱问一句：为什么只存 slope作为key呢， 不需要存和 y轴交点吗？

【在 h*******e 的大作中提到】
: 如果是pair作为 key 的话自定义的hash 函数一般怎么写
: 在 c++ unordered_set, int> 大牛给讲一下哦。
avatar
h*e
161 楼
不同的2点确定一条直线，确定一个直线方程，确定一斜率。

【在 h****t 的大作中提到】
:
: 弱问一句：为什么只存 slope作为key呢， 不需要存和 y轴交点吗？
avatar
h*t
162 楼
我的意思是 会存在2条不同的平行直线（相同斜率）。
只存斜率无法区分这2条不同直线。

【在 h*******e 的大作中提到】
: 不同的2点确定一条直线，确定一个直线方程，确定一斜率。
avatar
h*e
163 楼
我感觉你对这道题的总体思路还没有概念，为了不spoil你刷题的乐趣，你可以尝试思
考并且做一下leetcode第三题。max points on a line.

【在 h****t 的大作中提到】
: 我的意思是 会存在2条不同的平行直线（相同斜率）。
: 只存斜率无法区分这2条不同直线。
avatar
h*t
164 楼
不知道你的感觉从何而来。
2年前面世时就被问过这题并且答案通过。leetcode什么的其它不多说了，没刷过的人
现在不多了。
"总体思路还没有概念"，嘿嘿，嘿嘿。我一笑而过。

【在 h*******e 的大作中提到】
: 我感觉你对这道题的总体思路还没有概念，为了不spoil你刷题的乐趣，你可以尝试思
: 考并且做一下leetcode第三题。max points on a line.
avatar
y*n
165 楼
他应该不是用 slope作为key呢

【在 h****t 的大作中提到】
: 不知道你的感觉从何而来。
: 2年前面世时就被问过这题并且答案通过。leetcode什么的其它不多说了，没刷过的人
: 现在不多了。
: "总体思路还没有概念"，嘿嘿，嘿嘿。我一笑而过。
avatar
h*e
166 楼
哦那就是你刷题和我们大多数人的思路很不同哦，不妨你也介绍一下你的做法，大家开
阔思路哦。
我们是算每点和其他点的斜率，用斜率为key做hashmap,　看和本点相连的其他点落在
每个斜率内的有几个。　然后枚举这个轴心点　这样算法复杂度O(N*N)
我们现在都是用斜率作key　整个帖子纠结的是斜率怎么存和相应的精确度的问题，看
你说似乎不是用斜率做key,
所以开始还以为你没做过呢。

【在 h****t 的大作中提到】
: 不知道你的感觉从何而来。
: 2年前面世时就被问过这题并且答案通过。leetcode什么的其它不多说了，没刷过的人
: 现在不多了。
: "总体思路还没有概念"，嘿嘿，嘿嘿。我一笑而过。
avatar
i*s
167 楼
忍不住替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,
: 所以开始还以为你没做过呢。
avatar
h*e
168 楼
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是如何处理重复的点，一般没做过的
: 第一次做不一定想得到好办法。总体看之前的讨论无语了，跳出来说几句。
avatar
i*s
169 楼
之前回的有误，请看我更正后的解答，你这样行是因为每次内循环前都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);
: }
: };
: }
avatar
h*e
170 楼
我的是check　了　Ａ＝０　　Ｂ＝０的情况其实并不是严格意义上的斜率，垂直水平
是　０，　１　和　１，　０　一轴心点加上一方向自然能确定一条直线。

【在 i******s 的大作中提到】
: 之前回的有误，请看我更正后的解答，你这样行是因为每次内循环前都clear了map。如
: 果换一个实现，则一定要存截距。anyway，slope的精度问题如果面试官死扣，那就只
: 能换Ax+By+C的表示方式，如果让过就过了。我碰到过both。
:
: );
avatar
i*s
171 楼
你的解法没问题，只是要记得为什么可以不保存截距，只用"斜率"就可以。有的面试官
会confuse，因为可能他们没有想过如果每次内循环前清了map(或者创建一个新的)，则
截距不是必须的。因为一个点在外循环是已确定。如果碰上绕不过的新手面试官，建议
保存截距以迎合他们的口味。。。

【在 h*******e 的大作中提到】
: 我的是check　了　Ａ＝０　　Ｂ＝０的情况其实并不是严格意义上的斜率，垂直水平
: 是　０，　１　和　１，　０　一轴心点加上一方向自然能确定一条直线。
avatar
p*e
172 楼
A,B,C的解法更局限一点吧，因为只适用于整数情况
如果点是浮点的话，还是要考虑精度问题

【在 i******s 的大作中提到】
: 之前回的有误，请看我更正后的解答，你这样行是因为每次内循环前都clear了map。如
: 果换一个实现，则一定要存截距。anyway，slope的精度问题如果面试官死扣，那就只
: 能换Ax+By+C的表示方式，如果让过就过了。我碰到过both。
:
: );
avatar
i*s
173 楼
well, 一般遇到的都是point是int x, int y。如果面试官扣这个，那就只有跟他聊聊
怎么解决精度问题了。但对于都是int的情况，ABC法比较好。

【在 p****e 的大作中提到】
: A,B,C的解法更局限一点吧，因为只适用于整数情况
: 如果点是浮点的话，还是要考虑精度问题
avatar
h*e
174 楼
浮点要考虑精度问题的而且这时候要重写 unordered_map的equal函数了，　我现在还
没想清楚为什么这个 哈希函数一定要外面加个namespace std才能通过。
这种template我之前也没见过　搜了一下发现叫做全特化模板。

【在 p****e 的大作中提到】
: A,B,C的解法更局限一点吧，因为只适用于整数情况
: 如果点是浮点的话，还是要考虑精度问题
avatar
h*e
175 楼
轴心点　pointI 给定了　知道了　Ａ　Ｂ就能知道　　C了所以两个值就够了

【在 i******s 的大作中提到】
: 之前回的有误，请看我更正后的解答，你这样行是因为每次内循环前都clear了map。如
: 果换一个实现，则一定要存截距。anyway，slope的精度问题如果面试官死扣，那就只
: 能换Ax+By+C的表示方式，如果让过就过了。我碰到过both。
:
: );
avatar
f*t
176 楼
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;
}
};
avatar
w*a
177 楼
这个用分数存key最好，但是要写个GCD做约分
avatar
w*a
178 楼
感觉这题的考点就是用分数作为KEY
相关阅读
有人想收养我们家的猫咪吗？Re: 暴笑视频！！倒鸭子！！！有人看过吗？！ (转载)让人无语的强悍 (转载)分享猫有关raw food diet的资料豆芽哼唧了一早上普通青年vs文艺青年vs2B青年 （2B青年照片已更新）Bailey和Ulf的一些其他照片~贴个petflow的胖子狗呆新照小萌猫伸手要粑粑挠头有人记得给兔子建“豪华屋子”的帖子么？一边一个[合集] 求助，退烧药抵押哥来了！！发包子20枚~感谢大家填survey小灰终于出来啃饼干了贴美喵一只~~超可爱的都谁C了？普通青年vs文艺青年vs2B青年- 乌咪版Ulf和Bailey的建议变装照~
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。