preface

About the LeetCode array type problem related solutions, it can be seen that LeetCode array type problem before doing must see, classification solution summarized the problem, can be used to improve a single. If you think it is helpful, remember to give more likes and attention, thank you!

Topic describes

Determine if a 9×9 sudoku is valid. Just verify that the entered numbers are valid according to the following rules. The numbers 1-9 May appear only once in a row. The numbers 1-9 May appear only once in each column. The numbers 1-9 occur only once in each 3×3 uterus separated by thick solid lines. (Please refer to the example.) The Spaces in the sudoku section have been filled in with numbers, and the Spaces are represented by ‘.’.

Note: A valid sudoku (partially filled) is not necessarily solvable. You just need to verify that the entered numbers are valid according to the above rules.

Example 1: Enter: board = [[“5″,”3″,”.”,”.”,”7″,”.”,”.”,”.”,”.”] ,[“6″,”.”,”.”,”1″,”9″,”5″,”.”,”.”,”.”] [“. “, “9”, “eight”, “”,” “, “”,” “, “6”, “”], [” 8″, “”,” “, “”,” 6 “, “”,” “, “”,” 3 “], [” 4 “, “”,” “, “eight”, “”,” 3 “, “”,” “, “1”] [” 7 “, “. “, “”,” “, “2”, “”,” “, “”,” 6 “], [“. “, “6”, “”,” “, “”,” “, “2”, “eight”, “”], [“.”, “”,” “, “4”, “1”, “9”, “”,” “, “5”] ,[“.”,”.”,”.”,”.”,”.”,”.”,”.”,”8″,”.”,” 7″,”9″]] Output: true

Example 2: Enter: board = [[“8″,”3″,”.”,”.”,”7″,”.”,”.”,”.”,”.”] ,[“6″,”.”,”.”,”1″,”9″,”5″,”.”,”.”,”.”] [“. “, “9”, “eight”, “”,” “, “”,” “, “6”, “”], [” 8″, “”,” “, “”,” 6 “, “”,” “, “”,” 3 “], [” 4 “, “”,” “, “eight”, “”,” 3 “, “”,” “, “1”] [” 7 “, “. “, “”,” “, “2”, “”,” “, “”,” 6 “], [“. “, “6”, “”,” “, “”,” “, “2”, “eight”, “”], [“.”, “”,” “, “4”, “1”, “9”, “”,” “, “5”] [“. “, “. “, “”,” “, “eight”, “”,” “, “7”, “9”]] output: false interpretation: in addition to the first line of the first number changed from 5 to 8, other Numbers are the same as the sample 1 box. But because the 3×3 uterus in the upper left corner has two 8s, this sudoku is invalid. Link: leetcode-cn.com/problems/va…

Answer key

  1. Three arrays are used, row, COL and subBox. The element of each array is an object, and the element of the object is a number. The value is 1/undefine, which is used to record whether the number appears on the diagonal of the row, column and subBox. The time complexity is O(n²)
/ * * *@param {character[][]} board
 * @return {boolean}* /
var isValidSudoku = function(board) {
    let row = Array.from({ length: 9 }, () = > ({}))
    let col = Array.from({ length: 9 }, () = > ({}))
    let subBox = Array.from({ length: 9 }, () = > ({}))
    for (let i = 0; i < 9; i++) {
      for (let j = 0; j < 9; j++) {
        const now = board[i][j]
        if(now ! = ='. ') {
          const indexSubBox = Math.floor(i / 3) * 3 + Math.floor(j / 3)
          if (row[i][now] || col[j][now] || subBox[indexSubBox][now]) {
            return false
          } 
          row[i][now] = 1
          col[j][now] = 1
          subBox[indexSubBox][now] = 1}}}return true
};
Copy the code