破解保险箱【LC753】
There is a safe protected by a password. The password is a sequence of n digits where each digit can be in the range [0, k - 1].
The safe has a peculiar way of checking the password. When you enter in a sequence, it checks the most recent n digits that were entered each time you type a digit.
- For example, the correct password is “345”
and you enter in “012345” :
。After typing 0, the most recent 3 digits is "0", which is incorrect.
。After typing 1, the most recent 3 digits is "01", which is incorrect.
。After typing 2, the most recent 3 digits is "012", which is incorrect.
。After typing 3, the most recent 3 digits is "123", which is incorrect.
。After typing 4, the most recent 3 digits is "234", which is incorrect.
。After typing 5, the most recent 3 digits is "345", which is correct and the safe unlocks.
Return any string of minimum length that will unlock the safe at some point of entering it.
有点难的…
欧拉回路：通过图中所有边一次且仅一次行遍所有顶点的回路称为欧拉回路
dfs
- 思路：
。题意要求输入一个字符串，能够打开保险柜，密码的长度为n，每位数字小于k，因此题意可以转化为找到一个最短字符串，其包含了n位k进制所有的排列组合
。由于每次值取最后一个字符进行移动，那么对于n位密码，将n-1位的所有可能组合看做一个点，对于每个节点会有k条入边和k条出边，因此它一定存在一个欧拉回路
。如何找到最短字符串？
从00出发进行dfs搜索没有加入过的边，直至回到了该节点。此时图中仍有边未遍历到，那么从某个节点v开始，继续搜寻，然后将该路径嵌入，直至所有路径全部被添加。注意：需要将前缀加入结果集末尾
- 实现
。使用HashSet存储已经遍历过的n位k进制组合，然后
class Solution { Set<Integer> seen = new HashSet<Integer>(); public String crackSafe(int n, int k) { StringBuilder sb = new StringBuilder(); int nodeNum = (int)Math.pow(k, n - 1); dfs(0, k, sb, nodeNum); for (int i = 1; i < n; i++){ sb.append('0'); } return new String(sb); } public void dfs(int node, int k, StringBuilder sb, int nodeNum){ for (int i = 0; i < k; i++){ int x = node * k + i; if (seen.add(x)){ dfs(x % nodeNum, k, sb, nodeNum); sb.append(i); } } } }
。复杂度
- 时间复杂度：O ( k n )
- 空间复杂度：O ( k n − 1 )
贪心
- 思路：贪心
上面的搜索过程之所以会出现有部分边未遍历的情况，是因为起始点回的太早，那么如果可以尽可能晚回起点，那么就能遍历更多的边
。证明
- 最终我们回到起点密码0000，因为是从大到小取数的，说明之前已经有k-1次走到状态000，取走了1~k-1。
- 那这k次到达状态000是怎么来的呢？是尝试过密码x000后走到的。也就是说，我们一定尝试过所有k个形如x000的密码。
- 同理，当我们尝试某个密码x000时一定是第k次到达状态x00，所以我们一定尝试过所有形如yx00的密码。
- 以此类推，我们一定已经尝试过所有可能的密码。
- HashMap实现
选择00…作为起始点，每次要选择添加的数字时，从大数字开始，尽可能晚回到起始点
class Solution { public String crackSafe(int n, int k) { StringBuilder sb = new StringBuilder(); int edgesNum = (int)Math.pow(k, n); Map<String,Integer> strToVal = new HashMap<>();// 存储节点已经选择的最小数值 下一个可以选择的数值是其减1 // 字符串的最短长度为 n - 1 + edgesNum for (int i = 1; i < n; i++){// 初始0 节点为n-1位 sb.append('0'); } // 遍历所有边 while (edgesNum > 0){ String str = sb.substring(sb.length() - n + 1, sb.length()); strToVal.put(str, strToVal.getOrDefault(str, k) - 1); // if (!strToVal.containsKey(str)){ // strToVal.put(str, k - 1); // }else{ // strToVal.put(str, strToVal.get(str) - 1); // } sb.append(strToVal.get(str)); edgesNum--; } return new String(sb); } }
。复杂度
- 时间复杂度：O ( k n )
- 空间复杂度：O ( k n − 1 )
- 实现：数组代替哈希表，数组的下标是字符串节点的整数值，值为该节点已经选择的最小数值
class Solution { public String crackSafe(int n, int k) { int edgesNum = (int)Math.pow(k, n), nodeNum = (int)Math.pow(k, n - 1); int[] nodeToVal = new int[nodeNum];// 存储节点已经选择的最小数值 下一个可以选择的数值是其减1 Arrays.fill(nodeToVal, k);// 初始化值为k 下一个可选择的数值为k-1 StringBuilder sb = new StringBuilder(); // 字符串的最短长度为 n - 1 + edgesNum for (int i = 1; i < n; i++){// 添加初始0 n-1个 sb.append('0'); } // 遍历所有边 for (int i = 0, idx = 0; i < edgesNum; i++){ int edge = --nodeToVal[idx]; sb.append(edge); idx = (idx * k + edge) % nodeNum;// 去除最高位加入新的一位后节点的值 } return new String(sb); } }
。复杂度
- 时间复杂度：O ( k n )
- 空间复杂度：O ( k n − 1 )
