gpt4 book ai didi

36. Valid Sudoku 有效的数独

转载 作者:大佬之路 更新时间:2024-01-31 14:22:07 25 4
gpt4 key购买 nike

【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 弟弟快看-教程,程序员编程资料站,版权归原作者所有

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

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com