破解保险箱

题目

753. 破解保险箱

---

有一个需要密码才能打开的保险箱。密码是 n 位数, 密码的每一位是 k 位序列 0, 1, ..., k-1 中的一个 。

你可以随意输入密码，保险箱会自动记住最后 n 位输入，如果匹配，则能够打开保险箱。

举个例子，假设密码是 "345"，你可以输入 "012345" 来打开它，只是你输入了 6 个字符.

请返回一个能打开保险箱的最短字符串。

示例1:

输入: n = 1, k = 2
输出: "01"
说明: "10"也可以打开保险箱。

示例2:

输入: n = 2, k = 2
输出: "00110"
说明: "01100", "10011", "11001" 也能打开保险箱。

提示：

1. n 的范围是 [1, 4]。
2. k 的范围是 [1, 10]。
3. k^n 最大可能为 4096。

题解

方法一：

思路

贪心

建立一个图，图中节点是n-1位的k进制数，若节点x移除高位尾接一个低位e（e < k）转变为节点y，则x存在指向y的一条有向边，边权为e。

例：

n = 3, k = 2

图来自大佬newhar

我们只需要不重复的遍历所有边那么构造出来的字符串就是最短的。

图中每个点有k个入度和k个出度，所以存在欧拉回路。

接下来可以从0号点出发，每次走最大边权的边，就可以走出一条欧拉回路。

代码

class Solution {
public:
    string crackSafe(int n, int k) {
        int sz = pow(10, n-1);
        vector<int> left(sz, k-1);
        string ans = string(n-1, '0');
        int cur = 0;
        while (left[cur] != -1) {
            int val = left[cur]--;
            ans.push_back('0'+val);
            cur = (cur*10+val)%sz;
        }
        return ans;
    }
};

方法二：

思路

Hierholzer 算法可以在一个欧拉图中找出欧拉回路

首先任选一点做为起点进行深搜，深搜每次经过一条边则删除。

当到达没有可选边的节点时，回溯并将指向该点的边加入栈中。即当节点x选择边
e走向节点y，而y无可选则的边，则回溯到x，然后将e加入到栈中。

最后完成深搜，栈中保存的就是逆向的欧拉回路，通过不断出栈得到的序列就是欧拉回路。

例：

n = 3, k = 2

图来自大佬newhar

若选取00作为起点，每次尽可能选取边权较小的边。

00 通过0边走向 00，删除0边

00 通过1边走向 01，删除1边

01 通过0边走向 10，删除0边

10 通过0边走向 00，删除0边

00 无边可走，回到10，将0加入栈中

10 通过1边走向 01，删除1边

01 通过1边走向 11，删除1边

11 通过0边走向 10，删除0边

10 无边可走，回到11，将0加入栈中

11 通过1边走向 11，删除1边

11 无边可走，回到11，将1加入栈中

11 无边可走，回到01，将1加入栈中

01 无边可走，回到10，将1加入栈中

10 无边可走，回到01，将0加入栈中

01 无边可走，回到00，将1加入栈中

00 无边可走，回到00，将0加入栈中

出栈后序列为 0 1 0 1 1 1 0 0

在出栈序列前加上初始的位置在00，就得到了构造的最短字符串

代码实现中，这个串是逆序的也是正确的。

代码

class Solution {
public:
    string crackSafe(int n, int k) {
        int sz = 1; for (int i=0; i<n; i++) sz *= k;
        vector<bool> st(sz, false);
        string ans;
        function<void(int)> dfs = [&](int x) {
            for (int i=0; i<k; i++) {
                int y = (x*k+i)%sz;
                if (!st[y]) {
                    st[y] = true;
                    dfs(y);
                    ans.push_back(i+'0');
                }
            }
        };
        dfs(0);
        return ans+string(n-1, '0');
    }
};