Facebook Onsite

没懂第二轮的小偷题是怎么做的。。。

第三个

1. public class Solution {
   
2.   public List<String> wordLadder(String beginWord, String endWord, Set<String> wordList,
   
3.       Set<String> tabu) {
   
4.     if (beginWord.equals(endWord)) {
   
5.       List<String> ret = new ArrayList<>();
   
6.       ret.add(endWord);
   
7.       return ret;
   
8.     }
   
9.     tabu.add(beginWord);
   
10. 
    
11.     char[] arr = beginWord.toCharArray();
    
12.     for (int i = 0; i < arr.length; i++) {
    
13.       char orig = arr[i];
    
14.       for (char c = 'a'; c <= 'z'; c++) {
    
15.         if (c != orig) { // prune
    
16.           arr[i] = c;
    
17.           String w = String.valueOf(arr);
    
18.           if (wordList.contains(w) && !tabu.contains(w)) { // prune with tabu
    
19.             List<String> r = wordLadder(w, endWord, wordList, tabu);
    
20.             if (r != null) {
    
21.               r.add(0, beginWord);
    
22.               return r;
    
23.             }
    
24.           }
    
25.         }
    
26.       }
    
27.       arr[i] = orig; // reset
    
28.     }
    
29. 
    
30.     for (int i = 0; i <= beginWord.length(); i++) { // handle adding one letter
    
31.       for (char c = 'a'; c < 'z'; c++) {
    
32.         String w = beginWord.substring(0, i) + c + beginWord.substring(i);
    
33.         if (wordList.contains(w) && !tabu.contains(w)) {
    
34.           List<String> r = wordLadder(w, endWord, wordList, tabu);
    
35.           if (r != null) {
    
36.             r.add(0, beginWord);
    
37.             return r;
    
38.           }
    
39.         }
    
40.       }
    
41.     }
    
42.     return null;
    
43.   }
    
44. 
    
45.   public static void main(String[] args) {
    
46.     Set<String> dict = new HashSet<>();
    
47.     dict.add("hot");
    
48.     dict.add("dot");
    
49.     dict.add("dog");
    
50.     dict.add("lot");
    
51.     dict.add("log");
    
52.     dict.add("cog");
    
53.     dict.add("hit");
    
54.     dict.add("lotg");
    
55.     dict.add("aotg");
    
56.     Solution s = new Solution();
    
57.     System.out.println(s.wordLadder("hit", "cog", dict, new HashSet<String>()));
    
58.     System.out.println(s.wordLadder("hit", "aotg", dict, new HashSet<String>()));
    
59.     return;
    
60.   }
    
61. }
    

复制代码

第二个

1. public class Solution {
   
2.   public boolean canSurvive(int n, int[] seq) {
   
3.     boolean[][] survive = new boolean[seq.length][n];
   
4.     Arrays.fill(survive[0], true); // the first day
   
5.     survive[0][seq[0]] = false; // dead in the first day
   
6.     for (int i = 1; i < seq.length; i++) {
   
7.       for (int j = 0; j < n; j++) {
   
8.         boolean left = j - 1 >= 0 ? survive[i - 1][j - 1] : false;
   
9.         boolean right = j + 1 < n ? survive[i - 1][j + 1] : false;
   
10.         survive[i][j] = (left || right) && seq[i] != j;
    
11.       }
    
12.     }
    
13.     for (int i = 0; i < n; i++) {
    
14.       if (survive[seq.length - 1][i]) {
    
15.         return true;
    
16.       }
    
17.     }
    
18.     return false;
    
19.   }
    
20. 
    
21.   public boolean canSurvive2(int n, int[] seq) {
    
22.     boolean[] survive = new boolean[n];
    
23.     Arrays.fill(survive, true); // the first day
    
24.     survive[seq[0]] = false; // dead in the first day
    
25.     for (int i = 1; i < seq.length; i++) {
    
26.       boolean[] surviveNext = new boolean[n];
    
27.       for (int j = 0; j < n; j++) {
    
28.         boolean left = j - 1 >= 0 ? survive[j - 1] : false;
    
29.         boolean right = j + 1 < n ? survive[j + 1] : false;
    
30.         surviveNext[j] = (left || right) && seq[i] != j;
    
31.       }
    
32.       survive = surviveNext;
    
33.     }
    
34.     for (int i = 0; i < n; i++) {
    
35.       if (survive[i]) {
    
36.         return true;
    
37.       }
    
38.     }
    
39.     return false;
    
40.   }
    
41. 
    
42.   public static void main(String[] args) {
    
43.     Solution s = new Solution();
    
44.     System.out.println(s.canSurvive(3, new int[] {1, 1}));
    
45.     System.out.println(s.canSurvive2(3, new int[] {1, 1}));
    
46.     return;
    
47.   }
    
48. }
    

复制代码

补充内容 (2016-4-4 14:30):
楼主思路好棒

第二题， 对于第n天， 根据n-1天的小偷位置， 统计出在第n天小偷可能出现的位置。在第一天的时候， 小偷可以出现在所有的位置。

如果在其中一天， 小偷只可能出现在一个位置， 而这个人在这一天又恰好去了这个位置， 那么小偷就一定会被抓到。

面成这样都会挂？！脸书真火啊～

楼主能具体讲讲第二题吗，没看懂

ccgogo123 发表于 2015-7-4 00:44
第二题，的确可以优化到constant extra space. 感觉这题是西雅图Office的保留题目，不敢说人人都考，但是概 ...

请问一下这题怎么做啊

mantishrimp 发表于 2016-7-29 14:58
面成这样都会挂？！脸书真火啊～

感觉很多面试官也不考虑题目难易，他这个题一直拿来面，答案他都知道自然就觉得容易，然后谁要是没做出来就写差FEEDBACK

sealove999 发表于 2016-4-4 14:29
第二个

能讲讲思路吗，代码看不明白

sealove999 发表于 2016-4-4 14:29
第二个

终于看懂了，不过你的第二种解法每轮新建一个数组，那空间也是O(NK)不是O（N）吧