欣迪

出處:https://leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/769/

Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

  1. Each row must contain the digits 1-9 without repetition.
  2. Each column must contain the digits 1-9 without repetition.
  3. Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.
  • A Sudoku board (partially filled) could be valid but is not necessarily solvable.
  • Only the filled cells need to be validated according to the mentioned rules.
Input: 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"]]
Output: true
Input: 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"]]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.

Constraints:

  • board.length == 9
  • board[i].length == 9
  • board[i][j] is a digit 1-9 or '.'.
var isValidSudoku = function(board) {
    
    for(let i = 0; i < 9; i++) {
        // each line
        const chcekRow = new Set()
        for(let j = 0; j < 9; j++ ) {
            if (board[i][j] === '.') continue
            if (!chcekRow.has(board[i][j])) {
                chcekRow.add(board[i][j])
            } else {
                return false
            }
        }
        // each col
        const checkCol = new Set()
        for(let k = 0; k < 9; k++ ) {
            if(board[k][i] === '.') continue
            if (!checkCol.has(board[k][i])) {
                checkCol.add(board[k][i])
            } else {
                return false
            }
        }
        // each 3 x 3
        const groupCol = i % 3
        const groupRow = Math.floor(i/3)
        const checkBox = new Set()
        for(let l = groupCol * 3; l < groupCol * 3 + 3; l++ ) {
            for(let m = groupRow * 3; m < groupRow * 3 + 3; m++) {
                if(board[l][m] === '.') continue
                if (!checkBox.has(board[l][m])) {
                    checkBox.add(board[l][m])
                } else {
                    return false
                }
            }
        }
    }
    return true
};

思路

將驗證分成三個部分, 行, 列, 格

行, 列 驗證比較簡單,不贅述。

每隔的部分就需要稍微多想一下,因為是 9 x 9 的題目,所以拆解後會變成 9 個 3×3 的格子。
所以第一個大 loop 是 9個大格子,第二個 loop 是每格的 x 軸,第三個 loop 是每格的 y 軸。
這邊必須計算起始格的偏移量。
假設現在是第 i 個 3 x 3 格,每三格要換行,所以每個裡面起始的 x 位置會是 i / 3 * 3 , y 的位置則是 Math.floor( i / 3) * 3
計算出來每一個 3×3 格相對大格的位置是 [0][0], [3][0], [6][0], [0][3], [3][3], [6][3], [0][6], [3][6], [6][6]
得到每格位置後,再偏移 3 * 3 去計算內容是否重複

技巧

判斷是否有重複的值可以用 Set 這個 class

https://developer.mozilla.org/zh-TW/docs/Web/JavaScript/Reference/Global_Objects/Set

訂閱 IT-Monk

訂閱最新文章的發布消息! 😚😚😚
Loading

作者介紹 - 欣迪

欣迪

從設計到寫程式,發現自己有追求前端技巧的自虐傾向。不斷的踩坑,再從坑裡爬出來,慢慢對攀岩有點心得。 目前在多間公司擔任網站設計顧問。 同時也是網站架設公司負責人。

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。