leetCode之回溯法

首页目录 点击查看

第一题

解题思路

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


    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

第十一题

  • 难度：中等
  • 题目：#### 139. 单词拆分
    给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
  • 拆分时可以重复使用字典中的单词。
  • 你可以假设字典中没有重复的单词。

示例

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
     注意你可以重复使用字典中的单词。

解题思路

  • 这道题推荐使用动态规划去做，性能更好一些，但是我现在对于动态规划还不是非常熟悉，所以先做一个回溯版本，之后再出动态规划版本。首先把单词用set存储，创建一个数组用于存放是否存在某个单词，从第一个字符开始拆，截取的字符去寻找是否符合情况，如果符合则将位置存起来，然后继续去寻找接下来的字符。

我的答案

var wordBreak = function (s, wordDict) {
    let wordList = new Set(wordDict);
    let len = s.length;
    let hasWord = new Array(len);
    function dfs(start) {
        if (start == len) return true;
        if (hasWord[start] !== undefined) return hasWord[start];
        for (let i = start + 1; i <= len; i++) {
            let word = s.slice(start, i);
            if (wordList.has(word) && dfs(i)) {
                hasWord[i] = true
                return true
            }

        }
        hasWord[start] = false
        return false
    }
    return dfs(0)
};
image.png
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 204,684评论 6赞 478
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 87,143评论 2赞 381
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 151,214评论 0赞 337
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,788评论 1赞 277
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,796评论 5赞 368
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,665评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 38,027评论 3赞 399
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,679评论 0赞 258
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 41,346评论 1赞 299
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,664评论 2赞 321
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,766评论 1赞 331
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,412评论 4赞 321
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 39,015评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,974评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,203评论 1赞 260
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 45,073评论 2赞 350
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,501评论 2赞 343