算法day30|复习

30 第七章 回溯算法

• 332.重新安排行程

• 51. N皇后

• 37. 解数独

• 总结

详细布置

今天这三道题都非常难，那么这么难的题，为啥一天做三道？

因为 一刷 也不求大家能把这么难的问题解决，所以 大家一刷的时候，就了解一下题目的要求，了解一下解题思路，不求能直接写出代码，先大概熟悉一下这些题，二刷的时候，随着对回溯算法的深入理解，再去解决如下三题。

大家今天的任务，其实是 对回溯算法章节做一个总结就行。

重点是看 回溯算法总结篇：

代码随想录

332.重新安排行程（可跳过）

代码随想录

51. N皇后（可跳过）

var solveNQueens = function(n) {
    let result = []
    const isValid = function(chessboard,row,col,n){
        // col
        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<n;i--,j++){
            if(chessboard[i][j]=== 'Q'){
                return false
            }
        }
        // 135
        for(let i = row-1,j=col-1;i>=0&&j>=0;i--,j--){
            if(chessboard[i][j]==='Q'){
                return false
            }
        }
        return true
    }
    const transform = function(chessboard){
        let result = []
        chessboard.forEach(row=>{
            let rowStr = ''
            row.forEach(value=>{
                rowStr += value
            })
            result.push(rowStr)
        })
        return result
 
    }
    const backtracking = function(chessboard,row){
        // when end?
        if(row === n){
            // 需要转换
            result.push(transform(chessboard))
            return
        }
        for(let col = 0;col<n;col++){
            if(isValid(chessboard,row,col,n)){
                chessboard[row][col] = 'Q'
                backtracking(chessboard,row+1)
                chessboard[row][col] ='.'
            }
 
        }
    }
    let chessboard = new Array(n).fill([]).map(()=>(new Array(n).fill('.')))
    backtracking(chessboard,0)
    return result
    
};

代码随想录

视频讲解：这就是传说中的N皇后？ 回溯算法安排！| LeetCode：51.N皇后_哔哩哔哩_bilibili

37. 解数独（可跳过）

代码随想录

视频讲解：回溯算法二维递归？解数独不过如此！| LeetCode：37. 解数独_哔哩哔哩_bilibili

var solveSudoku = function (board) {
    const isValid = function (board, k, row, col) {
        // row
        for (let i = 0; i < board.length; i++) {
            if (i!== col && board[row][i] === k) {
                return false
            }
        }
        // col
        for (let i = 0; i < board.length; i++) {
            if (i!== row && board[i][col] === k) {
                return false
            }
        }
        //九方格
        let x = Math.floor(row / 3) * 3
        let y = Math.floor(col / 3) * 3
        for (let i = x; i < x + 3; i++) {
            for (let j = y; j < y + 3; j++) {
                if (i!== row && j!= col && board[i][j] === k) {
                    return false
                }
 
            }
        }
        return true
    }
    const backtracking = function () {
        for (let row = 0; row < board.length; row++) {
            for (let col = 0; col < board[0].length; col++) {
                if (board[row][col] === '.') {
                    for (let k = 1; k < 10; k++) {
                        if (isValid(board, `${k}`, row, col)) {
                            board[row][col] = `${k}`
                            if (backtracking()) { return true }
                            board[row][col] = '.'
                        }
                    }
                    return false
                }
            }
        }
        return true
    }
    backtracking()
    return board
 
};

总结

代码随想录