题目描述
leetcode 困难题
有一个需要密码才能打开的保险箱。密码是 n 位数, 密码的每一位都是范围 [0, k - 1] 中的一个数字。
保险箱有一种特殊的密码校验方法，你可以随意输入密码序列，保险箱会自动记住 最后 n 位输入 ，如果匹配，则能够打开保险箱。
例如，正确的密码是 “345” ，并且你输入的是 “012345” ：
输入 0 之后，最后 3 位输入是 “0” ，不正确。
输入 1 之后，最后 3 位输入是 “01” ，不正确。
输入 2 之后，最后 3 位输入是 “012” ，不正确。
输入 3 之后，最后 3 位输入是 “123” ，不正确。
输入 4 之后，最后 3 位输入是 “234” ，不正确。
输入 5 之后，最后 3 位输入是 “345” ，正确，打开保险箱。
在只知道密码位数 n 和范围边界 k 的前提下，请你找出并返回确保在输入的 某个时刻 能够打开保险箱的任一 最短 密码序列 。
示例1：
1
2
3
4
5
6
7
8
| 输入：n = 2, k = 2
输出："01100"
解释：对于每种可能的密码：
- "00" 从第 4 位开始输入。
- "01" 从第 1 位开始输入。
- "10" 从第 3 位开始输入。
- "11" 从第 2 位开始输入。
因此 "01100" 可以确保打开保险箱。"01100"、"10011" 和 "11001" 也可以确保打开保险箱。
|
提示1：
1
2
3
| 1 <= n <= 4
1 <= k <= 10
1 <= kn <= 4096
|
Hierholzer 算法
实际上是求以所有 $n - 1$ 位密码组合作为顶点所构成图的 欧拉回路 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
private int numRange;
private int mod;
private StringBuilder ans = new StringBuilder();
private Set<Integer> visit = new HashSet<>();
public String crackSafe(int n, int k) {
numRange = k;
mod = (int)Math.pow(10, n - 1);
hierholzer(0);
return ans.append("0".repeat(n - 1)).toString();
}
private void hierholzer(int p){
for(int i = 0; i < numRange; i++){
int e = p * 10 + i;
if(!visit.add(e)){
continue;
}
hierholzer(e % mod);
ans.append(i);
}
}
}
|