题目
有一个需要密码才能打开的保险箱。密码是 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 算法
节点上存放n-1位数，路径上1位，然后可以变成n位tmp=currNode*k+j，到另一个节点后，再转化为后n-1位
int currNode=i%node;
0~k-1就是到该节点后，可以选择的路径,通过side数组来记录删除的边。
由于记录路径，而不是节点，因此要在循环内, res+=j+'0'; 将路径加入到结果中去
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，翻转前后均为正确答案 */ } };
