美文网首页
10 - Easy - 有效的数独

10 - Easy - 有效的数独

作者: 1f872d1e3817 | 来源:发表于2018-04-18 14:17 被阅读0次

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

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

    <small style="box-sizing: border-box; font-size: 12px;">上图是一个部分填充的有效的数独。</small>

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

    示例 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 存在, 因此这个数独是无效的。</pre>

    说明:

    • 一个有效的数独(部分已被填充)不一定是可解的。
    • 只需要根据以上规则,验证已经填入的数字是否有效即可。
    • 给定数独序列只包含数字 1-9 和字符 '.'
    • 给定数独永远是 9x9 形式的。
    class Solution:
        def isValidSudoku(self, board):
            """
            :type board: List[List[str]]
            :rtype: bool
            """
            row = [[] for _ in range(9)]  # 行记录器
            col = [[] for _ in range(9)]  # 列记录器
            area = [[] for _ in range(9)]  # 子区域记录器
            for i in range(9):
                for j in range(9):
                    element = board[i][j]  # 遍历所有元素
                    if element != '.':  # 有数字才记录下来
                        top_id = i//3*3 + j//3  # 每个元素子区域的计算方法
                        if element in row[i] or element in col[j] or element in area[top_id]:  # 如果在这一行列子区域重读出现过了
                            return False
                        else:  # 没有出现过就加进去
                            row[i].append(element)
                            col[j].append(element)
                            area[top_id].append(element)
            return True
    
    class Solution:
        def isValidSudoku(self, board):
            """
            :type board: List[List[str]]
            :rtype: bool
            """
            row = [[0 for _ in range(9)] for _ in range(9)]
            col = [[0 for _ in range(9)] for _ in range(9)]
            mat = [[0 for _ in range(9)] for _ in range(9)]
            for i in range(9):
                for j in range(9):
                    if board[i][j] != ".":
                        num = int(board[i][j]) - 1
                        k = i // 3 * 3 + j // 3
                        if row[i][num] or col[j][num] or mat[k][num]:
                            return False
                        row[i][num] = col[j][num] = mat[k][num] = 1
            return True
    

    相关文章

      网友评论

          本文标题:10 - Easy - 有效的数独

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