讨论/《春招冲刺班 - 7 天刷题挑战》 - 753. 破解保险箱/
《春招冲刺班 - 7 天刷题挑战》 - 753. 破解保险箱
共 4 个回复

题目描述是不是郑爽的语文老师写的。

7

回溯方法

最短字符串的长度肯定为kn+n1k^n+n-1

初始化一个空字符串
然后每读取一个字符0...k10...k-1就判断末尾长度为n的子串是否前面出现过(可用一个set来记录),如果没有就添加进set然后继续递归回溯,直到set的大小等于n为止,思路很简单。时间复杂度为O(kkn)=O(kn+1)O(k\cdot k^n)=O(k^{n+1})

class Solution {
    public String res = "";

    public void recursive(int n, int k, String str, HashSet<String> set){
        if (!res.isEmpty()) return;
        if (set.size() == Math.pow(k,n)){
            res = str;
        }
        for (int i = 0; i < k; ++i){
            String next = str + i;
            if (next.length() < n){
                recursive(n,k,next,set);
            }else {
                String temp = next.substring(next.length()-n);
                if (!set.contains(temp)){
                    set.add(temp);
                    recursive(n,k,next,set);
                    set.remove(temp);
                }
            }
        }
    }

    public String crackSafe(int n, int k) {
        recursive(n,k,"",new HashSet<>());
        return res;
    }
}
1
class Solution {
public:
    bool st[10010];
    int n, k;
    string ans;
    //每一个点是长度为n - 1的串,每一条边是一个密码
    void dfs(string node, int edge)
    {
        st[edge] = true;
        //获得下一个节点串
        string next = node.substr(1);
        next += edge % 10 + '0';
        for(int i = 0; i < k; i++)
        {
            //如果这条边没有走过则走
            int t = (edge - (node[0] - '0') * pow(10, n - 1)) * 10 + i;
            if(!st[t]) dfs(next, t);
        }   
        ans += edge % 10 + '0';
    }

    string crackSafe(int n, int k) {
        this -> n = n;
        this -> k = k;
        if(n == 1)
        {
            for(int i = 0; i < k; i++) ans += i + '0';
            return ans;
        }
        if(k == 1)
        {
            for(int i = 0; i < n; i++) ans += '0';
            return ans;
        }
        dfs(string(n - 1, '0'), 0);
        //得到的是欧拉回路的倒序,要在最后加上初始节点串
        ans += string(n - 1, '0');
        return ans;
    }
};

参与“7天刷题挑战”的童鞋欢迎点击问卷加入专属社群哦~
2月1日-7日,字节跳动工程师直播刷题等你来围观