leetCode之回溯法

作者: Benzic | 来源:发表于2020-09-24 08:52 被阅读0次

首页目录点击查看

第一题

难度：中等
题目： 17. 电话号码的字母组合

解题思路

这道题也是需要使用回溯法来解决，穷尽所有可能。借用大佬笨猪爆破组的图解：

image.png

我的答案

var letterCombinations = function (digits) {
    if (!digits.length) return []
    let list = {
        "2": "abc",
        "3": "def",
        "4": "ghi",
        "5": "jkl",
        "6": "mno",
        "7": "pqrs",
        "8": "tuv",
        "9": "wxyz"
    }
    let array = [];
    function generate(curStr, i) {
        if (curStr.length === digits.length) {
            array.push(curStr)
            return
        }
        let letters = list[digits[i]];
        if (letters) {
            for (let key of letters) {

                generate(curStr + key, i + 1)
            }
        }

    }
    generate("", 0)
    return array
};

第二题

难度：中等
题目：22. 括号生成
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。
示例：

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

解题思路

判断回溯很简单，拿到一个问题，你感觉如果不穷举一下就没法知道答案，那就可以开始回溯了。
借用题解中大佬们的图

image.png

右边的括号大于左边括号，就要加入右边括号，左边括号的数量不能大于n。

我的答案

var generateParenthesis = function (n) {
    let array = [];
    let str = "";

    function generate(str, left, right) {
        if (str.length === 2 * n) {
            array.push(str)
            return
        }
        if (left > 0) {
            generate(str + "(", left - 1, right)
        }
        if (right > left) {
            generate(str + ")", left, right - 1)
        }
    }
    generate(str, n, n)
    return array
};

image.png

第三题

难度：困难
题目： 37. 解数独
编写一个程序，通过填充空格来解决数独问题。
一个数独的解法需遵循如下规则：
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用 '.' 表示。

image.png

一个数独。

示例

image.png

答案被标成红色。
- 给定的数独序列只包含数字 1-9 和字符 '.' 。
- 你可以假设给定的数独只有唯一解。
- 给定数独永远是 9x9 形式的。

解题思路

这道题是很典型的回溯法的题型，所以也只能用回溯法来解决，但是我对于回溯法确实不是很熟加上这道题本身难度较大，这道题主要参考了大佬的题解。分别创建3个数组，用于存放横向、纵向、单个9个小格子的元素，回溯调用fill方法，如果填写无冲突返回true,如果冲突则返回false。依次填写每个格子。

我的答案

/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var solveSudoku = function (board) {
    const rows = new Array(9);
    const cols = new Array(9);
    const blocks = new Array(9);
    const options = ['1', '2', '3', '4', '5', '6', '7', '8', '9'];
    for (let i = 0; i < 9; i++) {
        rows[i] = new Set(options)
        cols[i] = new Set(options)
        blocks[i] = new Set(options)
    }
    function getBlocksIndex(i, j) {
        return (i / 3 | 0) * 3 + j / 3 | 0        //获取当前处于哪个小方块
    }
    for (let i = 0; i < 9; i++) {
        for (let j = 0; j < 9; j++) {
            if (board[i][j] !== '.') {
                rows[i].delete(board[i][j]);
                cols[j].delete(board[i][j]);
                blocks[getBlocksIndex(i, j)].delete(board[i][j])
            }
        }
    }

    function fill(i, j) {
        if (j === 9) {
            i++
            j = 0
            if (i === 9) {
                return true
            }
        }
        if (board[i][j] !== '.') {
            return fill(i, j + 1)
        }
        const blockIndex = getBlocksIndex(i, j);
        for (let num = 0; num < 9; num++) {
            const option = options[num];
            if (!rows[i].has(option) || !cols[j].has(option) || !blocks[blockIndex].has(option)) {
                continue
            }
            board[i][j] = option;
            rows[i].delete(option)
            cols[j].delete(option)
            blocks[blockIndex].delete(option)
            
            if (fill(i, j + 1)) {
                return true
            }
            board[i][j] = ".";
            rows[i].add(option)
            cols[j].add(option)
            blocks[blockIndex].add(option)
        }
        return false
    }

    fill(0, 0)
    return board
};

image.png

第四题

难度：中等
题目：39. 组合总和
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
所有数字（包括 target）都是正整数。
解集不能包含重复的组合。

示例

输入：candidates = [2,3,6,7], target = 7,
所求解集为：
[
  [7],
  [2,2,3]
]
输入：candidates = [2,3,5], target = 8,
所求解集为：
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

解题思路

这道题采取回溯法，选出一个值后，把目标值减去选中值，就得到了新的目标值，只要数组中的值小于或者等于新的目标值，就可以继续执行下去，否则则代表路走不通返回重走。

我的答案

var combinationSum = function (candidates, target) {
    let arr = [];
    function dfs(value, array) {
        if (value === 0) return arr.push(array.slice());
        if (value < 0) return;
        for (let i = 0; i <= candidates.length - 1; i++) {
            if (!array.length || (array[array.length - 1] >= candidates[i])) {
                let temp = value - candidates[i];
                array.push(candidates[i]);
                dfs(temp, array);
                array.pop()
            }
        }
    }
    dfs(target, [])
    return arr
};

image.png

第五题

难度：中等
题目：77. 组合
给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。

示例

输入: n = 4, k = 2
输出:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

解题思路

回溯调用，依次取数一个零时数组，当数组长度===k则推入最后的结果数组中，下一次取数和零时数组的元素作比较。

我的答案

        var combine = function (n, k) {
            let arr = [];

            function dfs(array) {
                if (array.length === k) return arr.push(array.slice());
                for (let i = 1; i <= n; i++) {
                    if (!array.length || array[array.length - 1] > i) {
                        array.push(i);
                        dfs(array);
                        array.pop()
                    }
                }
            }
            dfs([]);
            return arr
        };

image.png

大神答案

自己写出来答案后，看了一下结果实在是有点慢，所以去看了题解，看了一下别人的答案，还是很有借鉴的地方，因为我在for循环这里，每次都需要从1开始，其实很浪费,像下面的方法就优化了for循环，得以提升速度。

var combine = function (n, k) {
    let arr = [];
    function dfs(start, array) {
        if (array.length === k) return arr.push(array.slice());
        for (let i = start; i <= n; i++) {
            array.push(i);
            dfs(i + 1, array);
            array.pop()
        }
    }
    dfs(1, []);
    return arr
};

image.png

第六题

难度：中等
题目：40. 组合总和 II
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
所有数字（包括目标数）都是正整数。
解集不能包含重复的组合。

示例

输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
  [1,2,2],
  [5]
]

解题思路

这道题和上面的第四题很相似只是说每一次每一个数只能用一次，我这里有两种方法，一种是用哈希来存储当前已经达标的数组字符串，一种是在for循环遍历时跳过相同的数字。

我的答案

哈希去重

        var combinationSum2 = function (candidates, target) {
            candidates = candidates.sort((a, b) => {
                return a - b
            })
            let arr = [];
            let obj = {}

            function dfs(target, index, array) {
                if (target === 0 && !obj[array.toString()]) {
                    obj[array.toString()] = true
                    return arr.push(array.slice())
                };
                if (target < 0) return;
                for (let i = index; i <= candidates.length - 1; i++) {
                    let temp = target - candidates[i];
                    array.push(candidates[i]);
                    dfs(temp, i + 1, array);
                    array.pop();
                }
            }
            dfs(target, 0, [])
            return arr
        };

image.png

continue跳过

        var combinationSum2 = function (candidates, target) {
            candidates = candidates.sort((a, b) => {
                return a - b
            })
            let arr = [];

            function dfs(target, index, array) {
                if (target === 0) {
                    return arr.push(array.slice())
                };
                if (target < 0) return;
                for (let i = index; i <= candidates.length - 1; i++) {
                    if (candidates[i - 1] == candidates[i] && i - 1 >= index) continue;
                    let temp = target - candidates[i];
                    array.push(candidates[i]);
                    dfs(temp, i + 1, array);
                    array.pop();
                }
            }
            dfs(target, 0, [])
            return arr
        };

image.png

以上两者明显是第二种更好，空间复杂度也相对较低

第七题

难度：中等
题目：46. 全排列
给定一个没有重复数字的序列，返回其所有可能的全排列。

示例

输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

解题思路

这道题是典型的回溯法，套用公式即可，只是需要处理数字是否使用过，这里用obj暂存使用过的数字

我的答案

var permute = function (nums) {
    let arr = [];
    let obj = {}
    function dfs(array) {
        if (array.length === nums.length) return arr.push(array.slice());
        if (array.length > nums.length) return;
        for (let i = 0; i <= nums.length - 1; i++) {
            if (!obj[i]) {
                obj[i] = true
                array.push(nums[i]);
                dfs(array);
                obj[i] = false
                array.pop()
            }
        }
    }
    dfs([])
    return arr
};

image.png

第八题

难度：中等
题目：47. 全排列 II
给定一个可包含重复数字的序列，返回所有不重复的全排列。

示例

输入: [1,1,2]
输出:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

解题思路

这道题和上一道题很类似，只是说数字会出现重复的，而且是乱序的。所以对于这两种情况，需要先排序，排完序过滤掉相同的数字和使用过的数字即可

我的答案

var permuteUnique = function (nums) {
    let arr = new Set();
    let obj = {}
    nums.sort((a, b) => a - b); // 升序排序
    function dfs(array, index) {
        if (array.length === nums.length) return arr.add(array.slice())
        if (array.length > nums.length) return
        for (let i = 0; i <= nums.length - 1; i++) {
            if (nums[i - 1] === nums[i] && i - 1 >= 0 && !obj[i - 1]) { // 避免产生重复的排列
                continue;
            }
            if (obj[i]) {      // 这个数使用过了，跳过。
                continue;
            }
            array.push(nums[i]);
            obj[i] = true
            dfs(array, i + 1);
            array.pop()
            obj[i] = false
        }
    }
    dfs([], 0)
    return [...arr]
};

image.png

第九题

难度：中等
题目：90. 子集 II
给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。

示例

输入: [1,2,2]
输出:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

解题思路

这道题和78题子集非常相似，只是说换成了可能包含重复元素的nums数组，这道题解题方法也是一样的，首先排序，排完序然后按dfs常规方法来处理，跳过相同的数字即可。

我的答案

var subsetsWithDup = function (nums) {
    let arr = [];
    nums.sort((a, b) => {
        return a - b
    });

    function dfs(index, array) {
        arr.push(array.slice());
        for (let i = index; i <= nums.length - 1; i++) {
            if (nums[i - 1] === nums[i] && i - 1 >= index) continue;
            array.push(nums[i]);
            dfs(i + 1, array);
            array.pop()
        }
    }
    dfs(0, [])
    return arr
};

image.png

第十题

难度：中等
题目：1079. 活字印刷
你有一套活字字模 tiles，其中每个字模上都刻有一个字母 tiles[i]。返回你可以印出的非空字母序列的数目。
注意：本题中，每个活字字模只能使用一次。

示例

输入："AAB"
输出：8
解释：可能的序列为 "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA"。

输入："AAABBC"
输出：188

解题思路

这道题还是套用回溯模板，值得注意的是，去重的方法，用了哈希去重得方法，性能实在太差，后来想着用new Set去重，情况稍微好一点。
但是也不太好，看了题解，看了大神得方法，豁然开朗，确实厉害：
n长度的字符可以看做是n-1长度字符和当前剩余字符拼接出来。所以n长度字符的可能性为n-1长度的可能性+剩余字符有多少种
所以从长度1开始一直到字符长度，递归即可。这样的方式占用内存小，击败100%

我的答案

new Set去重

        var numTilePossibilities = function (tiles) {
            let obj = {}
            let arr = new Set()

            function dfs(path) {
                if (path.length) {
                    arr.add(path)
                }
                for (let i = 0; i <= tiles.length - 1; i++) {
                    if (!obj[i]) {
                        obj[i] = true
                        path += tiles[i]
                        dfs(path);
                        obj[i] = false
                        path = path.slice(0, path.length - 1)
                    }
                }
            }
            dfs("")
            return arr.size
        };

image.png

内存较小递归

        var numTilePossibilities = function (tiles) {
            let sum = 0;

            function cal(list, n) {
                let ns = Array.from(new Set(Array.from(list)));
                sum += ns.length;
                for (let i = 0, l = ns.length; i < l; i++) {
                    if (n > 1) { 
                        cal(list.replace(ns[i], ''), n - 1);
                    }
                }
            }
            cal(tiles, tiles.length);
            return sum;
        };

image.png

第十一题

难度：中等
题目：1291. 顺次数
我们定义「顺次数」为：每一位上的数字都比前一位上的数字大 1 的整数。
请你返回由 [low, high] 范围内所有顺次数组成的有序列表（从小到大排序）。

示例

输出：low = 100, high = 300
输出：[123,234]

输出：low = 1000, high = 13000
输出：[1234,2345,3456,4567,5678,6789,12345]

解题思路

这道题我确实想的太麻烦了，处理了很久都没搞好，最后看了别人的题解，😔，真的菜，大神的题解，后面补上自己思路得版本

大神的答案

var sequentialDigits = function(low, high) {
    let ans = [];
    for (i = 1; i <= 9; i++) {
        backtrack(low, high, i, i);
    }
    ans.sort((a, b) => a-b)
    return ans;
    function backtrack (low, high, curNum, curTail) {
        if(curNum >= low && curNum <= high) {
            ans.push(curNum)
        }
        if(curNum > high) {
            return;
        }
        if(curTail + 1 <= 9) {
            backtrack(low, high, curNum*10 + curTail + 1, curTail + 1);
        }
    }
};

image.png

leetCode之回溯法

首页目录 点击查看

第一题

解题思路

我的答案

第二题

解题思路

我的答案

第三题

示例

解题思路

我的答案

第四题

示例

解题思路

我的答案

第五题

示例

解题思路

我的答案

大神答案

第六题

示例

解题思路

我的答案

第七题

示例

解题思路

我的答案

第八题

示例

解题思路

我的答案

第九题

示例

解题思路

我的答案

第十题

示例

解题思路

我的答案

第十一题

示例

解题思路

大神的答案

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

首页目录点击查看