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

2024-02-29 21:52

本文主要是介绍【数学】【深度优先搜索】【图论】【欧拉环路】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 <= 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$\rightarrow 10 则以 110 结尾。最后一条边是 11 10 则以110结尾。 最后一条边是 11 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

相关下载

想高屋建瓴的学习算法,请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

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

测试环境

操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。

这篇关于【数学】【深度优先搜索】【图论】【欧拉环路】753. 破解保险箱的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/760222

相关文章

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

hdu1240、hdu1253(三维搜索题)

1、从后往前输入,(x,y,z); 2、从下往上输入,(y , z, x); 3、从左往右输入,(z,x,y); hdu1240代码如下: #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#inc

hdu1180(广搜+优先队列)

此题要求最少到达目标点T的最短时间,所以我选择了广度优先搜索,并且要用到优先队列。 另外此题注意点较多,比如说可以在某个点停留,我wa了好多两次,就是因为忽略了这一点,然后参考了大神的思想,然后经过反复修改才AC的 这是我的代码 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<

uva 10014 Simple calculations(数学推导)

直接按照题意来推导最后的结果就行了。 开始的时候只做到了第一个推导,第二次没有继续下去。 代码: #include<stdio.h>int main(){int T, n, i;double a, aa, sum, temp, ans;scanf("%d", &T);while(T--){scanf("%d", &n);scanf("%lf", &first);scanf

uva 10025 The ? 1 ? 2 ? ... ? n = k problem(数学)

题意是    ?  1  ?  2  ?  ...  ?  n = k 式子中给k,? 处可以填 + 也可以填 - ,问最小满足条件的n。 e.g k = 12  - 1 + 2 + 3 + 4 + 5 + 6 - 7 = 12 with n = 7。 先给证明,令 S(n) = 1 + 2 + 3 + 4 + 5 + .... + n 暴搜n,搜出当 S(n) >=

uva 11044 Searching for Nessy(小学数学)

题意是给出一个n*m的格子,求出里面有多少个不重合的九宫格。 (rows / 3) * (columns / 3) K.o 代码: #include <stdio.h>int main(){int ncase;scanf("%d", &ncase);while (ncase--){int rows, columns;scanf("%d%d", &rows, &col

【生成模型系列(初级)】嵌入(Embedding)方程——自然语言处理的数学灵魂【通俗理解】

【通俗理解】嵌入(Embedding)方程——自然语言处理的数学灵魂 关键词提炼 #嵌入方程 #自然语言处理 #词向量 #机器学习 #神经网络 #向量空间模型 #Siri #Google翻译 #AlexNet 第一节:嵌入方程的类比与核心概念【尽可能通俗】 嵌入方程可以被看作是自然语言处理中的“翻译机”,它将文本中的单词或短语转换成计算机能够理解的数学形式,即向量。 正如翻译机将一种语言

uva 1342 欧拉定理(计算几何模板)

题意: 给几个点,把这几个点用直线连起来,求这些直线把平面分成了几个。 解析: 欧拉定理: 顶点数 + 面数 - 边数= 2。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#inc

poj 3190 优先队列+贪心

题意: 有n头牛,分别给他们挤奶的时间。 然后每头牛挤奶的时候都要在一个stall里面,并且每个stall每次只能占用一头牛。 问最少需要多少个stall,并输出每头牛所在的stall。 e.g 样例: INPUT: 51 102 43 65 84 7 OUTPUT: 412324 HINT: Explanation of the s

poj 2431 poj 3253 优先队列的运用

poj 2431: 题意: 一条路起点为0, 终点为l。 卡车初始时在0点,并且有p升油,假设油箱无限大。 给n个加油站,每个加油站距离终点 l 距离为 x[i],可以加的油量为fuel[i]。 问最少加几次油可以到达终点,若不能到达,输出-1。 解析: 《挑战程序设计竞赛》: “在卡车开往终点的途中,只有在加油站才可以加油。但是,如果认为“在到达加油站i时,就获得了一