POJ 1780 Code - Google interview: safe box

http://poj.org/problem?id=1780

KEY Inc., the leading company in security hardware, has developed a new kind of safe. To unlock it, you don't need a key but you are required to enter the correct n-digit code on a keypad (as if this were something new!). There are several models available, from toy safes for children (with a 2-digit code) to the military version (with a 6-digit code).

The safe will open as soon as the last digit of the correct code is entered. There is no "enter" key. When you enter more than n digits, only the last n digits are significant. For example (in the 4-digit version), if the correct code is 4567, and you plan to enter the digit sequence 1234567890, the door will open as soon as you press the 7 key.

The software to create this effect is rather simple. In the n-digit version the safe is always in one of 10^n-1 internal states. The current state of the safe simply represents the last n-1 digits that have been entered. One of these states (in the example above, state 456) is marked as the unlocked state. If the safe is in the unlocked state and then the right key (in the example above, 7) is pressed, the door opens. Otherwise the safe shifts to the corresponding new state. For example, if the safe is in state 456 and then you press 8, the safe goes into state 568.

A trivial strategy to open the safe is to enter all possible codes one after the other. In the worst case, however, this will require n * 10ⁿ keystrokes. By choosing a good digit sequence it is possible to open the safe in at most 10ⁿ + n - 1 keystrokes. All you have to do is to find a digit sequence that contains all n-digit sequences exactly once. KEY Inc. claims that for the military version (n=6) the fastest computers available today would need billions of years to find such a sequence - but apparently they don't know what some programmers are capable of...

Input

The input contains several test cases. Every test case is specified by an integer n. You may assume that 1<=n<=6. The last test case is followed by a zero.

Output

For each test case specified by n output a line containing a sequence of 10ⁿ + n - 1 digits that contains each n-digit sequence exactly once.

Sample Input

1
2
0

Sample Output

0123456789
00102030405060708091121314151617181922324252627282933435363738394454647484955657585966768697787988990

http://www.1point3acres.com/bbs/thread-166111-1-1.html

一堆密码箱，每个密码都是四位0-9之间，算一个暴力破解序列，包含所有可能的四位序列，让这个序列尽量短

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

dfs生成所有四位数啊- -

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

个人意见，这个题的最优解法要求你对de Bruijn图和汉密尔顿回路或者Lyndon words有相当了解，作为面试题的话，明显过于难了。所以我想应该和Flip Game这类题是一个性质：你用DFS等方法解出来是完全可以的，然后再进行优化，复杂度分析等等。这题的作用应该是看你“在面对一个非常难的问题时，会采用怎样的思考方式去试图解决它”。

我看了你的面经，关键问题在于“转动式”密码锁有两种：一种像老式电话的拨号盘那样，所有数字均匀刻在一个圆上，中间的旋柄上有一个指针，通过旋转旋柄来依次输入数字；另一种是行李箱上常用的那种，每一位数字单独有一个转盘，可以按任意顺序设置各位数字。

两种有一个关键区别：就是第一种必须顺序输入密码，每次试验的前2位必是上次试出结果的后2位；而第二种可以以任意顺序输入密码，每次试验结果的任意2位都可以和上次结果的对应2位相同。

第二种，旅行箱的密码锁，三位可以随意选择的转

如果是这种就比较简单一些。就是把每一个三位数想象成一个图中的节点，每个节点和周围的8个节点相连。把会爆炸的组合从这个图中删去。最后实际上就是求“在一个3维图上找到从000节点开始到777节点的最短路径”。因为这个图是无权的，用BFS最合适。当然，实际的节点数只有1000，用DFS其实也可以。

所以那这题就是在得在一个3位deBruijin图上找一个欧拉回路。每一个点有10个出度10个入度，一共1000个vertices和10000条edge。 不用Lyndon words的知识应该也可以构造出来。效率肯定比最优解低，但应该比Brute Force DFS快。

我之前贴的那段代码其实本质上就是在4维de Bruijn图上找Hamilton回路，和3维de Bruijn上的欧拉回路是一个意思。但是，这是在我已知de Bruijn是Hamiltonian的情况下写出的代码。如果是面试的时候，假设我之前从没有听说过de Bruijn，如何快速向面试官说明de Bruijn图是Hamiltonian或者Eulerian呢？

找欧拉回路有非常简单的Hierholzer算法，代码就这几行。我跟deBruijn对比过，是正确的。这里面为了和deBruijn答案相近我把结果reverse了，不reverse肯定也是有效答案。不过这个写法计算k = 10 n = 4会出现stackoverflow. 需要设置-Xss2m或以上。

1. public class EulerSolution {
2.     int n, k, v;
3.     boolean[][] visited;
4.     StringBuilder sequence;
5. 
   
6.     public String crackSequence(int k, int n) {
7.         this.n = n;
8.         this.k = k;
9.         v = (int)Math.pow(k, n - 1); // vertices are n-1 bit radix k number.
10.         visited = new boolean[v][k]; // edge list
11.         sequence = new StringBuilder(); 
12.         dfs(0);
13.         return sequence.reverse().toString();
14.     }
15. 
    
16.     private void dfs(int u) {
17.         for (int i = 0; i < k; ++i) {
18.             if (!visited[u][i]) {
19.                 visited[u][i] = true;
20.                 dfs((u * k + i) % v);
21.                 sequence.append(i);
22.             }
23.         }
24.     }
25. }

证明这个图是欧拉的非常容易，因为有向图，每一个节点的入度和出度都相等，必然是欧拉图。

我觉得这道题在题意明确的情况下，把所有状态看成点，状态之间的转移看成边是比较自然的。

这样就有两种看法，一种就是把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

我觉得没啥问题。

这个写法更好，复杂度完全是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. }

改写成Iterative，避免了全局变量，复杂度O(E) = O(k^n)

1. public class IterativeEulerSolution {
2. 
   
3.     // Hierholzer's algorithm
4.     public String crackSequence(int k, int n) {
5.         int v = 1;
6.         for (int i = 0; i < n - 1; ++i) v *= k; // vertices are n-1 bit radix k number.
7.         int[] edge = new int[v];
8.         StringBuilder sequence = new StringBuilder();
9.         
10.         int u = 0, i = 0;
11.         Deque<Integer[]> stack = new ArrayDeque<>();
12.         while (true) {
13.             if (i == k) {
14.                 if (stack.isEmpty()) break;
15.                 Integer[] t = stack.pop();
16.                 u = t[0];
17.                 sequence.append(t[1]);
18.                 i = edge[u];
19.             } else {
20.                 stack.push(new Integer[]{u, i});
21.                 edge[u]++;
22.                 u = (u * k + i) % v;
23.                 i = edge[u];
24.             }
25.         }
26. 
    
27. //        for (int i = 0; i < n - 1; ++i) sequence.append(0);
28.         return sequence.reverse().toString();
29.     }
30. 
    
31.     public static void main(String[] args) {
32.         System.out.println(new IterativeEulerSolution().crackSequence(10, 4).length());
33.     }
34. }

大概写了一下DFS的代码，我认为面试的话，给到这种解法已经可以了。下面的代码基于这些事实：
1. 因为de Bruijn sequence其实上是一个环，所以这个序列可以以任意四位数开头。此处，我们总是选0000开头。
2. de Bruijn sequence长度总是k^n，在本题中就是10^4。

        bool DFS(int ind) {
                if (ind==upper) { // No more number left
                        for (int i = 1; i <= n-1; ++i) { // Still need to validate the numbers that "wrap around"
                string st = seq.substr(upper-n+i, n-i) + seq.substr(0, i);
                                int temp = atoi(st.c_str());
                                if (avail[temp] == false) {
                    return false;
                                }
                        }
                        return true;
                }

                int prefix = atoi(seq.substr(ind-(n-1), n-1).c_str()) *10; 
                for (int i = 0; i <= 9; ++i) {
                        int cur = prefix + i;    // Try each possible choice at the current location
                        if (avail[cur]) {        // If this number hasn't appeared so far
                                avail[cur] = false;  // then try it.
                                seq[ind] = i + '0';
                                if (DFS(ind+1)) return true; 
                                avail[cur] = true;
                        }
                }
                return false;
        }
public:
    int n;
        int upper;
        vector<bool> avail;
        string seq;

        DeBruijn10(int _n):
                n(_n),
                upper(pow(10, n)),
                avail(upper, true),
                seq(upper, '0')
        {
                avail[0] = false;
                DFS(n);
        }
        void output() const {
            cout << "Length = " << seq.size() <<endl;
                cout << seq << endl;
        }

首先你要弄明白你面对的是一个神马密码锁，它的特性是这样的：

一个长度为n=4的密码框，一个键盘有k=10个按键，分别是0~9。

你输入0000，系统会验证0000是否是正确密码。

这时候你再输入一个1，不同的密码锁有不同的处理方式

一种会reset，也就是说前面的4个0消失了，你需要继续输入4个数供系统判断。

另一种不会reset，它会验证最近键入的4歌数字，即0001。

我们面对的是后一种。

如果是前一种的话，没啥好想的，破解序列就是4*10000

但是后一种，可以做到长度为10003的破解序列覆盖所有可能的10000个4位数。

题目就是让你找到这个序列。

http://blog.csdn.net/u013480600/article/details/30049093

首先题目中说了对于n位密码,锁中存了一个n-1位的当前状态.

可以证明:所有10^(n-1)个状态(一共这么多个,可以自己算算)中,任意一个状态都有一条出边(由0-9构成)和一条入边(由0-9构成),且出边数==入边数(这个可以自己假定n=1,n=2验证一下,注意这里可能存在0000这种自环). 所有这个锁的状态图是一个欧拉图,可以找到一个欧拉回路,正好可以将该欧拉图的所有边走仅一次.(走过所有边一次等同于遍历了所有可能的n位密码一次,想想是不是)

所以对于这道题,我们只需要输出其状态图的欧拉回路即可.不过既然要输出欧拉回路,就要遍历所有的可行边.但是这个图中的边是无数的重复0-9的数字,我们如何标记每一条边呢?

假设n=4,我们用4321(四千三百二十一)表示一条从432状态经过数字1出去的边.这种表示方式我们可以保证可以不重复的标记该状态图中的所有边.

注意(假设n=4)0000一定是一个可能的密码,所以我们把最终结果速度ans的0-3位设为0,且标记vis[0]为true(表示从状态000经0边出去的,这是一个自环.从000经过0边依然是到000状态.注意:我们标记的是每一条边,不是每个状态节点).

剩下的就是模拟栈来打印欧拉路径的事了.这有点麻烦.注意这里我们模拟的过程如下:首先初始状态是状态0,下面

从状态0走边00到状态0,(00)

从状态0走边01到状态1,(001)

从状态1走边10到状态0,(0010)

从状态0走边02到状态2,(00102)

从状态2走边00到状态0,(001020)

从状态0走边03到状态3,(0010203)

…

当前我们的ans数组已经为(0010203040506070809) 了,我们当前状态是9,且90这条边我们没走过,所以我们将走90边:

从状态9走边90到状态0,( 00102030405060708090)

此时我们发现我们现在在状态0,但是0节点的所有出边我们已经走过了一遍(也就是说我们进到0状态就出不去了),这样我们输出不了欧拉回路了,说明我在状态9的时候不应该先走边90,而应该去走边91,92…等,然后我们通过某条边X9回到了状态9之后,最后走边90结束欧拉回路的过程.(因为起点是状态0,终结点也是状态0)

所以对于我们已经从9走了边90到了死胡同0状态,我们应该回退该过程,即标记90边未走过,且把当前状态重新设为9,且我们选择边的起点应该从91(即0的下一个位置)开始选.

上面这个过程是用数组栈模拟深度优先遍历的过程,而不是模拟euler函数的过程.(但是我们如何证明深度优先遍历就一定能输出欧拉回路呢?这个问题我还不知道,其实就是euler递归函数如何非递归实现的问题)

1. const int maxn=1000000+10;  
2. char ans[maxn];//保存最终的结果  
3. bool vis[maxn];//标记边是否被走过  
4. int main()  
5. {  
6.     int n;  
7.     while(scanf("%d",&n)==1&&n)  
8.     {  
9.         if(n==1)  
10.         {  
11.             printf("0123456789\n");  
12.             continue;  
13.         }  
14.   
15.         int mod=1,end=1;  
16.         for(int i=1;i<=n;i++)  
17.         {  
18.             mod*=10;  
19.             end*=10;  
20.         }  
21.         mod /=10;  
22.         end+=n-1;  
23.         for(int i=0;i<n;i++)  
24.             ans[i]='0';  
25.         memset(vis,0,sizeof(vis));  
26.         vis[0]=true;  
27.         int now=0;//now表示的是当前所处的节点状态(即由n-1位数位构成的整数)  
28.         int i=0,pos=n;  
29.         while(pos<end)  
30.         {  
31.             now %=mod;  
32.             for(;i<10;i++)if(!vis[now*10+i])//当前状态节点还有没有走过的边  
33.             {  
34.                 vis[now*10+i]=true;  
35.                 ans[pos++]=i+'0';  
36.                 now = now*10+i;  
37.                 i=0;  
38.                 break;  
39.             }  
40.             if(i==10&&pos<end)//当前递归层走不通了(即我们进入了一个不存在没走过边的节点),且还没有走完所有的边  
41.             {  
42.                 pos--;  
43.                 now = (ans[pos-n+1]-'0')*mod + now;  
44.                 vis[now]=false;//消除死胡同的标记,因为如果直接在当前状态走边now的话,会进死胡同,所以回退  
45.                 i=now%10+1;  
46.                 now/=10;  
47.             }  
48.         }  
49.         ans[end]='\0';  
50.         printf("%s\n",ans); //注意:如果此处ans是int输出,一个个的输出每个数字的话,时间从79ms->489ms  
51.     }  
52.     return 0;  
53. }  

http://blog.csdn.net/abgnwl/article/details/48225425

给出的答案长度是10^n+n-1 如果每一次的数字都不重复的话 而且两个数之间共享了n-1位相同的数字

窗口每向后滑一次 产生一个新的数 一共10^n个数 滑了10^n-1次 加上第一个数的长度n 所以答案一共10^n+n-1个数字

而所有数字要求出现且仅出现1次

把每个数字转化为边 每个数前n-1位到后n-1位之间有一条边 求图的欧拉回路

http://www.cnblogs.com/CSU3901130321/p/4467807.html

poj 1780 ， poj 1392 欧拉回路求前后相互衔接的数字串

两道题目意思差不多

第一题是10进制 ， 第二题是2进制的

 5 #define N 1000010
 6 
 7 int ans[N] , cnt[N] , stack[N];
 8 int top1 , top2;
 9 int mod;
10 void euler(int v)
11 {
12     while(cnt[v]<10)
13     {
14         int w=v*10+cnt[v];
15         cnt[v]++;
16         stack[top1++]=w;
17         v=w%mod;
18     }
19 }
20 
21 int main()
22 {
23   //  freopen("in.txt" , "r" , stdin);
24     int n;
25     while(scanf("%d" , &n) , n)
26     {
27         top1 = 0 , top2 = 0 , mod = (int)pow(10.0,(n-1)*1.0);
28         stack[top1++] = 0;
29         memset(cnt , 0 , sizeof(cnt));
30         cnt[0]++;
31         while(top1)
32         {
33             ans[top2++] = stack[--top1];
34             int v = ans[top2-1]/10;
35             euler(v);
36         }
37         for(int i=1 ; i<=n ; i++) printf("%d" , 0);
38         for(int i=top2-1 ; i>=1 ; i--) printf("%d" , ans[i]%10);
39         puts("");
40     }
41     return 0;
42 }