LeetCode——有效的数独

左手的ㄟ右手 2022-05-15 07:11 242阅读 0赞

**题目**：

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

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

![250px-Sudoku-by-L2G-20050714.svg.png][]

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

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

**示例 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` 形式的。

**思路**：

这种限定了数字的个数并且是正整数的，首先要想到用数组来判断数字的个数是否超标，比如1的个数，那么就判断num\[1\]中的大小就可以了。根据数独的规则，我们只要判断每行，每列和每个3\*3方格是否满足就行。

**代码**：

class Solution:
        def isValidSudoku(self, board):
            """
            :type board: List[List[str]]
            :rtype: bool
            """
            numlist = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
            #先求列是否重复
            for i in range(0,9):
                numlist = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
                for row in board:
                    if row[i] != '.':
                        numlist[int(row[i])] += 1
                        if numlist[int(row[i])] > 1:
                            return False
            #求行是否重复
            for i in range(0,9):#得到某一行
                numlist = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
                for index, num in enumerate(board[i]):
                    if num != '.':
                        numlist[int(num)] += 1
                        if numlist[int(num)] > 1:
                            return False
            #得到每一个3*3方格
            for i in range(0, 9):
                #得到x，y的上下限
                minX = (int(i/3)) *3
                minY = (i % 3)*3
                maxX = (int(i/3)+1) *3-1
                maxY = (i % 3+1)*3 -1
                numlist = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
                index1 = minX
                while index1 <= maxX:
                    index2 = minY
                    while index2 <= maxY:
                        if board[index1][index2] !='.':
                            numlist[int(board[index1][index2] )] += 1
                            if numlist[int(board[index1][index2] )] > 1:
                                return False
                        index2 += 1
                    index1 += 1
            return True
    
    
    
    
    
    
    if __name__ =="__main__":
        res = Solution()
        print(res.isValidSudoku([
      ["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"]
    ]))
        pass

[250px-Sudoku-by-L2G-20050714.svg.png]: https://upload.wikimedia.org/wikipedia/commons/thumb/f/ff/Sudoku-by-L2G-20050714.svg/250px-Sudoku-by-L2G-20050714.svg.png