您的位置:首页 > 房产 > 家装 > Cracking the Safe

Cracking the Safe

2024/12/23 9:46:24 来源:https://blog.csdn.net/m0_49303993/article/details/141730502  浏览:    关键词:Cracking the Safe

在这里插入图片描述
原题链接:https://leetcode.cn/problems/cracking-the-safe/description/

题目要求的是,某个时刻能够打开保险箱的任一最短密码序列,需要包含所有密码子串。
答案应当是一个字符串,任意长度为n的子串的都是一种密码方案。
对于有n位,每位k种方案的密码串,共有k^n个。
题目要求最短,那么任意位置选出的子串应当是不重复的。
也就是说,一个长度为n的滑动窗口,在移动k^n次后,应得到k^n个不同的密码串。
一次滑动得到的两个不同密码串,前者的n-1位后缀是后者的n-1位前缀。
题目要求长度为n,将长度为n-1k^(n-1)个串作为图的节点。
通过追加[0,k),可以得到k^n个密码串,每个串的后n-1位子串一定等于图中的某个节点。在追加字符前前的子串,和,追加字符后的子串的后n-1位子串,之间,建立一条有向边。

  • 那么图中的每个节点都有k条出边,指向k个不同的图中节点。
  • k个图中节点一定是不同的,因为最后一个字符,也就是新追加的字符,是不相等的。

对于任意节点a1a2...aiaj,通过在xa1a2...ai末尾追加最后一个字符aj取后缀后得到,首位被舍弃。
首位有[0,k)k种情况,任意节点都有k的可选的状态来源:

  • 那么图中的每个节点都有k条入边,来自k个不同的图中节点。

那么图中的每个点,都有k条出边和入边。
那么任意节点出发,都有一条欧拉回路。
最暴力的写法是,枚举每一位所有可能的情况,将k^n个密码串拼接。但必然不是最短方案。
因为一定有密码串满足一者的后缀等于另一者的前缀,可以借此压缩密码串长度。

dfs过程分析

状态表示node

  • 集合:已经生成的串,的末尾n-1个字符的状态压缩表示为node
  • 属性:从node出发的最短序列

状态转移:

  • 当前状态表示为node,是一个长度为n-1的数字,表示最后n-1位数字。
  • 在状态的末尾添加一个k进制数字x,形成一个新的n位序列。

去重和记忆化:

  • 通过set<int> seen,记录所有已经访问过的状态,确保每个状态只被访问一次。
  • 通过nei % highset,取出新状态的高n-1位部分,如此递归,直到所有状态都被遍历。

字符串拼接:

  • 在递归过程中,每当成功生成了一个新的状态,就将对应的x,即当前状态后添加的数字,转化为字符,并将其添加到最终答案字符串中。
  • 最后追加n-1'0',表示起点,因为Hierholzer算法求的路径是逆序的。
class Solution {
public:string crackSafe(int n, int k) {int highset = pow(10, n - 1);set<int> seen;string ans;auto dfs = [&](auto dfs, int node) -> void {for (int x = 0; x < k; x++) {int nei = node * 10 + x;if (!seen.count(nei)) {seen.insert(nei);dfs(dfs, nei % highset);ans += x + '0';}}};dfs(dfs, 0);ans += string(n - 1, '0');return ans;}
};

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com