百元做网站,外国人做中国数学视频网站,建站中心,华为展厅设计方案文章目录1. 题目2. 解题1. 题目
有一个需要密码才能打开的保险箱。 密码是 n 位数, 密码的每一位是 k 位序列 0, 1, …, k-1 中的一个 。
你可以随意输入密码#xff0c;保险箱会自动记住最后 n 位输入#xff0c;如果匹配#xff0c;则能够打开保险箱。
举个例子#x…
文章目录1. 题目2. 解题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 也能打开保险箱。提示
n 的范围是 [1, 4]。
k 的范围是 [1, 10]。
k^n 最大可能为 4096。来源力扣LeetCode 链接https://leetcode-cn.com/problems/cracking-the-safe 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
class Solution {int kind;unordered_setint s;string ans;vectorint unit {0, 1, 10, 100, 1000};
public:string crackSafe(int n, int k) {kind pow(k, n);//有多少种密码string temp(n, 0);//第一种全零的temp.reserve(10000);s.insert(0);dfs(temp, 0, n, k);return ans;}void dfs(string temp, int num, int n, int k) {if(ans ! )return;if(s.size() kind){ans temp;//找到一种答案return;}int newnum;for(int i 0; i k; i){newnum num - unit[n]*(temp[temp.size()-n]-0);temp char(0i);newnum newnum*10 i;if(!s.count(newnum)){s.insert(newnum);dfs(temp, newnum, n, k);s.erase(newnum);}temp.pop_back();}}
};56 ms 11.2 MB C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
