谷歌google跪经

ws775901 发表于 2017-1-4 04:14
jin chang kan dao ceng zhu zai LC zhong de tie zi, mo bai yi xia.

真不敢当，共同讨论而已

zzgzzm 发表于 2017-1-5 13:12
真不敢当，共同讨论而已

问下大神，对于最后一题的follow up除了楼主说的线段树还有什么思路吗？

zzgzzm 发表于 2017-1-5 13:12
真不敢当，共同讨论而已

问下大神，对于最后一题的follow up除了楼主说的线段树还有什么思路吗？

littleMiao 发表于 2017-1-6 07:49
问下大神，对于最后一题的follow up除了楼主说的线段树还有什么思路吗？

这个按以给定weight为概率返回ID的问题应该是个高频题了。我写了一个解在第14层：用给定的weight直接构造一个pdf (probability distribution function)就是一个sorted array with max value = 1.0。然后生成一个[0, 1]之间的随机数看落到哪个区间。这个时间是O(N)， 而且对于weight为double一般类型（未考虑overflow问题，但这不影响算法本质）。

我不熟悉segment tree，但从描述楼主上来说应该差不多的算法。

第一题 感觉可以用DP和二分

DP 解法思路： 假设我们有 N 个 空隙可以继续放 K个加油站,  F(N,K) 表示最终答案， 即 把 K 个加油站放到这N 个空隙中 的最小的最大间距， 那么 F(N,K) 就等于 最后一个空隙 放 0 个， 1个，2个，一直到k 个的 所有情况的最小情况， F(N,K) =min( max ( F(N-1,K) , G0), max(F(N-1,K-1), G1), max(F(N-1,K-2), G3), ............ ); 其中G2 表示 最后一个空隙中放了2个加油站之后最大的空隙， 这个可以直接算出来， 因为在一个空隙中放几个加油站， 当然是越平均越好。 O（N×K×K）

二分发思路： 对结果进行二分， 假设最小的最大空隙是X ， 然后我们把 K个加油站试图放到N 个空隙中 但是必须保证新的空隙不能大于 X， 如果我们经过努力把 K个全部放进去了， 结果还是有空隙大于X，说明X 太小了， 下次就二分大的值; 如果我们遍历完了所有的空隙， 但是还剩下加油站， 或者刚好把加油站用完， 说明X 太大了， 下次就二分大的数字。 O（log(Len) *N） Len 为一开始的输入的最大空隙

zzgzzm 发表于 2016-11-30 07:26
感谢指正！我的确忽略了这一点，没有全面测试   :-(
Line7应该改为:

不好意思 没有看懂你这个reservoir sampling....大致意思就是去除invalid的棋子，然后随机选一个。 那比如说现在总共有1，2，3，4种糖果， 其中3是invalid的， 我随机的时候挑到了3 怎么办呢？ 多谢。。

spwahaha 发表于 2016-11-24 13:05
其中一种方法是先放一个
XOX                                                          XOO
OXO 这种 ...

Hi  请问一下你的idea是， 先随机出棋盘上任意一个位置，以它开始放置一个XOX
                                                                                                            OXO
然后再随机DFS其他所有位置嘛？

小A要当码农 发表于 2017-2-2 03:27
不好意思 没有看懂你这个reservoir sampling....大致意思就是去除invalid的棋子，然后随机选一个。 那比 ...

若是invalid 的话自动increments 变为下一个。（相当于1，2，4作抽样。3被4吸收了）

zzgzzm 发表于 2017-2-2 06:32
若是invalid 的话自动increments 变为下一个。（相当于1，2，4作抽样。3被4吸收了）

这样的话没有办法保证1，2，4概率是相同的吧？  1，2是 1/4， 4是1/2

小A要当码农 发表于 2017-2-2 06:37
这样的话没有办法保证1，2，4概率是相同的吧？  1，2是 1/4， 4是1/2

抽样时还是按连续ID：1，2，3来做，只不过当抽到3时将数字3改为4而已。实际上只是ID上的manipulation