首頁(yè)目錄 點(diǎn)擊查看
第一題
- 難度：中等
- 題目： 17. 電話號(hào)碼的字母組合
解題思路
-
這道題也是需要使用回溯法來(lái)解決，窮盡所有可能。借用大佬笨豬爆破組的圖解：
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. 括號(hào)生成
數(shù)字 n 代表生成括號(hào)的對(duì)數(shù)，請(qǐng)你設(shè)計(jì)一個(gè)函數(shù)，用于能夠生成所有可能的并且 有效的 括號(hào)組合。
示例：
輸入：n = 3
輸出：[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
解題思路
-
判斷回溯很簡(jiǎn)單，拿到一個(gè)問(wèn)題，你感覺(jué)如果不窮舉一下就沒(méi)法知道答案，那就可以開(kāi)始回溯了。
借用題解中大佬們的圖
image.png
右邊的括號(hào)大于左邊括號(hào)，就要加入右邊括號(hào)，左邊括號(hào)的數(shù)量不能大于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. 解數(shù)獨(dú)
編寫(xiě)一個(gè)程序，通過(guò)填充空格來(lái)解決數(shù)獨(dú)問(wèn)題。
一個(gè)數(shù)獨(dú)的解法需遵循如下規(guī)則： - 數(shù)字 1-9 在每一行只能出現(xiàn)一次。
- 數(shù)字 1-9 在每一列只能出現(xiàn)一次。
-
數(shù)字 1-9 在每一個(gè)以粗實(shí)線分隔的 3x3 宮內(nèi)只能出現(xiàn)一次。
空白格用 '.' 表示。
image.png
一個(gè)數(shù)獨(dú)。
示例
image.png
答案被標(biāo)成紅色。
- 給定的數(shù)獨(dú)序列只包含數(shù)字 1-9 和字符 '.' 。
- 你可以假設(shè)給定的數(shù)獨(dú)只有唯一解。
- 給定數(shù)獨(dú)永遠(yuǎn)是 9x9 形式的。
解題思路
- 這道題是很典型的回溯法的題型，所以也只能用回溯法來(lái)解決，但是我對(duì)于回溯法確實(shí)不是很熟加上這道題本身難度較大，這道題主要參考了大佬的題解。分別創(chuàng)建3個(gè)數(shù)組，用于存放橫向、縱向、單個(gè)9個(gè)小格子的元素，回溯調(diào)用fill方法，如果填寫(xiě)無(wú)沖突返回true,如果沖突則返回false。依次填寫(xiě)每個(gè)格子。
我的答案
/**
* @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 //獲取當(dāng)前處于哪個(gè)小方塊
}
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. 組合總和
給定一個(gè)無(wú)重復(fù)元素的數(shù)組 candidates 和一個(gè)目標(biāo)數(shù) target ，找出 candidates 中所有可以使數(shù)字和為 target 的組合。
candidates 中的數(shù)字可以無(wú)限制重復(fù)被選取。 - 所有數(shù)字（包括 target）都是正整數(shù)。
- 解集不能包含重復(fù)的組合。
示例
輸入：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]
]
解題思路
- 這道題采取回溯法，選出一個(gè)值后，把目標(biāo)值減去選中值，就得到了新的目標(biāo)值，只要數(shù)組中的值小于或者等于新的目標(biāo)值，就可以繼續(xù)執(zhí)行下去，否則則代表路走不通返回重走。
我的答案
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. 組合
給定兩個(gè)整數(shù) n 和 k，返回 1 ... n 中所有可能的 k 個(gè)數(shù)的組合。
示例
輸入: n = 4, k = 2
輸出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
解題思路
- 回溯調(diào)用，依次取數(shù)一個(gè)零時(shí)數(shù)組，當(dāng)數(shù)組長(zhǎng)度===k則推入最后的結(jié)果數(shù)組中，下一次取數(shù)和零時(shí)數(shù)組的元素作比較。
我的答案
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
大神答案
自己寫(xiě)出來(lái)答案后，看了一下結(jié)果實(shí)在是有點(diǎn)慢，所以去看了題解，看了一下別人的答案，還是很有借鑒的地方，因?yàn)槲以趂or循環(huán)這里，每次都需要從1開(kāi)始，其實(shí)很浪費(fèi),像下面的方法就優(yōu)化了for循環(huán)，得以提升速度。
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
給定一個(gè)數(shù)組 candidates 和一個(gè)目標(biāo)數(shù) target ，找出 candidates 中所有可以使數(shù)字和為 target 的組合。
candidates 中的每個(gè)數(shù)字在每個(gè)組合中只能使用一次。 - 所有數(shù)字（包括目標(biāo)數(shù)）都是正整數(shù)。
- 解集不能包含重復(fù)的組合。
示例
輸入: 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]
]
解題思路
- 這道題和上面的第四題很相似只是說(shuō)每一次每一個(gè)數(shù)只能用一次，我這里有兩種方法，一種是用哈希來(lái)存儲(chǔ)當(dāng)前已經(jīng)達(dá)標(biāo)的數(shù)組字符串，一種是在for循環(huán)遍歷時(shí)跳過(guò)相同的數(shù)字。
我的答案
- 哈希去重
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跳過(guò)
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
以上兩者明顯是第二種更好，空間復(fù)雜度也相對(duì)較低
第七題
- 難度：中等
- 題目：46. 全排列
給定一個(gè) 沒(méi)有重復(fù) 數(shù)字的序列，返回其所有可能的全排列。
示例
輸入: [1,2,3]
輸出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
解題思路
- 這道題是典型的回溯法，套用公式即可，只是需要處理數(shù)字是否使用過(guò)，這里用obj暫存使用過(guò)的數(shù)字
我的答案
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
給定一個(gè)可包含重復(fù)數(shù)字的序列，返回所有不重復(fù)的全排列。
示例
輸入: [1,1,2]
輸出:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
解題思路
- 這道題和上一道題很類似，只是說(shuō)數(shù)字會(huì)出現(xiàn)重復(fù)的，而且是亂序的。所以對(duì)于這兩種情況，需要先排序，排完序過(guò)濾掉相同的數(shù)字和使用過(guò)的數(shù)字即可
我的答案
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]) { // 避免產(chǎn)生重復(fù)的排列
continue;
}
if (obj[i]) { // 這個(gè)數(shù)使用過(guò)了，跳過(guò)。
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
給定一個(gè)可能包含重復(fù)元素的整數(shù)數(shù)組 nums，返回該數(shù)組所有可能的子集（冪集）。
說(shuō)明：解集不能包含重復(fù)的子集。
示例
輸入: [1,2,2]
輸出:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
解題思路
- 這道題和78題子集非常相似，只是說(shuō)換成了可能包含重復(fù)元素的nums數(shù)組，這道題解題方法也是一樣的，首先排序，排完序然后按dfs常規(guī)方法來(lái)處理，跳過(guò)相同的數(shù)字即可。
我的答案
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，其中每個(gè)字模上都刻有一個(gè)字母 tiles[i]。返回你可以印出的非空字母序列的數(shù)目。
注意：本題中，每個(gè)活字字模只能使用一次。
示例
輸入："AAB"
輸出：8
解釋：可能的序列為 "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA"。
輸入："AAABBC"
輸出：188
解題思路
- 這道題還是套用回溯模板，值得注意的是，去重的方法，用了哈希去重得方法，性能實(shí)在太差，后來(lái)想著用new Set去重，情況稍微好一點(diǎn)。
但是也不太好，看了題解，看了大神得方法，豁然開(kāi)朗，確實(shí)厲害：
n長(zhǎng)度的字符可以看做是n-1長(zhǎng)度字符和當(dāng)前剩余字符拼接出來(lái)。所以n長(zhǎng)度字符的可能性為n-1長(zhǎng)度的可能性+剩余字符有多少種
所以從長(zhǎng)度1開(kāi)始一直到字符長(zhǎng)度，遞歸即可。這樣的方式占用內(nèi)存小，擊敗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
- 內(nèi)存較小遞歸
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. 順次數(shù)
我們定義「順次數(shù)」為：每一位上的數(shù)字都比前一位上的數(shù)字大 1 的整數(shù)。
請(qǐng)你返回由 [low, high] 范圍內(nèi)所有順次數(shù)組成的 有序 列表（從小到大排序）。
示例
輸出：low = 100, high = 300
輸出：[123,234]
輸出：low = 1000, high = 13000
輸出：[1234,2345,3456,4567,5678,6789,12345]
解題思路
- 這道題我確實(shí)想的太麻煩了，處理了很久都沒(méi)搞好，最后看了別人的題解，??，真的菜，大神的題解，后面補(bǔ)上自己思路得版本
大神的答案
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. 單詞拆分
給定一個(gè)非空字符串 s 和一個(gè)包含非空單詞的列表 wordDict，判定 s 是否可以被空格拆分為一個(gè)或多個(gè)在字典中出現(xiàn)的單詞。 - 拆分時(shí)可以重復(fù)使用字典中的單詞。
- 你可以假設(shè)字典中沒(méi)有重復(fù)的單詞。
示例
輸入: s = "leetcode", wordDict = ["leet", "code"]
輸出: true
解釋: 返回 true 因?yàn)?"leetcode" 可以被拆分成 "leet code"。
輸入: s = "applepenapple", wordDict = ["apple", "pen"]
輸出: true
解釋: 返回 true 因?yàn)?"applepenapple" 可以被拆分成 "apple pen apple"。
注意你可以重復(fù)使用字典中的單詞。
解題思路
- 這道題推薦使用動(dòng)態(tài)規(guī)劃去做，性能更好一些，但是我現(xiàn)在對(duì)于動(dòng)態(tài)規(guī)劃還不是非常熟悉，所以先做一個(gè)回溯版本，之后再出動(dòng)態(tài)規(guī)劃版本。首先把單詞用set存儲(chǔ)，創(chuàng)建一個(gè)數(shù)組用于存放是否存在某個(gè)單詞，從第一個(gè)字符開(kāi)始拆，截取的字符去尋找是否符合情況，如果符合則將位置存起來(lái)，然后繼續(xù)去尋找接下來(lái)的字符。
我的答案
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
