36. 有效的数独

https://leetcode-cn.com/problems/valid-sudoku/

解法一:

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        for i in range(9):
            rows = set()  #每次i循环检测第i行
            cols = set()   #每次i循环检测第i列
            cubes = set()  #每次循环检测一块

            for j in range(9):
                char = board[i][j]
                if char != '.':
                    if char not in rows:
                        rows.add(char)
                    else:
                        return False

                char = board[j][i]
                if char != '.':
                    if char not in cols:
                        cols.add(char)
                    else:
                        return False

                rowIndex = 3*(i//3)
                colIndex = 3*(i%3)
                char = board[rowIndex + j//3][colIndex + j%3]
                if char != '.':
                    if char not in cubes:
                        cubes.add(char)
                    else:
                        return False
        return True

解法二:

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        for i in range(9):
            for j in range(9):
                if board[i][j] != '.':
                    #若该位置不为空,调用验证函数
                    if not self.isValid(board, i, j):
                        return False
        return True
    
    def isValid(self, board, row, col):    #验证是否与(row,col)位置重复
        for i in range(9):
            #验证同一列是否有重复
            if i != row and board[i][col] != '.' and board[i][col] == board[row][col]:
                return False
            # 验证同一行
            if i != col and board[row][i] != '.' and board[row][i] == board[row][col]: 
                return False
            #验证同一块
            #以该块的最左上角为基准[3*(row//3), 3*(col//3)]
            #从左到右(i//3),从上到下(i%3)遍历
            if 3 * (row // 3) + i // 3 != row \
              and 3 * (col // 3) + i % 3 != col \
              and board[3 * (row // 3) + i // 3][3 * (col // 3) + i % 3] != '.' \
              and board[3 * (row // 3) + i // 3][3 * (col // 3) + i % 3] == board[row][col]:  # 验证同一块
                return False
        return True

最后更新于