LeetCode 36. 有效的数独

36. 有效的数独

题目：
请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。
① 数字 1-9 在每一行只能出现一次。
② 数字 1-9 在每一列只能出现一次。
③ 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
注意：一个有效的数独（部分已被填充）不一定是可解的。

链接 https://leetcode.cn/problems/valid-sudoku

个人思路

1. 没什么好的思路，按要求判断行、列、宫内是否存在重复数字即可

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        # 判断行是否符合
        for i in board:
            temp = []
            for j in i:
                if j.isdigit() and j in temp:
                    return False
                else:
                    temp.append(j)                   
        # 判断列是否符合
        for j in range(9):
            temp = []
            for i in range(9):
                if board[i][j].isdigit() and board[i][j] in temp:
                    return False
                else:
                    temp.append(board[i][j])
        # 判断以点（x，y）为左上角的宫是否符合
        def isvalid(x,y):
            temp = []
            dot = [(x,y),(x,y+1),(x,y+2),(x+1,y),(x+1,y+1),(x+1,y+2),\
            (x+2,y),(x+2,y+1),(x+2,y+2)]
            for i,j in dot:
                if board[i][j].isdigit() and board[i][j] in temp:
                    return False
                else:
                    temp.append(board[i][j])    
            return True
        # 左上角的点
        leftdot = [(0,0),(0,3),(0,6),(3,0),(3,3),(3,6),(6,0),(6,3),(6,6)]
        for i,j in leftdot:
            if not isvalid(i,j):
                return False
        return True
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

注意：类内的方法必须要有self方法(来自一个在本地测试时把self删除后一直报错’‘xxx takes 1 positional argument but 2 were given’'的大冤种）

官方思路

1. 哈希表一次遍历，但感觉没有我的代码那么清晰，容易理解
   贴一个官方哈希java代码：

复杂度分析
时间复杂度：O(1)。数独共有 81 个单元格，只需要对每个单元格遍历一次即可。
空间复杂度：O(1)。由于数独的大小固定，因此哈希表的空间也是固定的。

class Solution {
    public boolean isValidSudoku(char[][] board) {
        int[][] rows = new int[9][9];
        int[][] columns = new int[9][9];
        int[][][] subboxes = new int[3][3][9];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char c = board[i][j];
                if (c != '.') {
                    int index = c - '0' - 1;
                    rows[i][index]++;
                    columns[j][index]++;
                    subboxes[i / 3][j / 3][index]++;
                    if (rows[i][index] > 1 || columns[j][index] > 1 || subboxes[i / 3][j / 3][index] > 1) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

而且没有python代码，这里贴一个其他大佬的代码：

class Solution:
    def isValid(self, flatList):
        cnt = Counter("".join(flatList))
        for k, v in cnt.items():
            if k != '.' and v > 1:
                return False
        return True

    def isValidSudoku(self, board) -> bool:
        border = [[0, 3], [3, 6], [6, 9]]
        # 1.遍历每一行
        for i in range(9):
            if not self.isValid(board[i]):
                return False
        # 2. 遍历每一列, 注意不能采取类似numpy的索引方式board[:][j]
        for j in range(9):
            tmp = [board[i][j] for i in range(9)]
            if not self.isValid(tmp):
                return False
        # 3. 遍历每一宫
        for i in border:
            for j in border:
                Gong = board[i[0]:i[1]]
                flatGong = [Gong[m][n] for m in range(3) for n in range(j[0], j[1])]
                # print(flatGong)
                if not self.isValid(flatGong):
                    return False
        return True
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

作者：CodeHard_LiveFun
链接：https://leetcode.cn/problems/valid-sudoku/solution/by-codehard_livefun-wjun/。