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 次浏览

启动您的 职业生涯

通过完成课程获得认证

开始
广告