Google面经题密码箱问题解法求问

求问这道题的算法，看不懂代码，求大神解释一下~
一堆密码箱，每个密码都是四位0-9之间，算一个暴力破解序列，包含所有可能的四位序列，让这个序列尽量短
用的是DeBruijn，代码如下

1. 
   
2. public class DeBruijn {
   
3.         public static String generateDeBruijnSequence(int k, int n) {
   
4.                 StringBuilder sequence = new StringBuilder();
   
5.                 generateLyndonWords(1, 1, k, new int[n+1], sequence);
   
6.                 return sequence.toString();
   
7.         }
   
8. 
   
9.         private static void generateLyndonWords(int t, int p, int k, int[] a, StringBuilder sequence) {
   
10.                 if (t > a.length-1) {
    
11.                         if((a.length-1)%p==0) {
    
12.                                 for(int i = 1; i < p+1;i++) {
    
13.                                         sequence.append(a[i]);
    
14.                                 }
    
15.                         }
    
16.                 } else {
    
17.                         a[t] = a[t-p];
    
18.                         generateLyndonWords(t+1,p, k, a, sequence);
    
19.                         for(int j=a[t-p]+1; j<=k-1; j++) {
    
20.                                 a[t] = j;
    
21.                                 generateLyndonWords(t+1,t, k, a, sequence);
    
22.                         }
    
23.                 }
    
24.         }
    
25.         public static void main(String[] args){
    
26.                 System.out.println(generateDeBruijnSequence(10, 4).length());
    
27.         }
    
28. }
    

复制代码

这里有个贴子说得很清楚：http://xwk.iteye.com/blog/2129621

这个写法更好，复杂度完全是O(E)了，不过对(10,4)还是会stackoverflow。设置-Xss2m或以上就可以，貌似不是啥大问题。

1. public class EulerSolution {
   
2.     int n, k, v;
   
3.     int[] edge;
   
4.     StringBuilder sequence;
   
5. 
   
6.     public String crackSequence(int k, int n) {
   
7.         this.n = n;
   
8.         this.k = k;
   
9.         v = 1; for (int i = 0; i < n - 1; ++i) v *= k; // vertices are n-1 bit radix k number.
   
10.         edge = new int[v]; // edge list
    
11.         sequence = new StringBuilder();
    
12.         dfs(0);
    
13. //        for (int i = 0; i < n - 1; ++i) sequence.append(0);
    
14.         return sequence.reverse().toString();
    
15.     }
    
16. 
    
17.     // Hierholzer's algorithm
    
18.     private void dfs(int u) {
    
19.         while (edge[u] != k) {
    
20.             int i = edge[u]++;
    
21.             dfs((u * k + i) % v);
    
22.             sequence.append(i);
    
23.         }
    
24.     }
    
25. 
    
26.     public static void main(String[] args) {
    
27.         System.out.println(new EulerSolution().crackSequence(9, 4).length());
    
28.     }
    
29. }

复制代码

我觉得这道题在题意明确的情况下，把所有状态看成点，状态之间的转移看成边是比较自然的。
这样就有两种看法，一种就是把4位看成状态，一种就是把3位看成状态。
把4位看成状态的图上面找Hamilton回路，很显然是本题的答案，因为访问了每一个节点一次且只有一次。
把3位看成状态的图上面找欧拉回路可能需要给面试官解释一下。但我觉得还是比较好解释的。
因为每一条边其实代表了一种4位的状态，于是就很好解释了。
那么上面的DFS找欧拉回路的算法就是相当简单有效的解法了。在删除边和查找下一个没有访问的边的复杂度是O(1)的情况下这个算法的复杂度是O(E)的，也就是O(k^n)的，de Buijin构造算法不会比这个复杂度更好。
我这个实现没有用LinkedList或者Hash来保存边的信息，所以每次都是循环所有可能的边，也就是O(k)查找边，所以总的复杂度是O(k^(n+1))。
考虑到
k = 10 n = 4
我觉得没啥问题。

我也是面的这道题- -

战栗的百香果 发表于 2016-1-22 07:50
我也是面的这道题- -

请问你知道求解得吗

神罗天征 发表于 2016-1-22 07:55
请问你知道求解得吗

我就是因为这道题跪了- -

战栗的百香果 发表于 2016-1-22 07:56
我就是因为这道题跪了- -

好吧，我就是看了面经看到了这道题，觉得太难了，google了解法，但是也不看懂……

神罗天征 发表于 2016-1-22 08:02
好吧，我就是看了面经看到了这道题，觉得太难了，google了解法，但是也不看懂……

我当时听到这道题写了个暴力然后就蒙了

战栗的百香果 发表于 2016-1-22 08:18
我当时听到这道题写了个暴力然后就蒙了

这面得太难了吧，gg太变态了。那暴力求解怎么做呀

这个题目有些难了。主要是很多人没有见过Lyndon word。可以参考 https://en.wikipedia.org/wiki/Lyndon_word
这样的题目其实回答的时候要和面试官讨论，首先说只有1个箱子，每个密码只有1位，每位密码都只有2个值可去，然后开始向上逐一构造，比方说，先变化成2位密码，看看怎么写。好像GOOGLE非常喜欢问这类构造性的问题。

神罗天征 发表于 2016-1-22 08:38
这面得太难了吧，gg太变态了。那暴力求解怎么做呀

dfs生成所有四位数啊- -

战栗的百香果 发表于 2016-1-22 12:35
dfs生成所有四位数啊- -

我能想到的也是暴力破解啊，四个for循环嵌套