leetcode 753. Cracking the Safe 全排列获取保险箱密码+深度优先遍历DFS + 贪心策略

There is a box protected by a password. The password is n digits, where each letter can be one of the first k digits 0, 1, …, k-1.

You can keep inputting the password, the password will automatically be matched against the last n digits entered.

For example, assuming the password is “345”, I can open it when I type “012345”, but I enter a total of 6 digits.

Please return any string of minimum length that is guaranteed to open the box after the entire string is inputted.

Example 1:
Input: n = 1, k = 2
Output: “01”
Note: “10” will be accepted too.
Example 2:
Input: n = 2, k = 2
Output: “00110”
Note: “01100”, “10011”, “11001” will be accepted too.
Note:
n will be in the range [1, 4].
k will be in the range [1, 10].
k^n will be at most 4096.

这道题说的是给了k个数字，值为0到k-1，让我们组成n位密码。我们可以发现，为了尽可能的使钥匙串变短，所以我们的密码之间尽可能要相互重叠，比如00和01，就共享一个0，如果是3个数，012和120共享两个数”12”，那么我们可以发现，两个长度为n的密码最好能共享n-1个数字，这样累加出来的钥匙串肯定是最短的。

密码共有n位，每一个位可以有k个数字，那么总共不同的密码总数就有k的n次方个。我们的思路是先从n位都是0的密码开始，取出钥匙串的最后n个数字，然后将最后一个数字依次换成其他数字，我们用一个HashSet来记录所有遍历过的密码，这样如果不在集合中，说明是一个新密码，而生成这个新密码也只是多加了一个数字，这样能保证我们的钥匙串最短，这是一种贪婪的解法，相当的巧妙，参见代码如下：

代码如下：

#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <stack>
#include <string>
#include <climits>
#include <algorithm>
#include <sstream>
#include <functional>
#include <bitset>
#include <numeric>
#include <cmath>
#include <regex>
#include <iomanip>
#include <cstdlib>
#include <ctime>
#include <array>
using namespace std;
class Solution
{
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 753. Cracking the Safe 全排列获取保险箱密码+深度优先遍历DFS + 贪心策略的全部内容，希望文章能够帮你解决leetcode 753. Cracking the Safe 全排列获取保险箱密码+深度优先遍历DFS + 贪心策略所遇到的程序开发问题。

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