跳到主要内容

1 篇博文 含有标签「欧拉回路」

查看所有标签

· 阅读需 6 分钟

1、题干​

有一个需要密码才能打开的保险箱。密码是 n 位数, 密码的每一位都是范围 [0, k - 1] 中的一个数字。

保险箱有一种特殊的密码校验方法，你可以随意输入密码序列，保险箱会自动记住 最后 n 位输入 ，如果匹配，则能够打开保险箱。

  • 例如，正确的密码是 "345" ，并且你输入的是 "012345" ：
    • 输入 0 之后，最后 3 位输入是 "0" ，不正确。
    • 输入 1 之后，最后 3 位输入是 "01" ，不正确。
    • 输入 2 之后，最后 3 位输入是 "012" ，不正确。
    • 输入 3 之后，最后 3 位输入是 "123" ，不正确。
    • 输入 4 之后，最后 3 位输入是 "234" ，不正确。
    • 输入 5 之后，最后 3 位输入是 "345" ，正确，打开保险箱。

在只知道密码位数 n 和范围边界 k 的前提下，请你找出并返回确保在输入的 某个时刻 能够打开保险箱的任一 最短 密码序列 。

 

示例 1：

输入：n = 1, k = 2
输出："10"
解释：密码只有 1 位，所以输入每一位就可以。"01" 也能够确保打开保险箱。

示例 2：

输入：n = 2, k = 2
输出："01100"
解释：对于每种可能的密码：
- "00" 从第 4 位开始输入。
- "01" 从第 1 位开始输入。
- "10" 从第 3 位开始输入。
- "11" 从第 2 位开始输入。
因此 "01100" 可以确保打开保险箱。"01100"、"10011" 和 "11001" 也可以确保打开保险箱。

 

提示：

  • 1 <= n <= 4
  • 1 <= k <= 10
  • 1 <= kn <= 4096

2、思路1​

  • 题意

题目要找一个能打开保险箱的最短字符串，实际是想找一个所有密码组合而成的最短字符串，该字符串的特征是：截取其中任意长度为 n 的字符串都是保险箱的密码。

  • 思路

先找出所有密码串，再用所有密码串组合出最短字符串。

找出所有密码时要注意，任一密码串长度都为 n，每一位的取值范围是 [0,k−1][0,k-1]。

组合最短字符串时要注意，在组合任意两个密码串 a 和 b 时，必须满足 a 剔除首位字符后与 b 剔除末位字符后相等。举个例子：

  • 012 与 123 可以组合，因为 012 剔除首位后与 123 剔除末位后都是 12
  • 012 与 213 则不能组合
  • 代码主要逻辑：
    • 先找出所有可能的密码串 pwds
    • 将所有密码串按前缀分组存入哈希表 pwdMap，前缀指的是剔除密码末位字符之后的字符串
    • 使用回溯组合所有密码串
    • 所有密码串都用完则顺序拼接并返回

3、代码​

function crackSafe(n: number, k: number): string {
    if (k === 1) return '0'.padStart(n, '0');

    // 生成pwds
    const pwds = new Array(k ** n).fill('0').map((v, i) => {
        return k < 2 ? v : i.toString(k).padStart(n, "0");
    });

    if (n === 1) return pwds.join('');

    const pwdMap = new Map();
    for (const p of pwds) {
        const prefix = p.slice(0, n - 1);
        if (!pwdMap.has(prefix)) pwdMap.set(prefix, []);
        pwdMap.get(prefix).push(p);
    }

    // 组合pwds
    let ans = '';
    function dfs(cur: string, used: Set<string>) {
        if (ans) return;
        if (used.size === pwds.length) {
            const nums = [...used];
            ans = nums[0] + nums.slice(1).map(w => w.slice(-1)).join('');
            return;
        }

        const nums = pwdMap.get(cur.slice(1));
        for (const n of nums) {
            if (used.has(n)) continue;
            used.add(n);
            dfs(n, used);
            used.delete(n);
        }
    }

    for (const p of pwds) dfs(p, new Set([p]));

    return ans;
}

4、复杂度​

  • 时间复杂度：O(k∗k2n)O(k*k^{2n})
  • 空间复杂度：O(k∗k2n)O(k*k^{2n})

5、执行结果​

image.png

6、思路2​

这是思路1的优化版，时间复杂度更低。主要是猜测以任意密码开头都有可能找到最短字符串，因此枚举时只取第一个密码作为起点构造字符串。代码的不同表现在倒数第二行，移除了遍历，只取第一个密码 pwds[0] 进行回溯。

7、代码​

function crackSafe(n: number, k: number): string {
    if (k === 1) return '0'.padStart(n, '0');

    // 生成pwds
    const pwds = new Array(k ** n).fill('0').map((v, i) => {
        return k < 2 ? v : i.toString(k).padStart(n, "0");
    });

    if (n === 1) return pwds.join('');

    const pwdMap = new Map();
    for (const p of pwds) {
        const prefix = p.slice(0, n - 1);
        if (!pwdMap.has(prefix)) pwdMap.set(prefix, []);
        pwdMap.get(prefix).push(p);
    }

    // 组合pwds
    let ans = '';
    function dfs(cur: string, used: Set<string>) {
        if (ans) return;
        if (used.size === pwds.length) {
            const nums = [...used];
            ans = nums[0] + nums.slice(1).map(w => w.slice(-1)).join('');
            return;
        }

        const nums = pwdMap.get(cur.slice(1));
        for (const n of nums) {
            if (used.has(n)) continue;
            used.add(n);
            dfs(n, used);
            used.delete(n);
        }
    }

    dfs(pwds[0], new Set([pwds[0]]));

    return ans;
}

8、复杂度​

  • 时间复杂度：O(k∗kn)O(k*k^n)
  • 空间复杂度：O(k∗kn)O(k*k^n)

9、执行结果​

image.png