【数学】【深度优先搜索】【图论】【欧拉环路】753. 破解保险箱

作者推荐

动态规划的时间复杂度优化

本文涉及知识点

数学深度优先搜索图论欧拉环路

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 <= kⁿ <= 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$\rightarrow $10 则以 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

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛