leetcode-753： 破解保险箱

• 题目
• 解题
• • 方法一：Hierholzer 算法

题目

题目链接
有一个需要密码才能打开的保险箱。密码是 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" 也能打开保险箱。

解题

方法一：Hierholzer 算法

参考链接

class Solution {
public:
    int node;
    string res;
    void dfs(vector<int>& side,int n,int k,int i){
        int currNode=i%node;//节点的值(n-1位)
        for(int j=0;j<k;j++){
            int tmp=currNode*k+j; //节点+边(1位) (共n位)
            if(!side[tmp]++){ /* 仅遍历没有走过的边 */
                dfs(side,n,k,tmp);
                res+=j+'0';//j+'0'代表一个字符('0'~'9')
            }
        }

    }
    string crackSafe(int n, int k) {
        node=pow(k,n-1);/* 节点个数 */
        vector<int> side(node*k,0);/* 边数标志，用来指示每条边是否遍历过 */
        dfs(side,n,k,0);/* 从 n -1 个 0 的节点开始寻找 */
        res.append(n-1,'0');/* 补充起始节点字符串 */
        return res;/* 无需 reverse，翻转前后均为正确答案 */
    }
};