首页 > 其他 > 详细

leetcode 36. 有效的数独

时间:2019-01-20 13:01:08      阅读:205      评论:0      收藏:0      [点我收藏+]

由于工作原因,以后A题一般都使用Python,不得不说Python还挺方便的,作为一个脚本语言学好了,会省很多事情。

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

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

技术分享图片

Code 1:

class Solution:
    def isValidSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: bool
        """

        for i in range(9):
            for j in range(9):
                if board[i][j] == .:
                    board[i][j] = 0
                else :
                    board[i][j] = int(board[i][j])


        flag = [0] * 10
        ans = True
        for i in range(9):
            flag = [0] * 10
            for j in range(9):
                if board[i][j] == 0:
                    continue
                flag[board[i][j]]+=1
                if flag[board[i][j]] > 1:
                    ans = False


        flag = [0] * 10

        for j in range(9):
            flag = [0] * 10
            for i in range(9):
                if board[i][j] == 0:
                    continue
                flag[board[i][j]] +=1
                if flag[board[i][j]] > 1:
                    ans = False


        for i in range(0,9,3):
            for j in range(0,9,3):
                flag = [0]*10
                for m in range(3):
                    for n in range(3):
                        if board[i+m][j+n] == 0:
                            continue
                        flag[board[i+m][j+n]] +=1
                        if flag[board[i+m][j+n]] > 1:
                            ans = False

        return ans

Code : 2

技术分享图片

  • 根据行列,可以得到子数独的索引 (row // 3) * 3 + col // 3
  • Python字典,d.get(key, default) ,当没有这个键,或者键没有值时,使用get方法返回默认值,否则出错。
class Solution:
    def isValidSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: bool
        """
        # init data
        rows = [{} for i in range(9)]
        columns = [{} for i in range(9)]
        boxes = [{} for i in range(9)]

        # validate a board
        for i in range(9):
            for j in range(9):
                num = board[i][j]
                if num != .:
                    num = int(num)
                    box_index = (i // 3) * 3 + j // 3

                    rows[i][num] = rows[i].get(num, 0) + 1
                    columns[j][num] = columns[j].get(num, 0) + 1
                    boxes[box_index][num] = boxes[box_index].get(num, 0) + 1

                    # check if this value has been already seen before
                    if rows[i][num] > 1 or columns[j][num] > 1 or boxes[box_index][num] > 1:
                        return False
        return True

 

leetcode 36. 有效的数独

原文:https://www.cnblogs.com/TreeDream/p/10294464.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!