LeetCode《初级算法》数组之有效的数独

题目

题解

1、暴力解法

使用中规中矩的方法，根据规则，先对数独的行进行检验，然后再对数独的列进行检验，最后对数独的 3×3 分区进行检验；

/**
 * @param {character[][]} board
 * @return {boolean}
 */
var isValidSudoku = function(board) {

    const rowLen = board[0].length;
    const columnLen = board.length;

    // 对行进行检验
    for( row of board) {
        
        // 这里注意是 row-1，要不然 i+1 会越界
        for( let i = 0;i < rowLen - 1;i++) {
            if( row[i] !== '.') {
                const isExistence = row.indexOf(row[i],i+1);
                if(isExistence !== -1) {
                    return false; 
                }
            }
        }
    }


    // 对列进行检验
    for( let i = 0 ;i < rowLen;i++) {

        for(let j = 0;j < columnLen-1;j++) {
        
            let temp = board[j][i];
            if( temp !== '.') {

                for(let n = j + 1;n < columnLen;n++) {

                    if( board[n][i] === temp) {
                        return false;
                    }
                }
            }

        }
    }
        

    // 函数，对  3x3 分区进行检验 i 为开始行，i+2 为结束行，m 为开始列，m+2 为结束列
    const isSudokuof3x3 = function (arr,i,m) {

        let arr1 = arr[i].slice(m,m+3);
        let arr2 = arr[i+1].slice(m,m+3);
        let arr3 = arr[i+2].slice(m,m+3);

        for(let item of arr1) {
            if( item !== '.') {
                if( arr2.indexOf(item) !== -1) {

                    return false;
                }
                if(arr3.indexOf(item) !== -1 ) {

                    return false;
                }
            }
        }

        for(let item of arr2) {

            if( item !== '.') {

                if(arr3.indexOf(item) !== (-1)) {

                    return false;
                }
            }
        }
    }

    for(let i = 0;i < 3;i++) {

        for(let j = 0;j < 3;j++) {
            // 注意这里要对这个自定义函数的返回值进行判断
            if( isSudokuof3x3(board,i*3,j*3) === false) {
                return false;
            }
            
        }
    }

    return true;
};

复制代码

2、对暴力解法的改进

在一次遍历中就检验完；
重点：

求得唯一标识一个 3 x 3 方块的数字，如下：

const squareIndex = Math.floor( i / 3) * 3 + Math.floor( j / 3);

/**
 * @param {character[][]} board
 * @return {boolean}
 */
var isValidSudoku = function(board) {

    const rowLen = board[0].length;
    const columnLen = board.length;

    let row = {};
    let column = {};
    let the3x3Square = {};

    for( let i = 0 ;i < columnLen;i++) {

        for(let j = 0;j < rowLen;j++) {

            let temp = board[i][j];
            if( temp !== '.') {

                const squareIndex = Math.floor( i / 3) * 3 + Math.floor( j / 3);

                if( row[i + '' + temp] || column[j + '' + temp] || the3x3Square[squareIndex + '' + temp]) {
                    return false;
                }
                row[i + '' + temp] = true;
                column[j + '' + temp] = true;
                the3x3Square[squareIndex + '' + temp] = true;
            }
        }
    }
    
    return true;
};

复制代码

3、在 bit 层次来标识是否数字重复出现

使用位运算，在一次遍历中对所有的非 ‘.’ 元素判断是否符合规则；
重点：

求得唯一标识一个 3×3 方块的数字；
通过位运算，可以在一个数字内体现出是否有重复数字（1-9）出现；

/**
 * @param {character[][]} board
 * @return {boolean}
 */
var isValidSudoku = function(board) {

    let raw = new Array(9).fill(0);
    let column = new Array(9).fill(0);
    let square = new Array(9).fill(0);

    let shift = 0;

    for(let i = 0;i < 9;i++) {

        for(let j = 0;j < 9;j++) {
            let temp = board[i][j];
            if( temp !== '.') {

                let squareIndex = Math.floor(i / 3) * 3 + Math.floor(j / 3);
                shift = 1 << Number(temp); // 用 shift 上的某位是否为1来标识某个数字是否出现过
                if( raw[i] & shift || column[j] & shift || square[squareIndex] & shift) {
                    return false;
                }

                raw[i] |= shift;
                column[j] |= shift;
                square[squareIndex] |= shift;

            }
        }
    }

    return true;
};

复制代码