1.题目基本信息
1.1.题目描述
有一个需要密码才能打开的保险箱。密码是 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.2.题目地址
https://leetcode.cn/problems/cracking-the-safe/description/
2.解题方法
2.1.解题思路
欧拉回路+深度优先搜索。该题可以抽样成一个图，每个n-1位数为一个结点，每个n位数为一条边，从a1a2...a_(n-1)结点到a2a3...an的边；由于保险箱的记忆特性，所以每个结点的入度和出度相等且都为k，所以图中一定存在欧拉回路，这个欧拉回路上一定包含了所有可能的密码组合，且是最短的密码输入顺序；题目要求的最短密码序列等价于「起始0结点」+「除首节点外欧拉回路上结点最后一个元素组成的序列」
2.2.解题步骤
第一步，构建维护变量。stack栈维护欧拉回路上结点的最后一个元素（这里的stack在循环内压栈，所以不会记录首节点）；visited维护已经访问过的边
第二步，构建深搜函数。从node结点开始，深搜欧拉回路，并更新维护变量
第三步，执行深搜，并根据首节点和stack构建最短序列
3.解题代码
python3代码
class Solution:
def crackSafe(self, n: int, k: int) -> str:
# 思路：欧拉回路。该题可以抽样成一个图，每个n-1位数为一个结点，每个n位数为一条边，从a1a2...a_(n-1)结点到a2a3...an的边；由于保险箱的记忆特性，所以每个结点的入度和出度相等且都为k，所以图中一定存在欧拉回路，这个欧拉回路上一定包含了所有可能的密码组合，且是最短的密码输入顺序；题目要求的最短密码序列等价于「起始0结点」+「除首节点外欧拉回路上结点最后一个元素组成的序列」
highest = 10 ** (n - 1)
# 第一步，构建维护变量。stack栈维护欧拉回路上结点的最后一个元素（这里的stack在循环内压栈，所以不会记录首节点）；visited维护已经访问过的边
stack = []
visited = set()
# 第二步，构建深搜函数。从node结点开始，深搜欧拉回路，并更新维护变量
def dfs(node:int):
for i in range(k):
edge = node * 10 + i
if edge not in visited:
visited.add(edge)
subNode = edge % highest
dfs(subNode)
stack.append(str(i))
# 第三步，执行深搜，并根据首节点和stack构建最短序列
dfs(0)
return "0" * (n - 1) + "".join(stack[::-1])c++代码
class Solution {
public:
int highest;
stack<int> stk;
set<int> visited;
void dfs (int node, int k) {
for (int i = 0; i < k; i++) {
int edge = node * 10 + i;
if (visited.find(edge) == visited.end()) {
visited.insert(edge);
int subNode = edge % highest;
dfs(subNode, k);
stk.push(i);
}
}
}
string crackSafe(int n, int k) {
highest = pow(10, n - 1);
dfs(0, k);
string result;
for (int i = 0; i < n - 1; i++) {
result += '0';
}
while (!stk.empty()) {
result += to_string(stk.top());
stk.pop();
}
return result;
}
};4.执行结果
