【JavaScript】LeetCode:66-70

发布于:2024-10-17 ⋅ 阅读:(49) ⋅ 点赞:(0)

66 组合总和

在这里插入图片描述

  • 回溯
  • sum:当前组合的数字和。
  • 递归终止条件:sum > target。
  • 收集结果条件:sum = target,找到了满足条件的组合。
  • 注意:因为可以重复取数,所以下一次遍历的开始索引startIndex为当前遍历的节点索引i。
/**
 * @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时,添加右括号,进入下一层递归。
/**
 * @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对应的字母。
/**
 * @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。
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了,注意收集数组时应该转为字符串形式。
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;
};