楼主: gougou9903
跳转到指定楼层
上一主题 下一主题
收起左侧

谷歌google跪经

 
🔗
zzgzzm 2016-12-12 12:25:42 | 只看该作者
全局:
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))
复制代码
回复

使用道具 举报

🔗
zyoppy008 2016-12-12 12:28:44 | 只看该作者
全局:
zzgzzm 发表于 2016-12-12 12:25
你说的思路没错,可以不用reservoir sampling (因为糖果sample的顺序是无所谓的). 总之目的就是为了实现O ...

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

使用道具 举报

🔗
工图新一 2016-12-12 13:45:43 | 只看该作者
全局:
spwahaha 发表于 2016-11-24 13:05
其中一种方法是先放一个
XOX                                                          XOO
OXO 这种 ...

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

使用道具 举报

🔗
spwahaha 2016-12-14 05:38:26 | 只看该作者
全局:
zyoppy008 发表于 2016-12-11 18:00
为啥需要水池抽样呀,感觉没必要,糖果总数是确定的n个,然后假如有vert或者hor 就n - 1或者n-2
然后ran ...

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

使用道具 举报

🔗
zyoppy008 2016-12-14 06:01:39 | 只看该作者
全局:
spwahaha 发表于 2016-12-14 05:38
感觉你这个有些道理,但是这样各个数字被选中的概率好像不相同,

明显一样的
回复

使用道具 举报

🔗
zyoppy008 2016-12-14 06:02:51 | 只看该作者
全局:
spwahaha 发表于 2016-12-14 05:38
感觉你这个有些道理,但是这样各个数字被选中的概率好像不相同,

明显一样的
回复

使用道具 举报

🔗
spwahaha 2016-12-14 06:28:13 | 只看该作者
全局:

嗯嗯,不好意思啊,好久不刷题脑子都僵住了
回复

使用道具 举报

🔗
lhh_NJU 2016-12-28 14:27:34 | 只看该作者
全局:
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
这样第一轮放的糖果可以完全随机, 然后第二轮把空补上时, 再考虑约束条件.
回复

使用道具 举报

🔗
Longfeng 2016-12-29 15:54:30 | 只看该作者
全局:
请问楼主在哪栋楼面的?
回复

使用道具 举报

🔗
ws775901 2017-1-4 04:14:34 | 只看该作者
全局:
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.
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表