leetCode之回溯法
2020-09-24 本文已影响0人
Benzic
首页目录 点击查看
第一题
- 难度：中等
- 题目： 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
