跳到主要内容

17 篇博文 含有标签「回溯」

查看所有标签

· 阅读需 2 分钟

1、题干​

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

 

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

输入：n = 1
输出：["()"]

 

提示：

  • 1 <= n <= 8

2、解题思路​

总体思路是：从 n-1 推导出 n 的组合情况，只需要遍历 n-1 的所有组合，并在所有组合的每个位置填入一对括号 () 并去重即可。


3、举个例子​

  • n=1时，组合情况仅一种：["()"]
  • n=2时
    • 遍历 n=1 的组合情况 ["()"]
    • 对于情况 "()"，在该字符串每个位置填入一对括号 () 后得到：["()()","(())","()()"]
    • 去重得到最终组合情况为：["()()","(())"]
  • n=3时
    • 遍历 n=2 的组合情况 ["()()","(())"]
    • 对于情况 "()()"，在每个位置填入一对括号 () 后得到：["()()()","(())()","()()()","()(())","()()()"]
    • 对于情况 "(())"，在每个位置填入一对括号 () 后得到：["()(())","(()())","((()))","(()())","(())()"]
    • 去重得到最终组合情况为：["()()()","(())()","()(())","(()())","((()))"]

4、代码​

var generateParenthesis = function (n) {
    let set = new Set(['()']);
    for (let c = 2; c <= n; c++) {
        let nextSet = new Set();
        for (const s of set) {
            for (let j = 0; j <= s.length; j++) {
                nextSet.add(s.slice(0, j) + '()' + s.slice(j));
            }
        }
        set = nextSet;
    }
    return [...set];
};

5、执行结果​

image.png

· 阅读需 2 分钟

1、题干​

正整数 n 代表生成括号的对数，请设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

 

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

输入：n = 1
输出：["()"]

 

提示：

  • 1 <= n <= 8

 

注意：本题与主站 22 题相同： https://leetcode-cn.com/problems/generate-parentheses/

2、解题思路​

总体思路是：从 n-1 推导出 n 的组合情况，只需要遍历 n-1 的所有组合，并在所有组合的每个位置填入一对括号 () 并去重即可。


3、举个例子​

  • n=1时，组合情况仅一种：["()"]
  • n=2时
    • 遍历 n=1 的组合情况 ["()"]
    • 对于情况 "()"，在该字符串每个位置填入一对括号 () 后得到：["()()","(())","()()"]
    • 去重得到最终组合情况为：["()()","(())"]
  • n=3时
    • 遍历 n=2 的组合情况 ["()()","(())"]
    • 对于情况 "()()"，在每个位置填入一对括号 () 后得到：["()()()","(())()","()()()","()(())","()()()"]
    • 对于情况 "(())"，在每个位置填入一对括号 () 后得到：["()(())","(()())","((()))","(()())","(())()"]
    • 去重得到最终组合情况为：["()()()","(())()","()(())","(()())","((()))"]

4、代码​

var generateParenthesis = function (n) {
    let set = new Set(['()']);
    for (let c = 2; c <= n; c++) {
        let nextSet = new Set();
        for (const s of set) {
            for (let j = 0; j <= s.length; j++) {
                nextSet.add(s.slice(0, j) + '()' + s.slice(j));
            }
        }
        set = nextSet;
    }
    return [...set];
};

5、执行结果​

image.png

· 阅读需 2 分钟

1、题干​

正整数 n 代表生成括号的对数，请设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

 

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

输入：n = 1
输出：["()"]

 

提示：

  • 1 <= n <= 8

 

注意：本题与主站 22 题相同： https://leetcode-cn.com/problems/generate-parentheses/

2、解题思路​

总体思路是：从 n-1 推导出 n 的组合情况，只需要遍历 n-1 的所有组合，并在所有组合的每个位置填入一对括号 () 并去重即可。


3、举个例子​

  • n=1时，组合情况仅一种：["()"]
  • n=2时
    • 遍历 n=1 的组合情况 ["()"]
    • 对于情况 "()"，在该字符串每个位置填入一对括号 () 后得到：["()()","(())","()()"]
    • 去重得到最终组合情况为：["()()","(())"]
  • n=3时
    • 遍历 n=2 的组合情况 ["()()","(())"]
    • 对于情况 "()()"，在每个位置填入一对括号 () 后得到：["()()()","(())()","()()()","()(())","()()()"]
    • 对于情况 "(())"，在每个位置填入一对括号 () 后得到：["()(())","(()())","((()))","(()())","(())()"]
    • 去重得到最终组合情况为：["()()()","(())()","()(())","(()())","((()))"]

4、代码​

var generateParenthesis = function (n) {
    let set = new Set(['()']);
    for (let c = 2; c <= n; c++) {
        let nextSet = new Set();
        for (const s of set) {
            for (let j = 0; j <= s.length; j++) {
                nextSet.add(s.slice(0, j) + '()' + s.slice(j));
            }
        }
        set = nextSet;
    }
    return [...set];
};

5、执行结果​

image.png

· 阅读需 5 分钟

1、题干​

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能从 s 获得的 有效 IP 地址 。你可以按任何顺序返回答案。

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。

 

示例 1：

输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]

示例 2：

输入：s = "0000"
输出：["0.0.0.0"]

示例 3：

输入：s = "1111"
输出：["1.1.1.1"]

示例 4：

输入：s = "010010"
输出：["0.10.0.10","0.100.1.0"]

示例 5：

输入：s = "10203040"
输出：["10.20.30.40","102.0.30.40","10.203.0.40"]

 

提示：

  • 0 <= s.length <= 3000
  • s 仅由数字组成

 

注意：本题与主站 93 题相同：https://leetcode-cn.com/problems/restore-ip-addresses/ 

2、解法1-嵌套循环​

三层嵌套循环确定 IP 地址的4个子串，并检验其合法性


3、代码​

var restoreIpAddresses = function (s) {
    const n = s.length;
    const valid = (str) => !((str.length > 1 && str[0] === '0') || +str > 255);

    const res = [];
    for (let i = 1; i < 4; i++) {
        if (n - i < 3 || n - i > 9) continue;
        for (let j = i + 1; j < i + 4; j++) {
            if (n - j < 2 || n - j > 6) continue;
            for (let k = j + 1; k < j + 4; k++) {
                if (n - k < 1 || n - k > 3) continue;
                const s1 = s.slice(0, i), s2 = s.slice(i, j);
                const s3 = s.slice(j, k), s4 = s.slice(k);
                if (valid(s1) && valid(s2) && valid(s3) && valid(s4)) res.push(`${s1}.${s2}.${s3}.${s4}`);
            }
        }
    }

    return res;
};

代码中的校验可以简化，但遍历次数会增加

var restoreIpAddresses = function (s) {
    const valid = (str) => !(str.length < 1 || str.length > 3 || (str.length > 1 && str[0] === '0') || +str > 255);

    const res = [];
    for (let i = 1; i < 4; i++) {
        for (let j = i + 1; j < i + 4; j++) {
            for (let k = j + 1; k < j + 4; k++) {
                const s1 = s.slice(0, i), s2 = s.slice(i, j);
                const s3 = s.slice(j, k), s4 = s.slice(k);
                if (valid(s1) && valid(s2) && valid(s3) && valid(s4)) res.push(`${s1}.${s2}.${s3}.${s4}`);
            }
        }
    }

    return res;
};

4、执行结果​

image.png


5、解法2-回溯​

使用回溯算法，在字符串 s 中选取3个索引作为选择路径（idxArr），其中索引值用于将字符串 s 分割成4个 IP 子串，以子串长度作为选择列表。

注意

  • 选择列表（子串长度）只有 1、2、3 三种选择
  • 为了代码简洁性，每次递归都传入不同引用的选择路径（idxArr），这样可以省略撤销操作，但是消耗的内存会偏多

6、代码​

var restoreIpAddresses = function (s) {
    const n = s.length;
    const valid = (str) => !((str.length > 1 && str[0] === '0') || +str > 255);

    const res = [];
    function backtrace(idxArr) {
        const ln = idxArr.length, li = idxArr[ln - 1] || 0;

        if (n - li < 4 - ln || n - li > 3 * (4 - ln)) return;
        if (ln === 3) {
            const s1 = s.slice(0, idxArr[0]), s2 = s.slice(idxArr[0], idxArr[1]);
            const s3 = s.slice(idxArr[1], idxArr[2]), s4 = s.slice(idxArr[2]);
            if (valid(s1) && valid(s2) && valid(s3) && valid(s4)) res.push(`${s1}.${s2}.${s3}.${s4}`);
            return;
        }

        for (let i = 1; i <= 3; i++) backtrace([...idxArr, li + i]);
    }

    return backtrace([]), res;
};

7、执行结果​

  • 执行用时: 68 ms
  • 内存消耗: 43.4 MB

· 阅读需 5 分钟

1、题干​

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能从 s 获得的 有效 IP 地址 。你可以按任何顺序返回答案。

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。

 

示例 1：

输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]

示例 2：

输入：s = "0000"
输出：["0.0.0.0"]

示例 3：

输入：s = "1111"
输出：["1.1.1.1"]

示例 4：

输入：s = "010010"
输出：["0.10.0.10","0.100.1.0"]

示例 5：

输入：s = "10203040"
输出：["10.20.30.40","102.0.30.40","10.203.0.40"]

 

提示：

  • 0 <= s.length <= 3000
  • s 仅由数字组成

 

注意：本题与主站 93 题相同：https://leetcode-cn.com/problems/restore-ip-addresses/ 

2、解法1-嵌套循环​

三层嵌套循环确定 IP 地址的4个子串，并检验其合法性


3、代码​

var restoreIpAddresses = function (s) {
    const n = s.length;
    const valid = (str) => !((str.length > 1 && str[0] === '0') || +str > 255);

    const res = [];
    for (let i = 1; i < 4; i++) {
        if (n - i < 3 || n - i > 9) continue;
        for (let j = i + 1; j < i + 4; j++) {
            if (n - j < 2 || n - j > 6) continue;
            for (let k = j + 1; k < j + 4; k++) {
                if (n - k < 1 || n - k > 3) continue;
                const s1 = s.slice(0, i), s2 = s.slice(i, j);
                const s3 = s.slice(j, k), s4 = s.slice(k);
                if (valid(s1) && valid(s2) && valid(s3) && valid(s4)) res.push(`${s1}.${s2}.${s3}.${s4}`);
            }
        }
    }

    return res;
};

代码中的校验可以简化，但遍历次数会增加

var restoreIpAddresses = function (s) {
    const valid = (str) => !(str.length < 1 || str.length > 3 || (str.length > 1 && str[0] === '0') || +str > 255);

    const res = [];
    for (let i = 1; i < 4; i++) {
        for (let j = i + 1; j < i + 4; j++) {
            for (let k = j + 1; k < j + 4; k++) {
                const s1 = s.slice(0, i), s2 = s.slice(i, j);
                const s3 = s.slice(j, k), s4 = s.slice(k);
                if (valid(s1) && valid(s2) && valid(s3) && valid(s4)) res.push(`${s1}.${s2}.${s3}.${s4}`);
            }
        }
    }

    return res;
};

4、执行结果​

image.png


5、解法2-回溯​

使用回溯算法，在字符串 s 中选取3个索引作为选择路径（idxArr），其中索引值用于将字符串 s 分割成4个 IP 子串，以子串长度作为选择列表。

注意

  • 选择列表（子串长度）只有 1、2、3 三种选择
  • 为了代码简洁性，每次递归都传入不同引用的选择路径（idxArr），这样可以省略撤销操作，但是消耗的内存会偏多

6、代码​

var restoreIpAddresses = function (s) {
    const n = s.length;
    const valid = (str) => !((str.length > 1 && str[0] === '0') || +str > 255);

    const res = [];
    function backtrace(idxArr) {
        const ln = idxArr.length, li = idxArr[ln - 1] || 0;

        if (n - li < 4 - ln || n - li > 3 * (4 - ln)) return;
        if (ln === 3) {
            const s1 = s.slice(0, idxArr[0]), s2 = s.slice(idxArr[0], idxArr[1]);
            const s3 = s.slice(idxArr[1], idxArr[2]), s4 = s.slice(idxArr[2]);
            if (valid(s1) && valid(s2) && valid(s3) && valid(s4)) res.push(`${s1}.${s2}.${s3}.${s4}`);
            return;
        }

        for (let i = 1; i <= 3; i++) backtrace([...idxArr, li + i]);
    }

    return backtrace([]), res;
};

7、执行结果​

  • 执行用时: 68 ms
  • 内存消耗: 43.4 MB

· 阅读需 7 分钟

1、题干​

累加数 是一个字符串，组成它的数字可以形成累加序列。

一个有效的 累加序列 必须 至少 包含 3 个数。除了最开始的两个数以外，序列中的每个后续数字必须是它之前两个数字之和。

给你一个只包含数字 '0'-'9' 的字符串，编写一个算法来判断给定输入是否是 累加数 。如果是，返回 true ；否则，返回 false 。

说明：累加序列里的数，除数字 0 之外，不会 以 0 开头，所以不会出现 1, 2, 03 或者 1, 02, 3 的情况。

 

示例 1：

输入："112358"
输出：true 
解释：累加序列为: 1, 1, 2, 3, 5, 8 。1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8

示例 2：

输入："199100199"
输出：true 
解释：累加序列为: 1, 99, 100, 199。1 + 99 = 100, 99 + 100 = 199

 

提示：

  • 1 <= num.length <= 35
  • num 仅由数字（0 - 9）组成

 

进阶：你计划如何处理由过大的整数输入导致的溢出?

2、解法1-回溯​

总体思路：使用回溯对所有可能性进行匹配直到成功。大体步骤如下：

  • 使用递归实现回溯算法，递归函数match，参数l、m、r分别表示待匹配的3个数的起始位置
  • match函数第一步先处理边界情况、0开头的特殊情况
  • 第二步从num字符串中取出前两个数并求和，得到第三个数n3
  • 第三步剪枝，如果剩余字符比要查找的结果更短，直接返回false
  • 第四步在剩余字符串中查找n3是否存在，若存在且正好用尽所有字符则返回true
  • 若不存在则尝试r右移一位以及m右移一位的情况

注意点

  • 测试用例中不存在大整数，因此没有做大整数特殊处理
  • 边界条件、特殊情况略多，如果不能AC可以多调试看看是否边界没处理好
  • 一定要剪枝，否则大概率会超时

3、代码​

var isAdditiveNumber = function (num) {
    function match(l, m, r) {
        // 处理边界情况、特殊情况（0开头的数）
        if (r > num.length || m > num.length - 1 || (num[l] === '0' && m - l > 1)) return false;
        if (m >= r) return match(l, m, r + 1);
        if (num[m] === '0' && r - m > 1) return match(l, m + 1, r);

        const n3 = `${+num.slice(l, m) + +num.slice(m, r)}`;
        // 剪枝：如果剩余字符比要查找的结果更短，直接返回false
        if (n3.length > num.length - r) return false;
        // 匹配成功 🚀🚀🚀
        if (num.slice(r, r + n3.length) === n3 && (r + n3.length === num.length || match(m, r, r + n3.length))) return true;

        // 匹配失败：尝试查找其他可能性
        return match(l, m, r + 1) || match(l, m + 1, r);
    }
    return match(0, 1, 2);
};

4、执行结果​

执行用时: 108 ms 内存消耗: 44.7 MB


5、解法1-优化版​

  • 问题1：确定开头两个数字之后（num.slice(r, r + n3.length) === n3）的后续匹配方式存在无效遍历，原先使用递归进行后续匹配，每次右移1位，因此存在大量无效匹配。
  • 问题2：已遍历过的情况没有直接跳过，导致存在大量重复遍历。
  • 优化1：确定开头两个数字之后，由于后面的数字是前面累加而来，因此后面的数字都是确定的，可以直接使用while循环匹配累加和。
  • 优化2：使用哈希表记录已遍历过的情况，后续直接跳过这些情况，进行记忆化搜索。（感谢评论区 @Jvaeyhcd 的提醒）

在用例"1991000199299498797"中遍历次数从解法1的15000+次降到99次。


6、代码​

var isAdditiveNumber = function (num) {
    const set = new Set();

    function match(l, m, r) {
        if (set.has(`${l}-${m}-${r}`)) return false;
        set.add(`${l}-${m}-${r}`);
        if (r > num.length || m > num.length - 1 || (num[l] === '0' && m - l > 1)) return false;
        if (r - m > num.length - r || m - l > num.length - r) return false;

        if (m >= r) return match(l, m, r + 1);
        if (num[m] === '0' && r - m > 1) return match(l, m + 1, r);

        let r2 = r, n1 = +num.slice(l, m), n2 = +num.slice(m, r), n3 = n1 + n2;
        while (num.slice(r2, r2 + `${n3}`.length) === `${n3}`) {
            (r2 = r2 + `${n3}`.length), (n1 = n2), (n2 = n3), (n3 = n1 + n2);
        }
        if (r2 === num.length) return true;

        return match(l, m, r + 1) || match(l, m + 1, r);
    }
    return match(0, 1, 2);
};

7、执行结果​

执行用时: 68 ms 内存消耗: 38.1 MB


8、解法2-双指针遍历​

总体思路：双层遍历确定开头两个数字之后，由于后面的数字是前面累加而来，因此后面的数字都是确定的，可以直接使用while循环匹配累加和。

在用例"1991000199299498797"中遍历次数从解法1的15000+次降到120次。


9、代码​

var isAdditiveNumber = function (num) {
    for (let m = 1; m < num.length; m++) {
        let n1 = +num.slice(0, m);
        if (num[0] === '0' && m > 1) return false;

        for (let r = m + 1; r < num.length; r++) {
            if (num[m] === '0' && r - m > 1) break;
            let n2 = +num.slice(m, r), r_2 = r, n_1 = n1, n3 = n1 + n2;
            while (num.slice(r_2, r_2 + `${n3}`.length) === `${n3}`) {
                (r_2 = r_2 + `${n3}`.length), (n_1 = n2), (n2 = n3), (n3 = n_1 + n2);
            }
            if (r_2 === num.length) return true;
        }
    }

    return false;
};

10、执行结果​

执行用时: 60 ms 内存消耗: 38.1 MB

1.png

· 阅读需 4 分钟

1、题干​

n 位格雷码序列 是一个由 2n 个整数组成的序列，其中：
  • 每个整数都在范围 [0, 2n - 1] 内（含 0 和 2n - 1）
  • 第一个整数是 0
  • 一个整数在序列中出现 不超过一次
  • 每对 相邻 整数的二进制表示 恰好一位不同 ，且
  • 第一个 和 最后一个 整数的二进制表示 恰好一位不同

给你一个整数 n ，返回任一有效的 n 位格雷码序列 。

 

示例 1：

输入：n = 2
输出：[0,1,3,2]
解释：
[0,1,3,2] 的二进制表示是 [00,01,11,10] 。
- 00 和 01 有一位不同
- 01 和 11 有一位不同
- 11 和 10 有一位不同
- 10 和 00 有一位不同
[0,2,3,1] 也是一个有效的格雷码序列，其二进制表示是 [00,10,11,01] 。
- 00 和 10 有一位不同
- 10 和 11 有一位不同
- 11 和 01 有一位不同
- 01 和 00 有一位不同

示例 2：

输入：n = 1
输出：[0,1]

 

提示：

  • 1 <= n <= 16

格雷编码的生成方式有3种，直接计算、镜像对称构造、交替构造；可惜我一个都没推出来，这里做个简单记录。

2、直接计算​

直接计算的公式是：G(n)=n⊕n2G(n) = n \oplus \dfrac{n}{2}。其中 G(n)G(n) 表示第 nn 个格雷码。

该解法对应官解2

3、代码​

var grayCode = function(n) {
    const ret = [];
    for (let i = 0; i < 1 << n; i++) {
        ret.push((i >> 1) ^ i);
    }
    return ret;
};

4、镜像对称构造​

  • 将前2k个格雷码去除首位二进制数并分成两半后具有镜像对称性。（如下图3位格雷码）
  • n位格雷码是将n-1位格雷码作为前半部分，将n-1位格雷码倒序遍历并在其二进制数之前添1作为后半部分。（如下图3位格雷码与2位格雷码关系）

image.png

该解法对应官解1

5、代码​

var grayCode = function (n) {
    const arr = [0, 1];
    for (let i = 2; i <= n; i++) {
        for (let j = arr.length - 1; j > -1; j--) {
            arr.push(arr[j] | (1 << (i - 1)));
        }
    }
    return arr;
};

6、交替构造​

以3位格雷码为例：

  • 从 n = 0 开始，按以下2步反复操作，即可得到所有格雷码
  • n 为偶数：翻转最低位得到下一个格雷码，如 000 变成 001
  • n 为奇数：把最右边的 1 左边的位翻转得到下一个格雷码，如 001 变成 011

实现略复杂，暂无代码，建议优先使用前2种方法生成