Google Onsite

zzgzzm 发表于 2016-11-14 07:21
第二题：用DFS是不是这个意思. 当用DFS迭代时同时要传当前的方向，然后若在同一方向的位置无障碍物时就只沿 ...

每个点有四个方向。简单的把visited过的点设成1是不够的。 比如点A从方向0进入， 在dfs中有可能要从方向1进入。

sunnyroom 发表于 2016-11-26 11:49
能解释一下概率是怎么计算的吗？
碰见概率就蒙蔽

用数学来说比较清楚：
设硬币X(i)=1的概率为p(i), X(i)=0的概率为1-p(i)。 用E(n,k)表示前n个X(i)中恰好k个X(i)=1的事件，那么求P(E(n,k))实际上就是用全概公式来DP求解。
因为显然事件X(n)=1与X(n)=0是互斥的，所以
P(E(n,k)) = P(E(n,k) and X(n)=1) + P(E(n,k) and X(n)=0)
= P(X(n)=1)*P(E(n,k) with condition X(n)=1) + P(X(n)=0)*P(E(n,k) with condition X(n)=0)
= p(n)*P(E(n-1,k-1)) + (1-p(n))*P(E(n-1,k))
其中p(n)给定已知，这样DP的转移方程就有了。关键是要注意到事件“E(n,k) with condition X(n)=1” 就是 E(n-1,k-1) 以及 “E(n,k) with condition X(n)=0”就是E(n-1,k)。
还有条件概率定义就是对任意事件A, B有：P(A with condition B) = P(A and B)/P(B).

补充内容 (2016-11-26 15:03):
全概公式：P(E) = P(A)*P(E with condition A) + (1-P(A))*P(E with condition not A), 其中E, A为任意事件。

linjin 发表于 2016-11-26 14:46
每个点有四个方向。简单的把visited过的点设成1是不够的。 比如点A从方向0进入， 在dfs中有可能要从方向1 ...

感谢指正，你说的没错。若某个cell是在十字交叉路口的话有可能需要经过2次，但方向不同(sliding path的特性)。我第一次遗漏了这一点，需要分别记录某个cell是否横向和纵向走过。我在另一个面经中看到同样的题(sliding maze)，同时要求找拐弯最少的路径。我写了个逻辑更简单BFS的，每次只将拐弯的cell入队（只visit一次），直行中的cell不必入队，我觉得只有拐点cell重要应该是sliding maze问题的关键了。
http://www.1point3acres.com/bbs/ ... 038&ptid=211354

zzgzzm 发表于 2016-11-14 05:20
第三轮：LZ已经写了recusive的，这和DP差不多了：时间O(nk)，空间O(k)

第8行似乎写错了，应该是cur[0] = prev[0] * (1 - c[nn - 1])吧

zzgzzm 发表于 2016-11-26 14:59
用数学来说比较清楚：
设硬币X(i)=1的概率为p(i), X(i)=0的概率为1-p(i)。 用E(n,k)表示前n个X(i)中恰好 ...

多谢多谢。

luofeidream 发表于 2016-11-27 02:21
第8行似乎写错了，应该是cur[0] = prev[0] * (1 - c[nn - 1])吧

感谢指正。

yhatl 发表于 2016-11-13 11:33
lz已经说了不会了 莫装逼
装逼遭雷劈

这位兄台，我没有装比啊．就题论题啊．

kevindx1120 发表于 2016-11-13 00:28
第三题，在你的recursive 解法里，你不是已经给出了递归关系式，为什么说不会bottum up 的递归．　
第四题 ...

Dijkstra面试中写不出来的。DFS全部遍历一遍得了

请问楼主在哪栋楼面的？