LeetCode 破解保险箱 全排列【1】

有一个需要密码才能打开的保险箱。密码是 n 位数, 密码的每一位是 k 位序列 0, 1, ..., k-1 中的一个 。

你可以随意输入密码，保险箱会自动记住最后 n 位输入，如果匹配，则能够打开保险箱。

举个例子，假设密码是 "345"，你可以输入 "012345" 来打开它，只是你输入了 6 个字符.

请返回一个能打开保险箱的最短字符串。

示例1:输入: n = 1, k = 2 输出: "01" 说明: "10"也可以打开保险箱。

示例2:输入: n = 2, k = 2 输出: "00110" 说明: "01100", "10011", "11001" 也能打开保险箱。

提示：

1. n 的范围是 [1, 4]。
2. k 的范围是 [1, 10]。
3. k^n 最大可能为 4096。

思路，1. 数据量比较少，容易处理。

          有点像小m序列一样，构造转移。

class Solution {
public:
string d[4096];
bool vist[4096];
int N;
int cnt=0;
int a[4];
string crackSafe(int n, int k) {
N=n;
if(n==0) return "";
if(n==1)
{
string tt="",t="A";
for(int i=0;i<k;i++)
{
t[0]='0'+i;
tt+=t;
}
return tt;
}
dfs(0,k,a);
memset(vist,0,sizeof(vist));
int sum=pow(k,n);
string res=d[0],scur=res;
vist[0]=true;
for(int i=1;i<sum;i++)
{
string ts=scur.substr(1,n-1);
for(int i=sum-1;i>-1;i--)
{
if(!vist[i]&&d[i].substr(0,n-1)==ts)
{
vist[i]=true;
scur=d[i];
res+=scur.substr(n-1,1);
break;
}
}
}
return res;
}
//得到全部排列
void dfs(int n,int k,int a[])
{
if(n==N)
{
string t="A",tt="";
for(int i=0;i<N;i++)
{
t[0]='0'+a[i];
tt+=t;
}
d[cnt++]=tt;
}
else
for(int i=0;i<k;i++)
{
a[n]=i;
dfs(n+1,k,a);
}
}
};

高效方法

public: string crackSafe(int n, int k)
{
string res = string(n, '0');
unordered_set<string> s;
s.insert(res);
for (int i = 0; i < pow(k, n); i++)
{
string tmp = res.substr(res.length() - n + 1, n - 1);
for (int j = k -1;j >= 0; j--)
{
string key = tmp + to_string(j);
if (s.find(key) == s.end())
{ res += to_string(j);
s.insert(key); break;
}
}
}
return res;
}

最后

以上就是暴躁金鱼为你收集整理的LeetCode 破解保险箱 全排列【1】的全部内容，希望文章能够帮你解决LeetCode 破解保险箱 全排列【1】所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。