FB新题求解答

马上onsite了，看到新题好抓狂。。。。
引用帖子：
第二道题：
面试官说是道新题  finding ali baba
就是ali baba是个怪兽，他可能在

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

化～～～

我感觉这题是DP，但不知道转移方程怎么写，不知走过路过的大神能给点idea咩？谢谢！

这道其实是老题了，之前就有出现过。很快这道题就会放到leetcode上的，你到时可以去试试。对于这道题，既然是判断时候稳赢，意思就是对于无论ali的起始位置在哪儿，我们都能抓到它。所以很自然，ali所在的位置肯定会作为状态的一部分。另外一个显然的需要记录的状态，就是strategy的当前位置。所以我们可以很容易写下如下的代码：

1. def canFind(numCaves, strategy):
   
2.         def helper(pos, curr):
   
3.                 if curr == len(strategy):
   
4.                         return False
   
5.                 if pos == strategy[curr]:
   
6.                         return True
   
7.                 res = True
   
8.                 if pos > 0:
   
9.                         res = res and helper(pos - 1, curr + 1)
   
10.                 if pos < numCaves - 1:
    
11.                         res = res and helper(pos + 1, curr + 1)
    
12.                 return res
    
13.         for i in xrange(numCaves):
    
14.                 if helper(i, 0) is False:
    
15.                         return False
    
16.         return True

复制代码

由于我们要稳赢，所以对于原问题helper(pos, curr)，它的解依赖于helper(pos - 1, curr + 1)（对应往左跳一格，如果可以的话）与上helper(pos + 1, curr + 1)（同理，往右一格）。然后我们对于ali所在的每个位置都算一遍就好了。

按照这样的设计方式，我们很快就能看出有许多的重复计算，所以可以加上cache，这样时间复杂度就是O(numCaves * len(strategy))。如果你改成bottom up的计算方式，就是直接填表，那么注意状态间的依赖方式，我们可以使用滚动数组，这样空间就可以从O(numCaves * len(strategy))优化到O(numCaves)。

我觉得可以用res[i][j] 来表示 第j 天在Cave i能不能捉到马云。如果捉到，则为true, 否则为false。
然后状态转换方程就是res[i][j] = res[i][j] || res[i - 1][j - 1] && res[i + 1][j - 1] 。 然后最后再check res[i][days - 1]是不是全是true， 是的话就代表work

1. public boolean alibaba(int numCaves, int[] strategy){
   
2.         int days = strategy.length;
   
3.         boolean[][] res = new boolean[numCaves][days];
   
4.         for(int i = 0; i < days; i++){
   
5.                 res[strategt[i]][i] = true;
   
6.         }
   
7. 
   
8. 
   
9.         for(int i = 0; i < numCaves;i++){
   
10.                 for(int j = 1; j < days; j++){
    
11.                         if(i == numCaves - 1){
    
12.                                 res[i][j] = res[i][j] || res[i - 1][j - 1];
    
13.                         }else if(i == 0){
    
14.                                 res[i][j] = res[i][j] || res[i + 1][j - 1];
    
15. 
    
16. 
    
17.                         }else{
    
18.                                 res[i][j] = res[i][j] || (res[i - 1][j - 1] &&  res[i + 1][j - 1]);
    
19.                         }                                               
    
20.                 }
    
21.         }
    
22. 
    
23.         boolean result = true;
    
24.         for(int i = 0; i < numCaves; i++){
    
25.                 if(!result){
    
26.                         break;
    
27.                 }else{
    
28.                         result = result && res[i][days - 1];
    
29.                 }
    
30. 
    
31.         }
    
32. 
    
33.        
    
34. 
    
35. }

复制代码

补充内容 (2015-5-29 02:29):
刚开始的是res[i][j]， 为什么提交了之后变了

补充内容 (2015-5-29 02:30):


补充内容 (2015-5-29 02:33):
忘记写return了

有可能有稳赢的吗？就算一个一个扫过去，那马云也可能藏在你旁边的山洞，然后下一天跟你调换位置，所以也会错过啊

是说ali的每天的位置必须是前一天位置加减1吗？

最简单的想法就是开一个numCaves大小的数组来保存某一天某个位置是否可到达，然后从第一天开始往后推，如果某一天所有位置都不能到达strategy就是正确的。空间复杂度O(numCaves)，每次推需要时间O(numCaves)，如果天数为d，总时间O(d * numCaves)。

但如果题意确实如此的话，不可达位置的分布会有规律，所以可能可以优化到常数空间和O(d)时间。

感觉可以BFS，分别计算第i天的可能位置，注意需要把strategy[i]从第i天可能的位置删除，如果遍历到某一天i，后发现可能的位置只有strategy[i]，则说明必胜，最欢时间复杂度是O(days * numCaves)。

我只想说

alibaba是怪兽这个梗 实在是好搞笑好可爱啊n(*≧▽≦*)n

notbad 发表于 2015-5-28 19:28
感觉可以BFS，分别计算第i天的可能位置，注意需要把strategy从第i天可能的位置删除，如果遍历到某一天i，后 ...

请问为什么要“把strategy从第i天可能的位置删除”？

补充内容 (2015-5-29 01:07):
好像get到你的回答了～

mrno5zzz 发表于 2015-5-29 02:28
我觉得可以用res[j] 来表示 第j 天在Cave i能不能捉到马云。如果捉到，则为true, 否则为false。
然后状态 ...

上面文字部分是

1. res[i][j]

复制代码

枚举每天的可能性，因为每天的可能性都是一定的，如果当遇到某一天小偷没地方去了，那么就说明这个序列ok，否则无法找到小偷。

请问使用BFS做吗。。