破解保险箱

题目描述 

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

题意转化
首先对题意进行转化和抽象，具体方式类似官方题解，即将所有的 n−1 位数作为节点。每个节点有 k 条边，节点上添加数字 0∼k−1 视为一条边。

举例说明，如 n=3,k=2（三位二进制数），其节点（二位二进制数）为 “00”，“01”，“10”，“11”，每个节点有 2 条边，节点上添加数字 0∼1 可转化到自身或另一个节点，如下图所示。

如果我们从任一节点出发，能够找出一条路径，经过图中的所有边且只经过一次，然后把边上的数字写入字符串（还需加入起始节点的数字），那么这个字符串显然符合要求，而且找不出比它更短的字符串了。

贪心构造算法
当我们无路可走时，一定是在起始点，并且起始点的所有边都已经过。 这是因为所有节点的入度和出度均为 k。如果我们不在起始点，那 “只要有进去的路，就一定还有至少一条出去的路”。

再看之前出现的无路可走的情况（下图），我们发现，起始点回的太早了。从贪心的角度来想，如果可以 尽可能晚返回起始点，就能遍历更多的边。

如果实现这个算法呢？很简单，稍微改动之前的算法即可。我们选择 “00” 作为起始点。但是每次要选择添加的数字时，从大数字开始（即从 k−1 遍历到 0）。这样可以尽可能晚地回到起始点。

 代码：

class Solution {
public:string crackSafe(int n, int k) {int kn = pow(k, n), kn_1 = pow(k, n-1), num[kn_1];fill(num, num + kn_1, k-1);string s(kn + (n-1), '0');for(int i = n-1, node = 0; i < s.size(); ++i) {s[i] = num[node]-- + '0';node = node*k - (s[i-(n-1)]-'0')*kn_1 + num[node] + 1;}return s;}
};