Redian新闻
>
学CS的人都是神人吗?这种题目没见过怎么能想出解法
avatar
学CS的人都是神人吗?这种题目没见过怎么能想出解法# JobHunting - 待字闺中
d*n
1
leetcode, maximum gap problem。
看了鸽笼原理的解法,真是叹服。
不过仔细想想,还是有点radix sort,bucket sort的影子。
avatar
d*n
2
这个DP怎么解?递推公式是什么?
愿闻其详。
avatar
m*k
3
leecode 解法区间长是整数,不知如何证明笼子为n-2
比如输入
[1,2,3,5]
笼子数为2
区间长是double好理解,但coding时有精度concern
avatar
m*k
4
望贴code指教,bow!
avatar
l*n
5
Talk is cheap, show us the code.
There may not be a linear time DP solution
avatar
g*1
6
avatar
e*2
7
我就没看答案想出来了,只是想得有点久而已。

【在 d****n 的大作中提到】
: leetcode, maximum gap problem。
: 看了鸽笼原理的解法,真是叹服。
: 不过仔细想想,还是有点radix sort,bucket sort的影子。

avatar
d*n
8
那大神在哪高就? FLAG哪家?

【在 e********2 的大作中提到】
: 我就没看答案想出来了,只是想得有点久而已。
avatar
S*0
9
我们都是站在巨人的肩上,真正牛逼的是原创者

【在 d****n 的大作中提到】
: leetcode, maximum gap problem。
: 看了鸽笼原理的解法,真是叹服。
: 不过仔细想想,还是有点radix sort,bucket sort的影子。

avatar
g*s
10
商业淘汰和经济流动。
如果不是工资高。不会有很多聪明的人,来做这一行的。
真正nb的人,有几个会去考虑代码。

【在 S********0 的大作中提到】
: 我们都是站在巨人的肩上,真正牛逼的是原创者
avatar
d*n
11
你的point是什么啊,不懂。

【在 g**s 的大作中提到】
: 商业淘汰和经济流动。
: 如果不是工资高。不会有很多聪明的人,来做这一行的。
: 真正nb的人,有几个会去考虑代码。

avatar
n*e
12
都是练习过了的在装逼
avatar
g*s
13
见13楼。
计算机本身没什么特别高深的地方。
学物理,数学的才是聪明的。
学计算机的多工资高,是因为商业,因为利润。

【在 d****n 的大作中提到】
: 你的point是什么啊,不懂。
avatar
h*i
14
楼主问这个问题有点搞笑
你说数学的微积分在考试的时候 难道还是你发明的那些方法吗
同样准备高考那是做了多少道数学题,高中数学那些定理让你自己去证明你也证明不出
来几个吧
老实刷个两三遍 就不会问这种问题了,问这样的问题就是你还没刷好
avatar
d*n
15
非也。
你还是没有明白我问的问题。
考微积分当然定理不是我发明的,但是用定理去证明些东西是要些聪明才智的。
这个max gap,用到鸽笼原理,这个就是已知定理。怎么活用,然后创造max cap的解决
办法,是要些聪明才智的。
我感叹的是,能想到用鸽笼原理去解决这个问题,就是牛逼之处。不是创造鸽笼原理而
牛逼,完全两马事。
高考牛人不是说他们证明了多少书本上的定理,是他们用定理去证明高考题目,这些题
目有些要技巧。
这个技巧可以通过很多联系来学,你也不能排除有些牛逼的人,天生就能想到这些技巧。

【在 h*******i 的大作中提到】
: 楼主问这个问题有点搞笑
: 你说数学的微积分在考试的时候 难道还是你发明的那些方法吗
: 同样准备高考那是做了多少道数学题,高中数学那些定理让你自己去证明你也证明不出
: 来几个吧
: 老实刷个两三遍 就不会问这种问题了,问这样的问题就是你还没刷好

avatar
r*t
16
说用鸽巢原理的是故弄玄虚,把一个简单的思想硬凑成什么原理, phd 干的事吧,真
是有意思
leetcode 确实有一些题需要多刷才能做出来 面试也不期待一下子就能做出来这种水平

巧。

【在 d****n 的大作中提到】
: 非也。
: 你还是没有明白我问的问题。
: 考微积分当然定理不是我发明的,但是用定理去证明些东西是要些聪明才智的。
: 这个max gap,用到鸽笼原理,这个就是已知定理。怎么活用,然后创造max cap的解决
: 办法,是要些聪明才智的。
: 我感叹的是,能想到用鸽笼原理去解决这个问题,就是牛逼之处。不是创造鸽笼原理而
: 牛逼,完全两马事。
: 高考牛人不是说他们证明了多少书本上的定理,是他们用定理去证明高考题目,这些题
: 目有些要技巧。
: 这个技巧可以通过很多联系来学,你也不能排除有些牛逼的人,天生就能想到这些技巧。

avatar
d*n
17
多刷是能做出来。见过解法再做,就不叫做出来了,也不能体现水平,顶多是熟练,而
且也没有自己想出来的快感。
PS。我也同意叫鸽笼原理是故弄玄虚,叫什么无所谓,关键是解决问题的思想。你要是
能不看解法想到
我也挺佩服。

【在 r******t 的大作中提到】
: 说用鸽巢原理的是故弄玄虚,把一个简单的思想硬凑成什么原理, phd 干的事吧,真
: 是有意思
: leetcode 确实有一些题需要多刷才能做出来 面试也不期待一下子就能做出来这种水平
:
: 巧。

avatar
P*i
18
bucket求min max, 然后scan一遍
弱问那个步骤用到了鸽笼原理

【在 r******t 的大作中提到】
: 说用鸽巢原理的是故弄玄虚,把一个简单的思想硬凑成什么原理, phd 干的事吧,真
: 是有意思
: leetcode 确实有一些题需要多刷才能做出来 面试也不期待一下子就能做出来这种水平
:
: 巧。

avatar
m*1
19
推荐楼主去做做hackerrank,topcoder(难题部分),同意很难的题想出来的时候是很有快
感的。
然后再回来看看leetcode,就会觉得leetcode混个熟练就好。。leetcode外的难题太多
avatar
d*n
20
你给你的code一个严谨的证明看看,纸上写写。看看哪步要用到。不严谨证明,随便看
看是不行的。

【在 P****i 的大作中提到】
: bucket求min max, 然后scan一遍
: 弱问那个步骤用到了鸽笼原理

avatar
r*t
21
不是叫什么名字的问题,看你之前的回复,还觉得用这个东西很神奇,说明没看透本质
,这么刷题,下次遇到类似的还不会

【在 d****n 的大作中提到】
: 多刷是能做出来。见过解法再做,就不叫做出来了,也不能体现水平,顶多是熟练,而
: 且也没有自己想出来的快感。
: PS。我也同意叫鸽笼原理是故弄玄虚,叫什么无所谓,关键是解决问题的思想。你要是
: 能不看解法想到
: 我也挺佩服。

avatar
P*L
22
这题无非就是先用一个 O(n) time 的排序算法,然后找最大的 gap。
排序算法可以用 bucket sort/radix sort/spaghetti sort。
鸽笼原理没有在这里用到。

【在 d****n 的大作中提到】
: leetcode, maximum gap problem。
: 看了鸽笼原理的解法,真是叹服。
: 不过仔细想想,还是有点radix sort,bucket sort的影子。

avatar
r*t
23
我看了你说的那个鸽巢原理解法的原稿,把 min 和 max 都取出来,凑成 n - 2 个数
,再往鸽巢原理上靠,
好不容易建出模型,还漏了 min 和 max 两个边界,然后把这两个数再加上去,这不是
搞笑吗

【在 d****n 的大作中提到】
: 你给你的code一个严谨的证明看看,纸上写写。看看哪步要用到。不严谨证明,随便看
: 看是不行的。

avatar
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。
: 鸽笼原理没有在这里用到。

avatar
d*n
25
…..
没看出哪里搞笑。
你怎么证明max gap不会在bucket里面?当然要用到,至少有一个bucket是空的,所以
max gap至少大于bucket的size,然后就证明max gap不会在bucket里面。
你知道本质,说来听听啊,什么本质?我愚钝不懂。
干脆也别说什么本质了,给个证明不用鸽笼原理看看。

【在 r******t 的大作中提到】
: 我看了你说的那个鸽巢原理解法的原稿,把 min 和 max 都取出来,凑成 n - 2 个数
: ,再往鸽巢原理上靠,
: 好不容易建出模型,还漏了 min 和 max 两个边界,然后把这两个数再加上去,这不是
: 搞笑吗

avatar
P*L
26
基于鸽笼原理的 code 是这个吧?
http://yiminghe.iteye.com/blog/250120
leetcode 原题是整数,所以各种基于 sort 的方法很好使。如果是实数,还是应该用
鸽笼原理。

【在 d****n 的大作中提到】
: leetcode, maximum gap problem。
: 看了鸽笼原理的解法,真是叹服。
: 不过仔细想想,还是有点radix sort,bucket sort的影子。

avatar
d*n
27
一开始试过radix sort,过不了oj。然后想了很长时间,google了下,看到鸽笼原理的
解法。
就是感叹下思想巧妙。学CS的人牛逼,不知道为什么反响会这么大,有些人回复也没有
什么
好语气。
不用鸽笼原理,有其他巧妙解法说出来就是,不想说去投conference也行,没有必要感
觉别人都是
傻逼。
不过我也是少见多怪了。我专业不是CS,数学物理里面的技巧见多了也就不觉得感叹了,
看到这个觉得新鲜感叹了一下。可能CS科班出身的不觉得有什么。都习以为常了。

【在 P*******L 的大作中提到】
: 基于鸽笼原理的 code 是这个吧?
: http://yiminghe.iteye.com/blog/250120
: leetcode 原题是整数,所以各种基于 sort 的方法很好使。如果是实数,还是应该用
: 鸽笼原理。

avatar
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里面。
: 你知道本质,说来听听啊,什么本质?我愚钝不懂。
: 干脆也别说什么本质了,给个证明不用鸽笼原理看看。

avatar
d*n
29
你是牛人,证毕。

【在 r******t 的大作中提到】
: 根本就没有哪个 bucket 非得是空的,他把 min 和 max 两个数拿出来,凑成 n - 2
: 个数玩鸽巢原理
: 玩完了发现没考虑 max 和 min 再加回去,还能至少有一个 bucket 是空的吗,搞了个
: 不严谨的原理,不搞笑吗?
: 一共 n 个数 n - 1 个 gap,平均 gap 都有 (max - min) / (n - 1)
: 我就说最大值不小于平均数就完了,就是这么一个简单的道理
: 不是说这个题简单打击楼主,这题不弱,我也想了很久,但是我一直在说的是有些人的
: 解法就是故弄玄虚,把简单的东西搞复杂

avatar
S*0
30

同意这个观点。
虽然我自己不会走理科的路线,但是真的不得不说,科学上,对这个世界贡献最大的,
真正的牛人,还都是理科的,外加一般都过得很清贫,更加让人敬佩。
话又说回来,牛人,一般也都是在艰苦环境下产生的,工资太高,生活太嗨皮,会比较
难。 就像好的红酒的葡萄都是在恶劣的地理环境下生产的。

【在 g**s 的大作中提到】
: 见13楼。
: 计算机本身没什么特别高深的地方。
: 学物理,数学的才是聪明的。
: 学计算机的多工资高,是因为商业,因为利润。

avatar
g*s
31
Re

【在 m****1 的大作中提到】
: 推荐楼主去做做hackerrank,topcoder(难题部分),同意很难的题想出来的时候是很有快
: 感的。
: 然后再回来看看leetcode,就会觉得leetcode混个熟练就好。。leetcode外的难题太多
: 了

avatar
P*i
32
max gap在bucket里面没关系啊,bucket_max - bucket_min也跟着比较就行了

【在 d****n 的大作中提到】
: …..
: 没看出哪里搞笑。
: 你怎么证明max gap不会在bucket里面?当然要用到,至少有一个bucket是空的,所以
: max gap至少大于bucket的size,然后就证明max gap不会在bucket里面。
: 你知道本质,说来听听啊,什么本质?我愚钝不懂。
: 干脆也别说什么本质了,给个证明不用鸽笼原理看看。

avatar
t*a
33
radix sorting 就可以了。2^32也就是10位数,worst case 10n也是线性时间吧

【在 d****n 的大作中提到】
: leetcode, maximum gap problem。
: 看了鸽笼原理的解法,真是叹服。
: 不过仔细想想,还是有点radix sort,bucket sort的影子。

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。