有效的数独

原文链接

判断一个 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 形式的。

解答¶

初步看到题目的时候，判断思路比较简单，就是判断行、列和九宫格的矩阵是否存在重复的数字。

我这边思路是通过，判断数字的实际个数，与数组 set 散列化之后的实际个数，如果大小不相等，则说明存在有重复的数字。

通过重复比较行、列、九宫格的值，如果不相等则跳出返回。最后如果判断全部完成，则说明是一个合理的数独。

写出代码如下：

In [2]:

class Solution:
    def isValidSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: bool
        """
        from collections import Counter
        for i in range(9):
            column_list = [ board[j][i] for j in range(9) ] 
            matrix_x = i // 3
            matrix_y = i%3
            matrix = [
                board[x][y]
                for x in range(matrix_x*3, (matrix_x+1)*3)
                for y in range(matrix_y*3, (matrix_y+1)*3)
            ]
            for v in (board[i], column_list, matrix):
                if len(set(v)) - 1 != 9 - Counter(v)["."]:
                    return False
        return True

这里我利用了一个数据结构 Counter 来将数组转化为相应的计数器，然后通过判断分别判断行、列、九宫格是否存在重复数字。

优化¶

但是以上解答实际上有个缺点，首先，其需要多次取值来构造判断的数组，其次，利用 Counter 也是对数组的一层遍历。

这里可以修改一下思路，使用字典遍历所有的元素来辅助我们达到一样的效果。

参考了一下时间耗时最短的写法，代码如下:

In [3]:

class Solution:
    def isValidSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: bool
        """
        rows = [''] * 9
        cols = [''] * 9
        grids = [''] * 9
        for idx, row in enumerate(board):
            for i, v in enumerate(row):
                if v != ".":
                    grid_index =  idx // 3 * 3 + i // 3
                    if v in rows[idx] or \
                        v in cols[i] or \
                        v in grids[grid_index]:
                        return False
                    rows[idx] += v
                    cols[i] += v
                    grids[grid_index] += v
        return True

一点备注¶

在尝试第二种解法的时候，一开始我是想着通过数组来存放 rows 、cols 、grids 中的每一组元素，在初始化的时候用使用了 [[]] * 9 这样的方式来初始化空数组。

但是在赋值的时候，发现造成了一个类似广播的效果。大概如下图。

错误的赋值

一开始还没有想出来问题所在，后来想了想，发现是应该是在数组乘法操作的时候，实际上是将该数组的指针复制了若干次。

此时原数组进行修改，自然会应用到所有的元素上去。

通过打印元素的 id 也可以证明这一点。

← 两数之和罗马数字转整数 →

Comments !

Search

2018-07-01

LeetCode