本文涉及知识点
数学 深度优先搜索 图论 欧拉环路
LeetCode753. 破解保险箱
有一个需要密码才能打开的保险箱。密码是 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
分析
令S是某n-1位[0,k)组成的字符串。所有的S都是节点，则每个S都有k条出边，分别连向：S.Right(n-2)+0 S.Right(n-2)+1 ⋯ \cdots⋯ S.Right(n-2)+k-1;k条入边，分别连向0+S.Right(n-2) 1+S.Right(n-2) ⋯ \cdots⋯ k-1+S.Right(n-2)。
比如：n为3，k为3
12的出边：20 21 22
12的入边：01 11 21
n =3,k=2的所有边。
每条边都至少经过一次，由于是欧拉回路，所有可以所有边都只经过一次。
最后一条边是11$\rightarrow10 则以 110 结尾。最后一条边是 11 10 则以110结尾。 最后一条边是 1110则以110结尾。最后一条边是11\rightarrow$11 则以111结尾。
由于是欧拉回路，任意起点任意方向的边数一样。我们以字典顺序最小的为起点，访问字典顺序最小的边。箭头上面是最后n个字符。
代码
核心代码
class Solution { public: string crackSafe(int n, int k) { if (1 == n) { for (int i = 0; i < k; i++) { m_strRet += '0' + i; } return m_strRet; } m_iK = k; int iMask = 1; for (int i = 1; i < n; i++) { iMask *= k; } vector<std::queue<int>> vNeiBo(iMask); for (int i = 0; i < iMask; i++) { int pre = i % (iMask / k); for (int j = 0; j < k; j++) { vNeiBo[i].emplace(pre * k + j); } } DFS(vNeiBo, 0); m_strRet += string(n - 2, '0'); //DFS时，已经加了一个零 return string(m_strRet.rbegin(),m_strRet.rend()); } void DFS(vector<std::queue<int>>& vNeiBo, int cur) { while (vNeiBo[cur].size()) { const auto next = vNeiBo[cur].front(); vNeiBo[cur].pop(); DFS(vNeiBo,next); } m_strRet += '0' + cur % m_iK; } int m_iK; string m_strRet; };
测试用例
template<class T,class T2> void Assert(const T& t1, const T2& t2) { assert(t1 == t2); } template<class T> void Assert(const vector<T>& v1, const vector<T>& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { Assert(v1[i], v2[i]); } } int main() { int n ,k; { Solution sln; n = 2, k = 2; auto res = sln.crackSafe(n, k); Assert(strlen("01100"), res.length()); } { Solution sln; n = 1, k = 2; auto res = sln.crackSafe(n, k); Assert(strlen("10"), res.length()); } { Solution sln; n = 3, k = 2; auto res = sln.crackSafe(n, k); Assert(strlen("0011101000"), res.length()); } { Solution sln; n = 2, k = 3; auto res = sln.crackSafe(n, k); Assert(strlen("0221120100"), res.length()); } }
2023年4月
class Solution { public: void dfs(int node) { for (int i = 0; i < m_iK; i++) { const int iLine = node * 10 + i; if (m_setHasDo.count(iLine)) { continue; } m_setHasDo.emplace(iLine); dfs(iLine% m_iRange); m_strRet += i + ‘0’; } }
string crackSafe(int n, int k) { m_iRange = pow(10, n - 1); m_iK = k; dfs(0); m_strRet += string(n - 1, '0'); return m_strRet; }
private: unordered_set m_setHasDo; string m_strRet; int m_iRange; int m_iK; };
2024年7月
class Solution { public: string crackSafe(int n, int k) { string str; if (1 == n) { for (int i = 0; i < k; i++) { str += (i + ‘0’); } return str; } m_iNodeNum = 1; for (int i = 1; i < n; i++) { m_iNodeNum *= k; } m_vNeiB.resize(m_iNodeNum); for (int i = 0; i < m_iNodeNum; i++) { for (int j = 0; j < k; j++) { m_vNeiB[i].emplace((i * k + j) % m_iNodeNum); } } dfs(0); string strRet(n - 1, ‘0’); for (int i = m_vRevVisitNode.size() - 2; i >= 0; i–) { strRet += m_vRevVisitNode[i]%k + ‘0’; } return strRet; } void dfs(int cur) { while (m_vNeiB[cur].size()) { int first = *m_vNeiB[cur].begin(); m_vNeiB[cur].erase(first); dfs(first); } m_vRevVisitNode.emplace_back(cur); } int m_iNodeNum; vector<std::unordered_set> m_vNeiB; vector m_vRevVisitNode; };
2024年8月
class Solution { public: string crackSafe(int n, int k) { if (1 == n) { vector vRet; for (int i = 0; i < k; i++) { vRet.emplace_back(i + ‘0’); } vRet.emplace_back(0); return vRet.data(); } m_iK = k; const int iNodeNum = pow(k, n - 1); m_vNeiBo.resize(iNodeNum); for (int i = 0; i < iNodeNum; i++) { for (int j = 0; j < k; j++) { m_vNeiBo[i].emplace((i * k + j)%iNodeNum); } } dfs(0); m_vRet.pop_back(); for (int i = 0; i+1 < n; i++) { m_vRet.emplace_back(‘0’); } std::reverse(m_vRet.begin(), m_vRet.end()); m_vRet.emplace_back(0); return m_vRet.data(); } void dfs(int cur) { auto& curSet = m_vNeiBo[cur]; while (curSet.size()) { const int next = *curSet.begin(); curSet.erase(next); dfs(next); } m_vRet.emplace_back(cur%m_iK+‘0’); } int m_iK; vector<set> m_vNeiBo; vector m_vRet; };
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 我想对大家说的话 |
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
