Skip to content

Latest commit

 

History

History
144 lines (106 loc) · 3.81 KB

36.valid_sudoku.md

File metadata and controls

144 lines (106 loc) · 3.81 KB
Raw
  1. Valid Sudoku

中等

https://leetcode.cn/problems/valid-sudoku/

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

  • Each row must contain the digits 1-9 without repetition.
  • Each column must contain the digits 1-9 without repetition.
  • Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.

Note:

  • 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.

Example 1:


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

Example 2:

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 '.'.

相关企业

  • 亚马逊 Amazon|17
  • 优步 Uber|9
  • 苹果 Apple|8
  • 微软 Microsoft|8
  • Facebook|5
  • 字节跳动|4
  • 谷歌 Google|3
  • 英伟达 NVIDIA|2

相关标签

  • Array
  • Hash Table
  • Matrix

相似题目

  • Sudoku Solver 困难

solution

解题思路

这题考查的是二维数组的遍历顺序。

判断每一行是否合法，外层循环枚举行，内层循环枚举列。

判断每一列是否合法，外层循环枚举列，内层循环枚举行。

判断每一块是否合法，每一块左上角的坐标都是(0, 0), (3, 0), (6, 0), (0, 3), (3, 3), (6, 3), (0, 6), (3, 6), (6, 6) ，可以发现都是3的倍数，可以总结出规律，先枚举i = [0, 1, 2]，再枚举j = [0, 1, 2]，左上角坐标就是(i3, j3)。

复杂度分析

假设这是一个N * N的数独，不止是9 * 9。

时间复杂度

要遍历3次这个数独，时间复杂度为O(N^2)。

空间复杂度

需要O(N)的空间，记录以用过的数。

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        if not board:
            return False

        # 先枚举行，检查每行是否合法
        for row in range(9):
            used = set()
            for col in range(9):
                if not self.isValid(board[row][col], used):
                    return False
        
        # 先枚举列，检查每列是否合法
        for col in range(9):
            used = set()
            for row in range(9):
                if not self.isValid(board[row][col], used):
                    return False

        # 每一块左上角的坐标(0, 0), (3, 0), (6, 0), (0, 3), (3, 3), (6, 3), (0, 6), (3, 6), (6, 6) 
        # 每个分块的左上角的坐标为(i * 3, j * 3)
        for i in range(3):
            for j in range(3):
                used = set()
                for row in range(i*3, i*3+3):
                    for col in range(j*3, j*3+3):
                        if not self.isValid(board[row][col], used):
                            return False
        return True
        
        
    def isValid(self, char, used):
        if char == ".":
            return True
        if char in used:
            return False
        used.add(char)
        return True