Java实现 LeetCode 753 破解保险箱（递归）

本是古典何须时尚 2023-07-26 05:38 15阅读 0赞

## 753. 破解保险箱 ##

有一个需要密码才能打开的保险箱。密码是 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。

PS：  
该说不说，百度翻译都比这个强

class Solution { 
       public static final int[] MASK = { 0, 1, 10, 100, 1000};
        public String crackSafe(int n, int k) { 
            M = MASK[n];
            StringBuilder sb = new StringBuilder();
            Hierholzer(0, k, new BitSet(), sb);
            for (int i = 0; i < n - 1; i++) sb.append(0);
            return sb.toString();
        }
    
        public int M;
        public void Hierholzer(int n, int k, BitSet bs, StringBuilder sb) { 
            bs.set(n);
            int tail = n % 10;
            n = (n % M) * 10;
            for (int i = 0; i < k; i++, n++) { 
                if (!bs.get(n)) Hierholzer(n, k, bs, sb);
            }
            sb.append(tail);
        }
     
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，15人围观）

还没有评论，来说两句吧...

相关阅读

相关 Java实现 LeetCode 753 破解保险箱（递归）

753. 破解保险箱有一个需要密码才能打开的保险箱。密码是 n 位数, 密码的每一位是 k 位序列 0, 1, …, k-1 中的一个。你可以随意输入密码，保险箱

本是古典何须时尚/ 2023年07月26日 05:38/ 0 赞/ 16 阅读

相关 Java实现 LeetCode 690 员工的重要性（简易递归）

690. 员工的重要性给定一个保存员工信息的数据结构，它包含了员工唯一的id，重要度和直系下属的id。比如，员工1是员工2的领导，员工2是员工3的领导。他们相应

旧城等待，/ 2023年07月22日 09:29/ 0 赞/ 59 阅读

相关 Java实现 LeetCode 679 24 点游戏（递归）

679. 24 点游戏你有 4 张写有 1 到 9 数字的牌。你需要判断是否能通过 \，/，+，-，(，) 的运算得到 24。示例 1: 输入: \[4, 1,

短命女/ 2023年07月22日 03:57/ 0 赞/ 20 阅读

相关 LeetCode——树：递归

LeetCode——树：递归 -------------------- 目录 1. 概述 2. 树的高度（LeetCode104） 3. 平衡树（LeetC

冷不防/ 2023年07月05日 13:10/ 0 赞/ 103 阅读

相关 java基础——递归法破解密码

package string; import java.util.Arrays; public class TestString {

待我称王封你为后i/ 2023年06月27日 03:53/ 0 赞/ 27 阅读

相关 java 递归尾递归_java8使用lambda实现Java的尾递归

原标题：java8使用lambda实现Java的尾递归前言本篇介绍的不是什么新知识，而是对前面讲解的一些知识的综合运用。众所周知，递归是解决复杂问题的一个很有效的方式，

╰+哭是因爲堅強的太久メ/ 2022年11月05日 11:55/ 0 赞/ 325 阅读

相关【leetcode】递归练习总结

一、总结 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmN

爱被打了一巴掌/ 2022年10月17日 04:18/ 0 赞/ 238 阅读

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

There is a box protected by a password. The password is n digits, where each letter can

╰+攻爆jí腚メ/ 2022年06月03日 10:16/ 0 赞/ 123 阅读

相关 java实现递归

什么是递归递归，简单的理解就是自己调用自己；主要分为两部分，——递归头，（递归的结束条件），——递归体，（自己调用自己的过程）常见递归算法（1）最常见的就是

短命女/ 2022年05月28日 10:48/ 0 赞/ 237 阅读

相关 leetcode - 递归

目录 98.验证搜索二叉树 22.括号生成 100.相同的树 101.对称二叉树 104.树的最大深度 108.将有序数组转换成搜索二叉树 110.平衡二叉树

快来打我*/ 2022年03月07日 00:38/ 0 赞/ 245 阅读