36. Valid Sudoku 有效的数独

【LeetCode】36. Valid Sudoku 解题报告（Python）

题目地址：https://leetcode.com/problems/valid-sudoku/description/

题目描述：

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

1、 Eachrowmustcontainthedigits1-9withoutrepetition.；
2、 Eachcolumnmustcontainthedigits1-9withoutrepetition.；
3、 Eachofthe93x3sub-boxesofthegridmustcontainthedigits1-9withoutrepetition.；

Apartially filled sudoku which is valid.

TheSudoku board could be partially filled, where empty cells are filled with the character '.'.

Example 1:

Input:
[
  ["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:
[
  ["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.

Note:

1、 ASudokuboard(partiallyfilled)couldbevalidbutisnotnecessarilysolvable.；
2、 Onlythefilledcellsneedtobevalidatedaccordingtothementionedrules.；
3、 Thegivenboardcontainonlydigits1-9andthecharacter'.'.；
4、 Thegivenboardsizeisalways9x9.；

题目大意

判断一个9*9的二维数组是不是一个有效的数独。只用判断有效即可，即题目中的三个条件，不用求解。

解题方法

如果只判断有效的话，实现三个函数分别对应三个条件即可：判断行，判断列，判断9宫格。

把要判断的这些位置的数字取出来，然后用set后的长度是否等于原长度就能知道是不是有重复数字了。题目中已经说了给出的数字只有1~9，所以省掉了很多事。判断之前需要把'.'给去掉，因为数字只允许出现一次，而'.'可能出现多次。

时间复杂度是O(N^2)，空间复杂度是O(N).

代码如下：

class Solution(object):
    def isValidSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: bool
        """
        n = len(board)
        return self.isValidRow(board) and self.isValidCol(board) and self.isValidNineCell(board)
        
    def isValidRow(self, board):
        n = len(board)
        for r in range(n):
            row = [x for x in board[r] if x != '.']
            if len(set(row)) != len(row):
                return False
        return True

    def isValidCol(self, board):
        n = len(board)
        for c in range(n):
            col = [board[r][c] for r in range(n) if board[r][c] != '.']
            if len(set(col)) != len(col):
                return False
        return True

    def isValidNineCell(self, board):
        n = len(board)
        for r in range(0, n, 3):
            for c in range(0, n, 3):
                cell = []
                for i in range(3):
                    for j in range(3):
                        num = board[r + i][c + j]
                        if num != '.':
                            cell.append(num)
                if len(set(cell)) != len(cell):
                    return False
        return True

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有

本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发