【JavaScript】LeetCode：66-70

文章目录

66 组合总和
67 括号生成
68 单词搜索
69 分割回文串
70 N皇后

66 组合总和

在这里插入图片描述

回溯
sum：当前组合的数字和。
递归终止条件：sum > target。
收集结果条件：sum = target，找到了满足条件的组合。
注意：因为可以重复取数，所以下一次遍历的开始索引startIndex为当前遍历的节点索引i。

javascript">/*** @param {number[]} candidates* @param {number} target* @return {number[][]}*/
var combinationSum = function(candidates, target) {var traversal = function(candidates, target, sum, startIndex){if(sum > target){return;}if(sum == target){res.push(path.slice());return;}for(let i = startIndex; i < candidates.length; i++){sum += candidates[i];path.push(candidates[i]);traversal(candidates, target, sum, i);sum -= candidates[i];path.pop();}};let res = [];let path = [];traversal(candidates, target, 0, 0);return res;
};

67 括号生成

在这里插入图片描述

回溯
left：左括号的数量，right：右括号的数量。
left < right：无效。
收集结果条件：left = right = n，括号都用完了。
当left < n时，添加左括号，进入下一层递归。
当left >= n且left > right时，添加右括号，进入下一层递归。

javascript">/*** @param {number} n* @return {string[]}*/
var generateParenthesis = function(n) {var traversal = function(n, str, left, right){if(left == n && right == n){res.push(str);return;}if(left < n){traversal(n, str + "(", left + 1, right);}if(left > right){traversal(n, str + ")", left, right + 1);}};let res = [];traversal(n, "", 0, 0);return res;
};

68 单词搜索

在这里插入图片描述

回溯、DFS
遍历board中每一个格子，若该格子的字母为word的首字母，则开始进入dfs遍历。
进入dfs后，按照上、右、下、左四个方向遍历。
递归终止条件：找到了word的最后一个字母。
继续递归的条件：横纵坐标不越界、该坐标所在位置之前没有被访问过、该坐标对应的字母 = word中当前index对应的字母。

javascript">/*** @param {character[][]} board* @param {string} word* @return {boolean}*/
var exist = function(board, word) {var dfs = function(board, word, vis, x, y, index){if(index == word.length){return true;}for(let d = 0; d < 4; d++){let x_ = x + dirt[d][0];let y_ = y + dirt[d][1];if(x_ >= 0 && x_ < m && y_ >= 0 && y_ < n && vis[x_][y_] == 0 && word[index] == board[x_][y_]){vis[x_][y_] = 1;if(dfs(board, word, vis, x_, y_, index + 1)){return true;}vis[x_][y_] = 0;}}return false;};let m = board.length;let n = board[0].length;let vis = Array(m).fill(null).map(() => Array(n).fill(0));let dirt = [[1, 0], [0, 1], [-1, 0], [0, -1]];for(let i = 0; i < m; i++){for(let j = 0; j < n; j++){if(word[0] == board[i][j]){vis[i][j] = 1;if(dfs(board, word, vis, i, j, 1)){return true;}vis[i][j] = 0;} }}return false;
};

69 分割回文串

在这里插入图片描述

回溯
startIndex：从0开始，表示切割线。
判断当前切割的子串（ [ startIndex, i ] ）是否是回文字符串：双指针法，一前一后两个指针向中间移动。
递归终止条件：切割线到str最后了。
下一次递归的切割点：当前遍历字母的索引i + 1。

javascript">var isValid = function(str){let start = 0;let end = str.length - 1;while(start < end){if(str.charAt(start) != str.charAt(end)){return false;}start++;end--;}return true;
};/*** @param {string} s* @return {string[][]}*/
var partition = function(s) {var traversal = function(s, startIndex){if(startIndex == s.length){res.push(path.slice());return;}for(let i = startIndex; i < s.length; i++){let tmp = s.slice(startIndex, i + 1);if(isValid(tmp)){path.push(tmp);traversal(s, i + 1);path.pop();}}}let res = [];let path = [];traversal(s, 0);return res;
};

70 N皇后

在这里插入图片描述

回溯
row：遍历的行数，i：遍历的列数。
递归结束条件：最后一行放置完Q了，注意收集数组时应该转为字符串形式。

javascript">var isValid = function(chessboard, row, col, n){for (let i = 0; i < row; i++) {for (let j = 0; j < n; j++) {if (chessboard[i][j] == 'Q' && (j == col || Math.abs(i - row) == Math.abs(j - col))) {return false;}}}return true;
}/*** @param {number} n* @return {string[][]}*/
var solveNQueens = function(n) {var traversal = function(chessboard, row, n){if(row == n){let tmp = chessboard.slice()for (let i = 0; i < n; i++) {tmp[i] = tmp[i].join(''); }res.push(tmp);return;}for(let i = 0; i < n; i++){if(isValid(chessboard, row, i, n)){chessboard[row][i] = 'Q';traversal(chessboard, row + 1, n);chessboard[row][i] = '.';}}};let res = [];let chessboard = Array(n).fill(null).map(() => Array(n).fill('.'));traversal(chessboard, 0, n);return res;
};