前端算法題解leetcode36-有效的數(shù)獨(dú)示例

更新時(shí)間：2022年09月23日 10:23:14 作者：前端_奔跑的蝸牛

這篇文章主要為大家介紹了前端算法題解leetcode36-有效的數(shù)獨(dú)示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

題目

題目地址

請你判斷一個 9 x 9 的數(shù)獨(dú)是否有效。只需要 根據(jù)以下規(guī)則 ，驗(yàn)證已經(jīng)填入的數(shù)字是否有效即可。

數(shù)字 1-9 在每一行只能出現(xiàn)一次。
數(shù)字 1-9 在每一列只能出現(xiàn)一次。
數(shù)字 1-9 在每一個以粗實(shí)線分隔的 3x3 宮內(nèi)只能出現(xiàn)一次。（請參考示例圖）

注意：

一個有效的數(shù)獨(dú)（部分已被填充）不一定是可解的。
只需要根據(jù)以上規(guī)則，驗(yàn)證已經(jīng)填入的數(shù)字是否有效即可。
空白格用 '.' 表示。

示例 1：

輸入： board =
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]

輸出： true

示例 2：

輸入： board =
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]

輸出： false

解釋：除了第一行的第一個數(shù)字從 5 改為 8 以外，空格內(nèi)其他數(shù)字均與示例1 相同。但由于位于左上角的 3x3 宮內(nèi)有兩個 8 存在, 因此這個數(shù)獨(dú)是無效的。

提示：

board.length == 9

board[i].length == 9

board[i][j] 是一位數(shù)字（1-9）或者 '.'

解題思路-分別處理

分別處理每一行、每一列以及每一個九宮格，哪一部分驗(yàn)證失敗，都返回 false，如果都驗(yàn)證通過，返回 true。

代碼實(shí)現(xiàn)

function getOrigin(){
    return {
        '1':0,
        '2':0,
        '3':0,
        '4':0,
        '5':0,
        '6':0,
        '7':0,
        '8':0,
        '9':0,
    }
}
function checkArr(arr){
    const counts = getOrigin()
    for(let i = 0;i<9;i++){
        if(counts[arr[i]]){
            return false
        }else{
            counts[arr[i]]++
        }
    }
    return true
}
var isValidSudoku = function(board) {
    // 處理每一行
    for(let i = 0;i<9;i++){
        if(!checkArr(board[i])){
            return false
        }
    }
    // 處理每一列
    for(let i = 0;i<9;i++){
        const arr = []
        for(let j = 0;j<9;j++){
            if(board[j][i] === '.'){
                continue
            }
            arr.push(board[j][i])
        }
        if(!checkArr(arr)){
            return false
        }
    }
    // 處理 9 個九宮格
    for(let i = 0;i<3;i++){
        for(let j = 0;j<3;j++){
            const arr = []
            for(let k = j*3;k<j*3+3;k++){
                for(let h = 3*i;h<3*i+3;h++){
                    if(board[k][h] === '.'){
                        continue
                    }
                    arr.push(board[k][h])
                }
            }
            if(!checkArr(arr)){
                return false
            }
        }
    }
    return true
}

解題思路-一次掃描判斷所有

首先創(chuàng)建 lines 記錄每一行出現(xiàn)的數(shù)字的次數(shù)，columns 記錄每一列出現(xiàn)的數(shù)字的次數(shù)，scratchableLatexs 記錄每一個九空格出現(xiàn)的數(shù)字的次數(shù)。

然后雙層循環(huán)可以遍歷輸入數(shù)組中的每一個元素，根據(jù)當(dāng)前 i,j 值判斷屬于哪一行，哪一列以及哪一個九宮格，分別判斷即可。

代碼實(shí)現(xiàn)

function getOrigin(){
    return {
        '1':0,
        '2':0,
        '3':0,
        '4':0,
        '5':0,
        '6':0,
        '7':0,
        '8':0,
        '9':0,
    }
}
var isValidSudoku = function(board) {
    const lines = []
    const columns = []
    const scratchableLatexs = []
    for(let i = 0;i<9;i++){
        lines[i] = getOrigin()
        columns[i] = getOrigin()
        scratchableLatexs[i] = getOrigin()
    }
    for(let i = 0;i<9;i++){
        for(let j = 0;j<9;j++){
            const item = board[i][j]
            if(item === '.'){
                continue
            }
            if(lines[i][item]){
                return false
            }else{
                lines[i][item]++
            }
            if(columns[j][item]){
                return false
            }else{
                columns[j][item]++
            }
            if(i<3){
                if(j<3){
                    if(scratchableLatexs[0][item]){
                        return false
                    }else{
                        scratchableLatexs[0][item]++
                    }
                }else if(j<6){
                    if(scratchableLatexs[1][item]){
                        return false
                    }else{
                        scratchableLatexs[1][item]++
                    }
                }else{
                    if(scratchableLatexs[2][item]){
                        return false
                    }else{
                        scratchableLatexs[2][item]++
                    }
                }
            }else if(i<6){
                if(j<3){
                    if(scratchableLatexs[3][item]){
                        return false
                    }else{
                        scratchableLatexs[3][item]++
                    }
                }else if(j<6){
                    if(scratchableLatexs[4][item]){
                        return false
                    }else{
                        scratchableLatexs[4][item]++
                    }
                }else{
                    if(scratchableLatexs[5][item]){
                        return false
                    }else{
                        scratchableLatexs[5][item]++
                    }
                }
            }else{
                if(j<3){
                    if(scratchableLatexs[6][item]){
                        return false
                    }else{
                        scratchableLatexs[6][item]++
                    }
                }else if(j<6){
                    if(scratchableLatexs[7][item]){
                        return false
                    }else{
                        scratchableLatexs[7][item]++
                    }
                }else{
                    if(scratchableLatexs[8][item]){
                        return false
                    }else{
                        scratchableLatexs[8][item]++
                    }
                }
            }
        }
    }
    return true
}

至此我們就完成了 leetcode-36-有效的數(shù)獨(dú)，更多關(guān)于前端算法題解有效的數(shù)獨(dú)的資料請關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: