破解保险箱

标签: 深度优先搜索 图 欧拉回路

难度: Hard

有一个需要密码才能打开的保险箱。密码是 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：

输入：n = 1, k = 2
输出："10"
解释：密码只有 1 位，所以输入每一位就可以。"01" 也能够确保打开保险箱。

示例 2：

输入：n = 2, k = 2
输出："01100"
解释：对于每种可能的密码：
- "00" 从第 4 位开始输入。
- "01" 从第 1 位开始输入。
- "10" 从第 3 位开始输入。
- "11" 从第 2 位开始输入。
因此 "01100" 可以确保打开保险箱。"01100"、"10011" 和 "11001" 也可以确保打开保险箱。

提示：

  • 1 <= n <= 4
  • 1 <= k <= 10
  • 1 <= kn <= 4096

Submission

运行时间: 30 ms

内存: 16.5 MB

class Solution:
    def crackSafe(self, n: int, k: int) -> str:
        if n == 1:
            return ''.join(str(i) for i in range(k))

        m = k ** (n - 1)
        adj = [[] for _ in range(m)]
        for i in range(m):
            x = i * k % m
            adj[i] = [j for j in range(x, x + k)]
        a = [0]
        stack = []
        while a:
            u = a[-1]
            if adj[u]:
                a.append(adj[u].pop())
            else:
                stack.append(a.pop())
        ss = ['0' * (n - 2)]
        for x in reversed(stack):
            ss.append(str(x % k))
        return ''.join(ss)

Explain

这道题目可以使用Hierholzer算法来找到Euler路径，即一条通过图中每条边恰好一次的路径。图中的节点表示密码的前n-1位，而边则表示可能的n位密码。算法的核心是构建一个有向图，图的节点表示长度为n-1的序列，每个节点会有k条出边，这些出边对应在该序列后添加一个数字形成的n位序列。解题过程首先构建图的邻接表，然后使用深度优先搜索遍历图来寻找Euler回路，最后将这个回路转换成对应的密码序列。

时间复杂度: O(k^n)

空间复杂度: O(k^n)

class Solution:
    def crackSafe(self, n: int, k: int) -> str:
        if n == 1:
            # 当密码长度为1时，简单返回0到k-1的所有可能
            return ''.join(str(i) for i in range(k))

        # 计算前缀为n-1的所有可能状态数量
        m = k ** (n - 1)
        # 创建邻接表
        adj = [[] for _ in range(m)]
        for i in range(m):
            # 计算每个状态的出边
            x = i * k % m
            adj[i] = [j for j in range(x, x + k)]
        a = [0]
        stack = []
        # 使用DFS找到Euler回路
        while a:
            u = a[-1]
            if adj[u]:
                a.append(adj[u].pop())
            else:
                stack.append(a.pop())
        # 构建最终的密码序列
        ss = ['0' * (n - 2)]
        for x in reversed(stack):
            ss.append(str(x % k))
        return ''.join(ss)

Explore

Hierholzer算法是用于寻找Euler路径的经典算法，它特别适用于需要遍历图中每条边恰好一次的问题。在破解保险箱的场景中，我们需要找到一个密码序列，该序列通过所有可能的n位密码恰好一次，这可以被抽象为在一个有向图中找到一个Euler回路。因此，考虑到题目需求和Hierholzer算法的适用性，我决定采用此算法来解决问题。

Hierholzer算法适用于有向图和无向图，但它要求图中至少存在一个欧拉路径或欧拉回路。对于无向图，欧拉回路存在的条件是所有顶点的度数都是偶数；欧拉路径存在的条件是恰有两个顶点的度数是奇数，其他顶点的度数都是偶数。对于有向图，欧拉回路存在的条件是每个顶点的入度和出度相等；欧拉路径存在的条件是恰有一个顶点的出度比入度大1，恰有一个顶点的入度比出度大1，其他顶点的入度和出度相等。

在这个算法中，图的节点代表长度为n-1的序列。假设使用数字0到k-1，那么有k^(n-1)种可能的序列，这些序列作为图的节点。为了构建边，对于每个节点（即每个序列），我们通过在序列末尾添加一个从0到k-1的数字来生成新的n位序列。这样，从每个节点出发都会有k条边，对应于添加不同数字得到的序列。我们通过计算来确定每个新序列对应的节点，确保边的正确连接。

在使用DFS进行欧拉回路的搜索过程中，我们维护一个栈来记录访问的路径，并且对每个节点维护一个邻接表来记录其可达的节点。当访问一个节点时，我们将其从当前节点的邻接表中移除，这样每条边只会被访问一次。一旦一个节点没有更多可访问的边，我们就将其加入到最终的路径中。这种方法确保了每条边在整个过程中仅被访问一次，符合欧拉路径的要求。