leetcode/36.有效的数独.py at main · lit-road/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
# @before-stub-for-debug-begin
from python3problem36 import *
from typing import *
# @before-stub-for-debug-end

#
# @lc app=leetcode.cn id=36 lang=python3
#
# [36] 有效的数独
#

# @lc code=start
class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        rows = [{} for _ in range(9)]
        columns = [{} for _ in range(9)]
        boxes = [{} for _ in range(9)]

        for i in range(9):
            for j in range(9):
                num = board[i][j]
                if num == ".":
                    continue

                rows[i][num] = rows[i].get(num, 0) + 1
                columns[j][num] = columns[j].get(num, 0) + 1
                boxex_index = (i // 3) * 3 + j // 3
                boxes[boxex_index][num] = boxes[boxex_index].get(num, 0) + 1

                if rows[i][num] > 1 or columns[j][num] > 1 or boxes[boxex_index][num] > 1:
                    return False

        return True

# @lc code=end

# @history 2021/7/6 start
class HistorySolution:
    # 507/507 cases passed (56 ms)
    # Your runtime beats 7.92 % of python3 submissions
    # Your memory usage beats 41.93 % of python3 submissions (16.4 MB)
    def isValidSudoku1(self, board: List[List[str]]) -> bool:
        # 同行不重复
        # 同列不重复
        # 同3x3宫格不重复
        for i in range(9): # 行
            for j in range(9): # 列
                if board[i][j] == '.':
                    continue
                # 判断是否重复
                for k in range(9):
                    if j != k and board[i][j] == board[i][k] or i != k and board[i][j] == board[k][j]:
                        return False
                # 判断3x3宫格
                i_begin, j_begin = i // 3 * 3, j // 3 * 3
                for m in range(i_begin, i_begin + 3):
                    for n in range(j_begin, j_begin + 3):
                        if i != m and j != n and board[i][j] == board[m][n]:
                            return False

        return True

    # 507/507 cases passed (43 ms)
    # Your runtime beats 66.04 % of python3 submissions
    # Your memory usage beats 37.12 % of python3 submissions (16.4 MB)
    def isValidSudoku2(self, board: List[List[str]]) -> bool:

        rows = [{} for _ in range(9)]
        columns = [{} for _ in range(9)]
        boxes = [{} for _ in range(9)]

        for i in range(9):
            for j in range(9):
                num = board[i][j]
                if num == ".":
                    continue

                rows[i][num] = rows[i].get(num, 0) + 1
                columns[j][num] = columns[j].get(num, 0) + 1
                boxex_index = (i // 3) * 3 + j // 3
                boxes[boxex_index][num] = boxes[boxex_index].get(num, 0) + 1

                if rows[i][num] > 1 or columns[j][num] > 1 or boxes[boxex_index][num] > 1:
                    return False

        return True
# @history 2021/7/6 end

# @test start
def test_valid_sudoku_board(self):
    solution = HistorySolution()
    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"]
    ]
    assert solution.isValidSudoku1(board) == True

def test_one_cell_filled(self):
    solution = HistorySolution()
    board = [
        [".",".",".",".",".",".",".",".","."],
        [".",".",".",".",".",".",".",".","."],
        [".",".",".",".",".",".",".",".","."],
        [".",".",".",".",".",".",".",".","."],
        [".",".",".",".","5",".",".",".","."],
        [".",".",".",".",".","5",".",".","."],
        [".",".",".",".",".",".",".",".","."],
        [".",".",".",".",".",".",".",".","."],
        [".",".",".",".",".",".",".",".","."]
    ]
    assert solution.isValidSudoku1(board) == False
# @test end