LeetCode36-有效的数独

今天中午在食堂吃完饭回来的途中看到了一位老爷爷在卖东西

于是好奇的上去凑凑热闹

发现是在卖水墨画

而且画的还真是挺棒的

老爷爷十分热情

于是我上去和他交流

他说：他是退休人民教师（第一眼看上去就像是）

他是教理工科的，画画是他的兴趣爱好

这些画，都是他一笔一画的添上去的

看着这位老教师脸上洋溢的笑容

真心为他点赞！！！

下面附两幅我拍的照片

LeetCode36-有效的数独

36-有效的数独

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

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

LeetCode36-有效的数独

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

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

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

思路：

这一题其实算是比较简单的了，没有什么绕弯的地方，就是分情况讨论就行。本题是要讨论3种情况：

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

只要有一种情况不符合，那就说明这个不是数独，我这儿查重的方法是用set()函数来实现的，只需要比较使用set()函数前后的数组长度大小即可判断，直接贴代码。

代码如下：

import numpy as np


class Solution:
    # 题目分三种情况讨论，那我们也分三种情况讨论
    # 先讨论每一行和每一列的重复情况（2合1）
    # 最后讨论3x3矩阵内的重复情况
    def isValidSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: bool
        """
        board = np.array(board)
        length = np.shape(board)[0]
        Flag = False
        for col in range(length):
            row = [index for index in board[col] if '0' <= index <= '9']
            column = [index for index in board[:, col] if '0' <= index <= '9']
            row_length = len(row)
            column_length = len(column)
            row_set = set(row)
            column_set = set(column)
            if len(row_set) < row_length or len(column_set) < column_length:
                return False
            else:
                Flag = True
        for row_index in range(0, 9, 3):
            for column_index in range(0, 9, 3):
                batch = board[row_index:row_index+3, column_index:column_index+3]
                batch = batch.flatten()
                batch_num = [index for index in batch if '0' <= index <= '9']
                batch_num_length = len(batch_num)
                batch_num_set = set(batch_num)
                if len(batch_num_set) < batch_num_length:
                    return False
                else:
                    Flag = True
        return Flag


if __name__ == "__main__":
    board = [['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']]
    result = Solution().isValidSudoku(board)
    print(result)

但是执行效率挺低的，只有4%左右，在网上找了半天，也没有特别好的方法，如果各位笔者有更优良的方法，请一定要告诉我哈！！！

LeetCode36-有效的数独

顺便也把我用字典法写的查重方法贴出来吧，本还以为使用了字典速度会快些，结果却是不快反慢，一脸懵逼！！！

import numpy as np


class Solution:
    # 改进版，每种情况下for循环查重时使用字典来加快速度；也就是把每一列每一行元素的值保存在字典的key键中，value初始值为0
    # 然后对每一列每一行依次遍历，若发现只要有一个value值大于1，则有重复数。立即退出
    # 题目分三种情况讨论，那我们也分三种情况讨论
    # 先讨论每一行和每一列的重复情况（2合1）
    # 最后讨论3x3矩阵内的重复情况
    def isValidSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: bool
        """
        board = np.array(board)
        Flag = True
        for col in range(len(board)):
            if self.check(board[col]) is False or self.check(board[:, col]) is False:
                return False
        for row_index in range(0, 9, 3):
            for column_index in range(0, 9, 3):
                batch = board[row_index:row_index+3, column_index:column_index+3]
                batch = batch.flatten()
                if self.check(batch) is False:
                    return False
        return Flag

    # 查重函数
    def check(self, one_array):
        # 创建一字典，里面key值为给定数组里的值，value初始值设为0
        check_dict = dict.fromkeys(one_array, 0)
        # 依次遍历给定one_array数组里的值，如果发现有一个value值大于1，说明有重复数，返回False，立即退出
        for index in one_array:
            if index in check_dict.keys():
                if index != '.':
                    check_dict[index] += 1
                if check_dict[index] > 1:
                    return False
        return True


if __name__ == "__main__":
    board = [['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']]
    result = Solution().isValidSudoku(board)
    print(result)

这是他的执行效率。

LeetCode36-有效的数独

LeetCode36-有效的数独

36-有效的数独

相关推荐