Day 30 | 51.N 皇后

Leetcode 51.N 皇后

题目：https://leetcode.cn/problems/n-queens/

代码

var solveNQueens = function (n) {
    // 判断位置是否合法
    function isValid (row, col, chessBoard, n) {
        // 检查列
        for (let i = 0; i < row; i ++){
            if (chessBoard[i][col] === 'Q') {
                return false
            }
        }
        // 检查45度角
        for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--){
            if (chessBoard[i][j] === 'Q') {
                return false
            }
        }
        // 检查135度角
        for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++){
            if (chessBoard[i][j] === 'Q') {
                return false
            }
        }
        return true
    }
    // 把二维数组转换为一维数组
    function transformChessBoard (chessBoard) {
        let chessBoardBack = []
        chessBoard.forEach(row => {
            let rowStr = ''
            row.forEach(value => {
                rowStr += value
            })
            chessBoardBack.push(rowStr)
        })
        return chessBoardBack
    }
    let res = []
    const backtracking = (row, chessBoard) => {
        // 如果到了最后一行，说明可以收集结果
        if (row === n) {
            res.push(transformChessBoard(chessBoard))
            return
        }
        for (let col = 0; col < n; col++){
            if (isValid(row, col, chessBoard, n)) {
                // 放置皇后
                chessBoard[row][col] = 'Q'
                backtracking(row + 1, chessBoard)
                // 回溯，撤销皇后
                chessBoard[row][col] = '.'
            }
        }
    }
    // 申请一个nxn的数组，用.填充
    let chessBoard = new Array(n).fill([]).map(() => new Array(n).fill('.'))
    backtracking(0, chessBoard)
    return res
};

感想