数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++ 中的安全破解
假设我们有一个用密码保护的箱子。密码是由 n 位数字组成的序列，每位数字可以是前 k 个数字 0, 1, ..., k-1 中的一个。因此，当我们输入密码时，最后输入的 n 位数字将自动与正确的密码进行匹配。
例如，假设正确的密码是“563”，如果我们输入“285639”，则箱子将打开，因为正确的密码与输入密码的后缀匹配。我们必须找到任何保证在某个时刻打开箱子的最小长度密码。
当输入为 n = 2，k = 2 时，结果可以是“01100”、“00110”、“10011”、“11001”中的任何一个。
为了解决这个问题，我们将遵循以下步骤：
- 定义一个名为 visited 的集合
- 定义一个函数 dfs()，它将接收 s、k 作为参数。
- 从 i := 0 开始，当 i < k 时，更新（i 加 1），执行：
- temp := s 与 i 拼接成字符串
- 如果 visited 中不存在 temp，则：
- 将 temp 插入 visited
- temp := 获取 temp 从索引 1 到结尾的子字符串
- dfs(temp, k)
- ret := ret 与 i 拼接成字符串
- 在主方法中，执行以下操作：
- 如果 n 等于 1 且 k 等于 1，则：
- 返回 "0"
- ret := 空字符串，s := 空字符串
- 从 i := 0 开始，当 i < n - 1 时，更新（i 加 1），执行：
- s := s 与 "0" 拼接
- dfs(s, k)
- 从 i := 0 开始，当 i < n - 1 时，更新（i 加 1），执行：
- ret := ret 与 "0" 拼接
- 返回 ret
让我们看看下面的实现以更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
set <string> visited;
string ret;
string crackSafe(int n, int k) {
if(n == 1 && k == 1) return "0";
ret = "";
string s = "";
for(int i = 0; i < n - 1; i++){
s += "0";
}
dfs(s, k);
for(int i = 0; i < n - 1; i++) ret += "0";
return ret;
}
void dfs(string s, int k) {
string temp;
for(int i = 0; i < k; i++){
temp = s + to_string(i);
if(!visited.count(temp)){
visited.insert(temp);
temp = temp.substr(1);
dfs(temp, k);
ret += to_string(i);
}
}
}
};
main(){
Solution ob;
cout << (ob.crackSafe(2,2));
}输入
2 2
输出
01100
更新于：2020年6月2日
290 次浏览
广告