学CS的人都是神人吗？这种题目没见过怎么能想出解法# JobHunting - 待字闺中
d*n
1 楼
leetcode， maximum gap problem。
看了鸽笼原理的解法，真是叹服。
不过仔细想想，还是有点radix sort，bucket sort的影子。
看了鸽笼原理的解法，真是叹服。
不过仔细想想，还是有点radix sort，bucket sort的影子。
d*n
2 楼
这个DP怎么解？递推公式是什么？
愿闻其详。
愿闻其详。
m*k
3 楼
leecode 解法区间长是整数，不知如何证明笼子为n-2
比如输入
［1，2，3，5］
笼子数为2
区间长是double好理解，但coding时有精度concern
比如输入
［1，2，3，5］
笼子数为2
区间长是double好理解，但coding时有精度concern
m*k
4 楼
望贴code指教，bow!
l*n
5 楼
Talk is cheap, show us the code.
There may not be a linear time DP solution
There may not be a linear time DP solution
g*1
6 楼
e*2
7 楼
我就没看答案想出来了，只是想得有点久而已。
【在 d****n 的大作中提到】
: leetcode， maximum gap problem。
: 看了鸽笼原理的解法，真是叹服。
: 不过仔细想想，还是有点radix sort，bucket sort的影子。
【在 d****n 的大作中提到】
: leetcode， maximum gap problem。
: 看了鸽笼原理的解法，真是叹服。
: 不过仔细想想，还是有点radix sort，bucket sort的影子。
d*n
8 楼
那大神在哪高就？ FLAG哪家？
【在 e********2 的大作中提到】
: 我就没看答案想出来了，只是想得有点久而已。
【在 e********2 的大作中提到】
: 我就没看答案想出来了，只是想得有点久而已。
S*0
9 楼
我们都是站在巨人的肩上，真正牛逼的是原创者
【在 d****n 的大作中提到】
: leetcode， maximum gap problem。
: 看了鸽笼原理的解法，真是叹服。
: 不过仔细想想，还是有点radix sort，bucket sort的影子。
【在 d****n 的大作中提到】
: leetcode， maximum gap problem。
: 看了鸽笼原理的解法，真是叹服。
: 不过仔细想想，还是有点radix sort，bucket sort的影子。
g*s
10 楼
商业淘汰和经济流动。
如果不是工资高。不会有很多聪明的人，来做这一行的。
真正nb的人，有几个会去考虑代码。
【在 S********0 的大作中提到】
: 我们都是站在巨人的肩上，真正牛逼的是原创者
如果不是工资高。不会有很多聪明的人，来做这一行的。
真正nb的人，有几个会去考虑代码。
【在 S********0 的大作中提到】
: 我们都是站在巨人的肩上，真正牛逼的是原创者
d*n
11 楼
你的point是什么啊，不懂。
【在 g**s 的大作中提到】
: 商业淘汰和经济流动。
: 如果不是工资高。不会有很多聪明的人，来做这一行的。
: 真正nb的人，有几个会去考虑代码。
【在 g**s 的大作中提到】
: 商业淘汰和经济流动。
: 如果不是工资高。不会有很多聪明的人，来做这一行的。
: 真正nb的人，有几个会去考虑代码。
n*e
12 楼
都是练习过了的在装逼
g*s
13 楼
见13楼。
计算机本身没什么特别高深的地方。
学物理，数学的才是聪明的。
学计算机的多工资高，是因为商业，因为利润。
【在 d****n 的大作中提到】
: 你的point是什么啊，不懂。
计算机本身没什么特别高深的地方。
学物理，数学的才是聪明的。
学计算机的多工资高，是因为商业，因为利润。
【在 d****n 的大作中提到】
: 你的point是什么啊，不懂。
h*i
14 楼
楼主问这个问题有点搞笑
你说数学的微积分在考试的时候 难道还是你发明的那些方法吗
同样准备高考那是做了多少道数学题，高中数学那些定理让你自己去证明你也证明不出
来几个吧
老实刷个两三遍 就不会问这种问题了，问这样的问题就是你还没刷好
你说数学的微积分在考试的时候 难道还是你发明的那些方法吗
同样准备高考那是做了多少道数学题，高中数学那些定理让你自己去证明你也证明不出
来几个吧
老实刷个两三遍 就不会问这种问题了，问这样的问题就是你还没刷好
d*n
15 楼
非也。
你还是没有明白我问的问题。
考微积分当然定理不是我发明的，但是用定理去证明些东西是要些聪明才智的。
这个max gap，用到鸽笼原理，这个就是已知定理。怎么活用，然后创造max cap的解决
办法，是要些聪明才智的。
我感叹的是，能想到用鸽笼原理去解决这个问题，就是牛逼之处。不是创造鸽笼原理而
牛逼，完全两马事。
高考牛人不是说他们证明了多少书本上的定理，是他们用定理去证明高考题目，这些题
目有些要技巧。
这个技巧可以通过很多联系来学，你也不能排除有些牛逼的人，天生就能想到这些技巧。
【在 h*******i 的大作中提到】
: 楼主问这个问题有点搞笑
: 你说数学的微积分在考试的时候 难道还是你发明的那些方法吗
: 同样准备高考那是做了多少道数学题，高中数学那些定理让你自己去证明你也证明不出
: 来几个吧
: 老实刷个两三遍 就不会问这种问题了，问这样的问题就是你还没刷好
你还是没有明白我问的问题。
考微积分当然定理不是我发明的，但是用定理去证明些东西是要些聪明才智的。
这个max gap，用到鸽笼原理，这个就是已知定理。怎么活用，然后创造max cap的解决
办法，是要些聪明才智的。
我感叹的是，能想到用鸽笼原理去解决这个问题，就是牛逼之处。不是创造鸽笼原理而
牛逼，完全两马事。
高考牛人不是说他们证明了多少书本上的定理，是他们用定理去证明高考题目，这些题
目有些要技巧。
这个技巧可以通过很多联系来学，你也不能排除有些牛逼的人，天生就能想到这些技巧。
【在 h*******i 的大作中提到】
: 楼主问这个问题有点搞笑
: 你说数学的微积分在考试的时候 难道还是你发明的那些方法吗
: 同样准备高考那是做了多少道数学题，高中数学那些定理让你自己去证明你也证明不出
: 来几个吧
: 老实刷个两三遍 就不会问这种问题了，问这样的问题就是你还没刷好
r*t
16 楼
说用鸽巢原理的是故弄玄虚，把一个简单的思想硬凑成什么原理， phd 干的事吧，真
是有意思
leetcode 确实有一些题需要多刷才能做出来 面试也不期待一下子就能做出来这种水平
巧。
【在 d****n 的大作中提到】
: 非也。
: 你还是没有明白我问的问题。
: 考微积分当然定理不是我发明的，但是用定理去证明些东西是要些聪明才智的。
: 这个max gap，用到鸽笼原理，这个就是已知定理。怎么活用，然后创造max cap的解决
: 办法，是要些聪明才智的。
: 我感叹的是，能想到用鸽笼原理去解决这个问题，就是牛逼之处。不是创造鸽笼原理而
: 牛逼，完全两马事。
: 高考牛人不是说他们证明了多少书本上的定理，是他们用定理去证明高考题目，这些题
: 目有些要技巧。
: 这个技巧可以通过很多联系来学，你也不能排除有些牛逼的人，天生就能想到这些技巧。
是有意思
leetcode 确实有一些题需要多刷才能做出来 面试也不期待一下子就能做出来这种水平
巧。
【在 d****n 的大作中提到】
: 非也。
: 你还是没有明白我问的问题。
: 考微积分当然定理不是我发明的，但是用定理去证明些东西是要些聪明才智的。
: 这个max gap，用到鸽笼原理，这个就是已知定理。怎么活用，然后创造max cap的解决
: 办法，是要些聪明才智的。
: 我感叹的是，能想到用鸽笼原理去解决这个问题，就是牛逼之处。不是创造鸽笼原理而
: 牛逼，完全两马事。
: 高考牛人不是说他们证明了多少书本上的定理，是他们用定理去证明高考题目，这些题
: 目有些要技巧。
: 这个技巧可以通过很多联系来学，你也不能排除有些牛逼的人，天生就能想到这些技巧。
d*n
17 楼
多刷是能做出来。见过解法再做，就不叫做出来了，也不能体现水平，顶多是熟练，而
且也没有自己想出来的快感。
PS。我也同意叫鸽笼原理是故弄玄虚，叫什么无所谓，关键是解决问题的思想。你要是
能不看解法想到
我也挺佩服。
【在 r******t 的大作中提到】
: 说用鸽巢原理的是故弄玄虚，把一个简单的思想硬凑成什么原理， phd 干的事吧，真
: 是有意思
: leetcode 确实有一些题需要多刷才能做出来 面试也不期待一下子就能做出来这种水平
:
: 巧。
且也没有自己想出来的快感。
PS。我也同意叫鸽笼原理是故弄玄虚，叫什么无所谓，关键是解决问题的思想。你要是
能不看解法想到
我也挺佩服。
【在 r******t 的大作中提到】
: 说用鸽巢原理的是故弄玄虚，把一个简单的思想硬凑成什么原理， phd 干的事吧，真
: 是有意思
: leetcode 确实有一些题需要多刷才能做出来 面试也不期待一下子就能做出来这种水平
:
: 巧。
P*i
18 楼
bucket求min max, 然后scan一遍
弱问那个步骤用到了鸽笼原理
【在 r******t 的大作中提到】
: 说用鸽巢原理的是故弄玄虚，把一个简单的思想硬凑成什么原理， phd 干的事吧，真
: 是有意思
: leetcode 确实有一些题需要多刷才能做出来 面试也不期待一下子就能做出来这种水平
:
: 巧。
弱问那个步骤用到了鸽笼原理
【在 r******t 的大作中提到】
: 说用鸽巢原理的是故弄玄虚，把一个简单的思想硬凑成什么原理， phd 干的事吧，真
: 是有意思
: leetcode 确实有一些题需要多刷才能做出来 面试也不期待一下子就能做出来这种水平
:
: 巧。
m*1
19 楼
推荐楼主去做做hackerrank,topcoder(难题部分),同意很难的题想出来的时候是很有快
感的。
然后再回来看看leetcode，就会觉得leetcode混个熟练就好。。leetcode外的难题太多
了
感的。
然后再回来看看leetcode，就会觉得leetcode混个熟练就好。。leetcode外的难题太多
了
d*n
20 楼
你给你的code一个严谨的证明看看，纸上写写。看看哪步要用到。不严谨证明，随便看
看是不行的。
【在 P****i 的大作中提到】
: bucket求min max, 然后scan一遍
: 弱问那个步骤用到了鸽笼原理
看是不行的。
【在 P****i 的大作中提到】
: bucket求min max, 然后scan一遍
: 弱问那个步骤用到了鸽笼原理
r*t
21 楼
不是叫什么名字的问题，看你之前的回复，还觉得用这个东西很神奇，说明没看透本质
，这么刷题，下次遇到类似的还不会
【在 d****n 的大作中提到】
: 多刷是能做出来。见过解法再做，就不叫做出来了，也不能体现水平，顶多是熟练，而
: 且也没有自己想出来的快感。
: PS。我也同意叫鸽笼原理是故弄玄虚，叫什么无所谓，关键是解决问题的思想。你要是
: 能不看解法想到
: 我也挺佩服。
，这么刷题，下次遇到类似的还不会
【在 d****n 的大作中提到】
: 多刷是能做出来。见过解法再做，就不叫做出来了，也不能体现水平，顶多是熟练，而
: 且也没有自己想出来的快感。
: PS。我也同意叫鸽笼原理是故弄玄虚，叫什么无所谓，关键是解决问题的思想。你要是
: 能不看解法想到
: 我也挺佩服。
P*L
22 楼
这题无非就是先用一个 O(n) time 的排序算法，然后找最大的 gap。
排序算法可以用 bucket sort/radix sort/spaghetti sort。
鸽笼原理没有在这里用到。
【在 d****n 的大作中提到】
: leetcode， maximum gap problem。
: 看了鸽笼原理的解法，真是叹服。
: 不过仔细想想，还是有点radix sort，bucket sort的影子。
排序算法可以用 bucket sort/radix sort/spaghetti sort。
鸽笼原理没有在这里用到。
【在 d****n 的大作中提到】
: leetcode， maximum gap problem。
: 看了鸽笼原理的解法，真是叹服。
: 不过仔细想想，还是有点radix sort，bucket sort的影子。
r*t
23 楼
我看了你说的那个鸽巢原理解法的原稿，把 min 和 max 都取出来，凑成 n - 2 个数
，再往鸽巢原理上靠，
好不容易建出模型，还漏了 min 和 max 两个边界，然后把这两个数再加上去，这不是
搞笑吗
【在 d****n 的大作中提到】
: 你给你的code一个严谨的证明看看，纸上写写。看看哪步要用到。不严谨证明，随便看
: 看是不行的。
，再往鸽巢原理上靠，
好不容易建出模型，还漏了 min 和 max 两个边界，然后把这两个数再加上去，这不是
搞笑吗
【在 d****n 的大作中提到】
: 你给你的code一个严谨的证明看看，纸上写写。看看哪步要用到。不严谨证明，随便看
: 看是不行的。
d*n
24 楼
….那我把每个数转化为二进制，然后用32Xn 的radix sort为什么过不了oj，理论上也
是O（n）time，O（n）space。
也不是bucket sort就一定行。对bucket size也有要求。
我也不是想不到bucket sort。
【在 P*******L 的大作中提到】
: 这题无非就是先用一个 O(n) time 的排序算法，然后找最大的 gap。
: 排序算法可以用 bucket sort/radix sort/spaghetti sort。
: 鸽笼原理没有在这里用到。
是O（n）time，O（n）space。
也不是bucket sort就一定行。对bucket size也有要求。
我也不是想不到bucket sort。
【在 P*******L 的大作中提到】
: 这题无非就是先用一个 O(n) time 的排序算法，然后找最大的 gap。
: 排序算法可以用 bucket sort/radix sort/spaghetti sort。
: 鸽笼原理没有在这里用到。
d*n
25 楼
…..
没看出哪里搞笑。
你怎么证明max gap不会在bucket里面？当然要用到，至少有一个bucket是空的，所以
max gap至少大于bucket的size，然后就证明max gap不会在bucket里面。
你知道本质，说来听听啊，什么本质？我愚钝不懂。
干脆也别说什么本质了，给个证明不用鸽笼原理看看。
【在 r******t 的大作中提到】
: 我看了你说的那个鸽巢原理解法的原稿，把 min 和 max 都取出来，凑成 n - 2 个数
: ，再往鸽巢原理上靠，
: 好不容易建出模型，还漏了 min 和 max 两个边界，然后把这两个数再加上去，这不是
: 搞笑吗
没看出哪里搞笑。
你怎么证明max gap不会在bucket里面？当然要用到，至少有一个bucket是空的，所以
max gap至少大于bucket的size，然后就证明max gap不会在bucket里面。
你知道本质，说来听听啊，什么本质？我愚钝不懂。
干脆也别说什么本质了，给个证明不用鸽笼原理看看。
【在 r******t 的大作中提到】
: 我看了你说的那个鸽巢原理解法的原稿，把 min 和 max 都取出来，凑成 n - 2 个数
: ，再往鸽巢原理上靠，
: 好不容易建出模型，还漏了 min 和 max 两个边界，然后把这两个数再加上去，这不是
: 搞笑吗
P*L
26 楼
基于鸽笼原理的 code 是这个吧？
http://yiminghe.iteye.com/blog/250120
leetcode 原题是整数，所以各种基于 sort 的方法很好使。如果是实数，还是应该用
鸽笼原理。
【在 d****n 的大作中提到】
: leetcode， maximum gap problem。
: 看了鸽笼原理的解法，真是叹服。
: 不过仔细想想，还是有点radix sort，bucket sort的影子。
http://yiminghe.iteye.com/blog/250120
leetcode 原题是整数，所以各种基于 sort 的方法很好使。如果是实数，还是应该用
鸽笼原理。
【在 d****n 的大作中提到】
: leetcode， maximum gap problem。
: 看了鸽笼原理的解法，真是叹服。
: 不过仔细想想，还是有点radix sort，bucket sort的影子。
d*n
27 楼
一开始试过radix sort，过不了oj。然后想了很长时间，google了下，看到鸽笼原理的
解法。
就是感叹下思想巧妙。学CS的人牛逼，不知道为什么反响会这么大，有些人回复也没有
什么
好语气。
不用鸽笼原理，有其他巧妙解法说出来就是，不想说去投conference也行，没有必要感
觉别人都是
傻逼。
不过我也是少见多怪了。我专业不是CS，数学物理里面的技巧见多了也就不觉得感叹了，
看到这个觉得新鲜感叹了一下。可能CS科班出身的不觉得有什么。都习以为常了。
【在 P*******L 的大作中提到】
: 基于鸽笼原理的 code 是这个吧？
: http://yiminghe.iteye.com/blog/250120
: leetcode 原题是整数，所以各种基于 sort 的方法很好使。如果是实数，还是应该用
: 鸽笼原理。
解法。
就是感叹下思想巧妙。学CS的人牛逼，不知道为什么反响会这么大，有些人回复也没有
什么
好语气。
不用鸽笼原理，有其他巧妙解法说出来就是，不想说去投conference也行，没有必要感
觉别人都是
傻逼。
不过我也是少见多怪了。我专业不是CS，数学物理里面的技巧见多了也就不觉得感叹了，
看到这个觉得新鲜感叹了一下。可能CS科班出身的不觉得有什么。都习以为常了。
【在 P*******L 的大作中提到】
: 基于鸽笼原理的 code 是这个吧？
: http://yiminghe.iteye.com/blog/250120
: leetcode 原题是整数，所以各种基于 sort 的方法很好使。如果是实数，还是应该用
: 鸽笼原理。
r*t
28 楼
根本就没有哪个 bucket 非得是空的，他把 min 和 max 两个数拿出来，凑成 n - 2
个数玩鸽巢原理
玩完了发现没考虑 max 和 min 再加回去，还能至少有一个 bucket 是空的吗，搞了个
不严谨的原理，不搞笑吗？
一共 n 个数 n - 1 个 gap，平均 gap 都有 (max - min) / (n - 1)
我就说最大值不小于平均数就完了，就是这么一个简单的道理
不是说这个题简单打击楼主，这题不弱，我也想了很久，但是我一直在说的是有些人的
解法就是故弄玄虚，把简单的东西搞复杂
【在 d****n 的大作中提到】
: …..
: 没看出哪里搞笑。
: 你怎么证明max gap不会在bucket里面？当然要用到，至少有一个bucket是空的，所以
: max gap至少大于bucket的size，然后就证明max gap不会在bucket里面。
: 你知道本质，说来听听啊，什么本质？我愚钝不懂。
: 干脆也别说什么本质了，给个证明不用鸽笼原理看看。
个数玩鸽巢原理
玩完了发现没考虑 max 和 min 再加回去，还能至少有一个 bucket 是空的吗，搞了个
不严谨的原理，不搞笑吗？
一共 n 个数 n - 1 个 gap，平均 gap 都有 (max - min) / (n - 1)
我就说最大值不小于平均数就完了，就是这么一个简单的道理
不是说这个题简单打击楼主，这题不弱，我也想了很久，但是我一直在说的是有些人的
解法就是故弄玄虚，把简单的东西搞复杂
【在 d****n 的大作中提到】
: …..
: 没看出哪里搞笑。
: 你怎么证明max gap不会在bucket里面？当然要用到，至少有一个bucket是空的，所以
: max gap至少大于bucket的size，然后就证明max gap不会在bucket里面。
: 你知道本质，说来听听啊，什么本质？我愚钝不懂。
: 干脆也别说什么本质了，给个证明不用鸽笼原理看看。
d*n
29 楼
你是牛人，证毕。
【在 r******t 的大作中提到】
: 根本就没有哪个 bucket 非得是空的，他把 min 和 max 两个数拿出来，凑成 n - 2
: 个数玩鸽巢原理
: 玩完了发现没考虑 max 和 min 再加回去，还能至少有一个 bucket 是空的吗，搞了个
: 不严谨的原理，不搞笑吗？
: 一共 n 个数 n - 1 个 gap，平均 gap 都有 (max - min) / (n - 1)
: 我就说最大值不小于平均数就完了，就是这么一个简单的道理
: 不是说这个题简单打击楼主，这题不弱，我也想了很久，但是我一直在说的是有些人的
: 解法就是故弄玄虚，把简单的东西搞复杂
【在 r******t 的大作中提到】
: 根本就没有哪个 bucket 非得是空的，他把 min 和 max 两个数拿出来，凑成 n - 2
: 个数玩鸽巢原理
: 玩完了发现没考虑 max 和 min 再加回去，还能至少有一个 bucket 是空的吗，搞了个
: 不严谨的原理，不搞笑吗？
: 一共 n 个数 n - 1 个 gap，平均 gap 都有 (max - min) / (n - 1)
: 我就说最大值不小于平均数就完了，就是这么一个简单的道理
: 不是说这个题简单打击楼主，这题不弱，我也想了很久，但是我一直在说的是有些人的
: 解法就是故弄玄虚，把简单的东西搞复杂
S*0
30 楼
同意这个观点。
虽然我自己不会走理科的路线，但是真的不得不说，科学上，对这个世界贡献最大的，
真正的牛人，还都是理科的，外加一般都过得很清贫，更加让人敬佩。
话又说回来，牛人，一般也都是在艰苦环境下产生的，工资太高，生活太嗨皮，会比较
难。 就像好的红酒的葡萄都是在恶劣的地理环境下生产的。
【在 g**s 的大作中提到】
: 见13楼。
: 计算机本身没什么特别高深的地方。
: 学物理，数学的才是聪明的。
: 学计算机的多工资高，是因为商业，因为利润。
g*s
31 楼
Re
【在 m****1 的大作中提到】
: 推荐楼主去做做hackerrank,topcoder(难题部分),同意很难的题想出来的时候是很有快
: 感的。
: 然后再回来看看leetcode，就会觉得leetcode混个熟练就好。。leetcode外的难题太多
: 了
【在 m****1 的大作中提到】
: 推荐楼主去做做hackerrank,topcoder(难题部分),同意很难的题想出来的时候是很有快
: 感的。
: 然后再回来看看leetcode，就会觉得leetcode混个熟练就好。。leetcode外的难题太多
: 了
P*i
32 楼
max gap在bucket里面没关系啊，bucket_max - bucket_min也跟着比较就行了
【在 d****n 的大作中提到】
: …..
: 没看出哪里搞笑。
: 你怎么证明max gap不会在bucket里面？当然要用到，至少有一个bucket是空的，所以
: max gap至少大于bucket的size，然后就证明max gap不会在bucket里面。
: 你知道本质，说来听听啊，什么本质？我愚钝不懂。
: 干脆也别说什么本质了，给个证明不用鸽笼原理看看。
【在 d****n 的大作中提到】
: …..
: 没看出哪里搞笑。
: 你怎么证明max gap不会在bucket里面？当然要用到，至少有一个bucket是空的，所以
: max gap至少大于bucket的size，然后就证明max gap不会在bucket里面。
: 你知道本质，说来听听啊，什么本质？我愚钝不懂。
: 干脆也别说什么本质了，给个证明不用鸽笼原理看看。
t*a
33 楼
radix sorting 就可以了。2^32也就是10位数，worst case 10n也是线性时间吧
【在 d****n 的大作中提到】
: leetcode， maximum gap problem。
: 看了鸽笼原理的解法，真是叹服。
: 不过仔细想想，还是有点radix sort，bucket sort的影子。
【在 d****n 的大作中提到】
: leetcode， maximum gap problem。
: 看了鸽笼原理的解法，真是叹服。
: 不过仔细想想，还是有点radix sort，bucket sort的影子。
相关阅读
本科学校改名了或者被合并了，写当时的名字还是现在的？US IT Worker Files Hiring Lawsuit Against Infosys, Class Action ProposedG家面经 已跪提供Google内推博士毕业后没有申请opt，换专业硕士毕业可以申请硕士专业相关的opt吗？RFE超过两个月H1b是不是就没戏了？版上大牛们说说ads还有前途吗关于opt的小问题求Effective C++英文版第三版的pdf下载,小包子一个酬谢纯文科转CS非典型性经验贴（顺求refer)Palindrome那题，OJ上通不过太吓人啦!微软总部发生强奸案到现在还不明白么？美国是以族裔为单位竞争利益 (转载)google onsite归来，求bless问一道题(6)请教Bloomberg FAE申请intern 结束给的return offer 如果接了以后，可以拒吗？ 担心有不好后果看到搞IT的天天被印度同事虐，庆幸自己选了生物 (转载)为什么没有发拒信的courtesyH1B的一个问题。