一道Amazon intern面试题有感

cqx83 发表于 2014-3-29 03:23
实在没看出这题有用bitset的必要啊。。

just for saving memory.

if you did this I think interviewer would give u a higher feedback.

北美农民 发表于 2014-3-30 02:09
Sry cannot type Chinese.

This is for going backward and recover bits if we did not find solutio ...

Thank you very much, really resolve my confusion.

Longford Pairing 既然是一种permutation, 自然就是考虑用DFS, 在DFS的过程中，每次尝试加入一个新的数字到solution中时, 都要check是否满足Longford Pairing的feature, 所以这道题的思路也是一种backtracking的想法。注意需要一个List<List<Integer>>保存结果。

1. public class LongfordSequence {
   
2.         public List<List<Integer>> gernerateSequence(int n) {
   
3.                 List<List<Integer>> result = new ArrayList<List<Integer>>();
   
4.                 int[] count = new int[n + 1];
   
5.                 gernerateHelper(result, new ArrayList<Integer>(), count);
   
6.                 return result;
   
7.         }
   
8. 
   
9.         private void gernerateHelper(List<List<Integer>> result, List<Integer> solution, int[] count) {
   
10.                 if (solution.size() == 2 * (count.length - 1)) {
    
11.                         result.add(new ArrayList<Integer>(solution));
    
12.                         return;
    
13.                 }
    
14. 
    
15.                 for (int i = 1; i <= count.length - 1; i++) {
    
16.                         if (count[i] == 0) {
    
17.                                 solution.add(i);
    
18.                                 count[i] = 1;
    
19.                                 gernerateHelper(result, solution, count);
    
20.                                 solution.remove(solution.size() - 1);
    
21.                                 count[i] = 0;
    
22.                         } else if (count[i] == 1) {
    
23.                                 int size = solution.size();
    
24.                                 if (size - i - 1 >= 0 && solution.get(size - i - 1) == i) {
    
25.                                         solution.add(i);
    
26.                                         count[i] = 2;
    
27.                                         gernerateHelper(result, solution, count);
    
28.                                         solution.remove(solution.size() - 1);
    
29.                                         count[i] = 1;
    
30.                                 }
    
31.                         }
    
32.                 }
    
33.         }
    
34. }

复制代码