FB新题求解答

感觉DFS可以。。

觉得楼上的DP是对的。。。

milanelllo13 发表于 2015-6-29 04:27
觉得楼上的DP是对的。。。

Let's define a boolean array of the length n as pos. If pos[i] is true, it means alibaba can be in the ith house at this moment. For each day, we update the pos. If we find that there is no where alibaba can be, it turns out to be successful.

ccgogo123 发表于 2015-7-4 11:05
Let's define a boolean array of the length n as pos. If pos is true, it means alibaba can be in th ...

终于明白了！太感谢了~！！！

有没有方法可以找一个稳赢的策略？

ryancooper 发表于 2015-5-28 23:01
这道其实是老题了，之前就有出现过。很快这道题就会放到leetcode上的，你到时可以去试试。对于这道题，既然 ...

牛, 根据你的思路,写了个bottomup的dp

1. public static boolean catchAlibaba(int numCaves, int[] strategy){
   
2.         int i,j,l=strategy.length;
   
3.         boolean[][] dp = new boolean[numCaves][l];
   
4.         dp[strategy[l-1]][l-1] = true;
   
5.        
   
6.         for(j=l-2;j>=0;j--){
   
7.                 dp[0][j] = dp[1][j+1];
   
8.                 for(i=1;i<numCaves-1;i++){
   
9.                         dp[i][j] = dp[i-1][j+1] && dp[i+1][j+1];
   
10.                 }
    
11.                 dp[numCaves-1][j] = dp[numCaves-2][j+1];
    
12.                 dp[strategy[j]][j] = true;
    
13.         }
    
14.        
    
15.         for(i=0;i<numCaves;i++){
    
16.                 if(!dp[i][0]) return false;
    
17.         }
    
18.         return true;
    
19. }
    
20.        
    
21. public static void main(String[] args){
    
22.         System.out.println(catchAlibaba(3, new int[]{1,1}));
    
23.         System.out.println(catchAlibaba(4, new int[]{1,1,2,2,1}));
    
24. }

复制代码

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

层主代码横纵坐标貌似搞反了，用例子：{1, 1, 2, 2, 2, 2, 1}, 4个cave。 跑不过去

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

I think your solution is right.

我在想一个稳赢的策略是不是就是从头开始每天往右猜一步到最后一个位置，这样迟早能碰到？

bfs的方法～

1. public boolean canFindAlibaba(int numCaves, int[] strategy) {
   
2.     Queue<Integer> q = new LinkedList<>();
   
3.     for (int i = 0; i < numCaves; i++) {
   
4.       q.offer(i);
   
5.     }
   
6.     int day = 0;
   
7.     while (!q.isEmpty() && day < strategy.length) {
   
8.       int size = q.size();
   
9.       boolean[] added = new boolean[numCaves];
   
10.       for (int i = 0; i < size; i++) {
    
11.         int cur = q.poll();
    
12.         if (cur == strategy[day]) continue;
    
13.         if (cur - 1 >= 0 && !added[cur - 1]) {
    
14.           added[cur - 1] = true;
    
15.           q.offer(cur - 1);
    
16.         }
    
17.         if (cur + 1 < numCaves && !added[cur + 1]) {
    
18.           added[cur + 1] = true;
    
19.           q.offer(cur + 1);
    
20.         }
    
21.       }
    
22.       day++;
    
23.     }
    
24.     return q.isEmpty();
    
25.   }

复制代码