代码随想录算法训练营第30天 | 332.重新安排行程 、51. N皇后、37. 解数独

332.重新安排行程（可跳过）
https://programmercarl.com/0332.重新安排行程.html

有难度，涉及到图，有些用例会超时
/**
 * @param {string[][]} tickets
 * @return {string[]}
 */
var findItinerary = function(tickets) {
    const res = ['JFK'];
    const map = {};
    for (let [from, to] of tickets) {
        if (!map[from]) {
            map[from] = [];
        }
        map[from].push(to);
    }
    for (let key in map) {
        map[key].sort();
    }

    const backtraversing = ()=>{
        if (res.length === tickets.length+1) {
            return true;
        }
        if (!map[res[res.length-1]] || !map[res[res.length-1]].length) {
            return false;
        }

        for (let i=0;i<map[res[res.length-1]].length;i++) {
            let city = map[res[res.length-1]][i];
            map[res[res.length-1]].splice(i,1);
            res.push(city);
            if (backtraversing()) {
                return true;
            }
            res.pop();
            map[res[res.length-1]].splice(i,0,city);

        }
    
    }
    backtraversing();
    return res;
};

51. N皇后（可跳过）
    https://programmercarl.com/0051.N皇后.html
    视频讲解：https://www.bilibili.com/video/BV1Rd4y1c7Bq

能想到思路，但具体的实现有些写不出来
function isVaild(arr, row, col) {
    for (let i = 0; i< row; i++) {
        if (arr[i][col] === 'Q') {
            return false;
        }
    }

    for (let i=row-1,j=col-1;i>=0&&j>=0;i--,j--) {
        if (arr[i][j]==='Q') {
            return false;
        }
    }

    for (let i=row-1,j=col+1;j<arr.length&&i>=0;i--,j++) {
        if (arr[i][j]==='Q') {
            return false;
        }
    }
    return true;
}
/**
 * @param {number} n
 * @return {string[][]}
 */
var solveNQueens = function(n) {
    const res = [];
    const path = [];
    const matrix = new Array(n).fill(0).map(()=>new Array(n).fill('.'));
    const backtraversing = (n, row, matrix) => {
        if (n === row) {
            res.push([...path]);
            return;
        }

        for (let i=0;i<n;i++) {
            if (!isVaild(matrix, row, i)) {
                continue;
            }
            matrix[row][i] = 'Q';
            path.push(matrix[row].join(''));
            backtraversing(n, row+1, matrix);
            matrix[row][i]='.';
            path.pop();
        }
    }
    backtraversing(n, 0, matrix);
    return res;
};

37. 解数独（可跳过）
    https://programmercarl.com/0037.解数独.html
    视频讲解：https://www.bilibili.com/video/BV1TW4y1471V

function isValid(row, col, val, board) {
        let len = board.length
        // 行不能重复
        for(let i = 0; i < len; i++) {
            if(board[row][i] === val) {
                return false
            }
        }
        // 列不能重复
        for(let i = 0; i < len; i++) {
            if(board[i][col] === val) {
                return false
            }
        }
        let startRow = Math.floor(row / 3) * 3
        let startCol = Math.floor(col / 3) * 3

        for(let i = startRow; i < startRow + 3; i++) {
            for(let j = startCol; j < startCol + 3; j++) {
                if(board[i][j] === val) {
                    return false
                }
            }
        }

        return true
    }

/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var solveSudoku = function(board) {
    const back = (board) => {
        let len = board.length;
        for(let row = 0;row<len;row++) {
            for (let col =0;col<len;col++) {
                if (board[row][col]!=='.') continue;
                for (let k=1;k<=9;k++) {
                    let strNum = k+'';
                    if (!isValid(row,col,strNum,board)) continue;
                    board[row][col] = strNum;
                    if (back(board)) return true;
                    board[row][col] = '.';
                }
                return false;
            }
        }
        return true;
    }
    back(board);
    return board;
};

总结
https://programmercarl.com/回溯总结.html