LeetCode 36. 有效的数独

作者: freesan44 | 来源:发表于2020-05-31 19:02 被阅读0次

    题目

    判断一个 9x9 的数独是否有效。只需要根据以下规则,验证已经填入的数字是否有效即可。

    数字 1-9 在每一行只能出现一次。
    数字 1-9 在每一列只能出现一次。
    数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

    上图是一个部分填充的有效的数独。

    数独部分空格内已填入了数字,空白格用 '.' 表示。

    示例 1:
    
    输入:
    [
      ["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:
    
    输入:
    [
      ["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
    解释: 除了第一行的第一个数字从 5 改为 8 以外,空格内其他数字均与 示例1 相同。
         但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。
    

    说明:

    一个有效的数独(部分已被填充)不一定是可解的。
    只需要根据以上规则,验证已经填入的数字是否有效即可。
    给定数独序列只包含数字 1-9 和字符 '.' 。
    给定数独永远是 9x9 形式的。

    解题思路

    先把每行每列每个九宫格抽取出来,然后进行重复判断,可以用元组重复判断

    class Solution:
        def isValidSudoku(self, board: [[str]]) -> bool:
            lines = [[] for i in range(9)] #横数组
            rows = [[] for i in range(9)] #竖数组
            block = [[] for i in range(9)]#九宫格
            for i in range(0,9):
                for j in range(0,9):
                    if board[i][j] != ".":
                        lines[i].append(board[i][j])
                        rows[j].append(board[i][j])
                        block[i//3*3+j//3].append(board[i][j])
            for line in lines:
                if len(line) != len(set(line)):
                    return False
            for row in rows:
                if len(row) != len(set(row)):
                    return False
            for bl in block:
                if len(bl) != len(set(bl)):
                    return False
    
    
            return True
    

    相关文章

      网友评论

        本文标题:LeetCode 36. 有效的数独

        本文链接:https://www.haomeiwen.com/subject/kturzhtx.html