谷歌google跪经

zyoppy008 发表于 2016-12-11 18:00
为啥需要水池抽样呀，感觉没必要，糖果总数是确定的n个，然后假如有vert或者hor 就n - 1或者n-2
然后ran ...

你说的思路没错，可以不用reservoir sampling (因为糖果sample的顺序是无所谓的). 总之目的就是为了实现O(1)space. (而且你的还是O(1)时间)
在你的code应该再加上对sz的check，因为有vert == hor并且均非零的情况:

1. sz =  (vert != 0) + (hor != 0);
   
2. if (sz == 2 && vert == hor) sz = 1;
   
3. n -= sz;
   
4. res = rand() % n + 1;
   
5. if (res == hor) res = (n + 1);
   
6. else if (res == vert) res = (n + 1 + (sz == 2))

复制代码

zzgzzm 发表于 2016-12-12 12:25
你说的思路没错，可以不用reservoir sampling (因为糖果sample的顺序是无所谓的). 总之目的就是为了实现O ...

对 vert hor都存在，且相等的情况 我没有考虑。。。

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

请问一下这个先放 可以消除的模块 和 生成board后在替换一块区域 两种方法比较有区别吗？我感觉是后者好一点，因为 放可消除模块应该是要随机生成一个放入点的坐标。如果先将模块放在board中间的位置，可能在后续生成board的时候比较麻烦，所以是不是先生成board，然后在放入模块会来的方便一点？

zyoppy008 发表于 2016-12-11 18:00
为啥需要水池抽样呀，感觉没必要，糖果总数是确定的n个，然后假如有vert或者hor 就n - 1或者n-2
然后ran ...

感觉你这个有些道理，但是这样各个数字被选中的概率好像不相同，

spwahaha 发表于 2016-12-14 05:38
感觉你这个有些道理，但是这样各个数字被选中的概率好像不相同，

明显一样的

spwahaha 发表于 2016-12-14 05:38
感觉你这个有些道理，但是这样各个数字被选中的概率好像不相同，

明显一样的

zyoppy008 发表于 2016-12-14 06:02
明显一样的

嗯嗯，不好意思啊，好久不刷题脑子都僵住了

zzgzzm 发表于 2016-11-22 04:11
第二题candy crash: 这个好像就是随机的一行一行从左向右生在board上成均匀随机数{1, 2, 3, 4}。在位置(i,j ...

我觉得有一种小小的优化, 就是先是第一轮放糖果时, 放一格, 跳一格, 像下面这种
1 0 2 0
0 3 0 4
1 0 2 0
0 3 0 4
这样第一轮放的糖果可以完全随机, 然后第二轮把空补上时, 再考虑约束条件.

请问楼主在哪栋楼面的？

zzgzzm 发表于 2016-11-21 14:28
第一题：这个题应该可以DP: 假设delta[]是相邻加油站的间距，并且是sorted（这个题与顺序无关，所以若不是s ...

jin chang kan dao ceng zhu zai LC zhong de tie zi, mo bai yi xia.