目录
- 题目
- 答案
- 运行结果
题目
请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ,验证已经填入的数字是否有效即可。
- 数字 1-9 在每一行只能出现一次。
- 数字 1-9 在每一列只能出现一次。
- 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。(请参考示例图)
注意:
- 一个有效的数独(部分已被填充)不一定是可解的。
- 只需要根据以上规则,验证已经填入的数字是否有效即可。
- 空白格用 ‘.’ 表示。
提示:
- board.length == 9
- board[i].length == 9
- board[i][j] 是一位数字(1-9)或者 ‘.’
答案
有效的数独满足以下三个条件:
- 每一行中的数字都不重复;
- 每一列中的数字都不重复;
- 每一个 3×3 的宫格中的数字都不重复。
遍历数独,对于每个数字,判断其所在的行、列 以及 3×3 的宫格是否已经出现过该数字,如果是,则返回 false。遍历结束,返回 true。
时间复杂度 O©,空间复杂度 O©,其中 C 是数独中的空格数。本题中 C=81。
class Solution(object):def isValidSudoku(self, board):""":type board: List[List[str]]:rtype: bool"""row = [[False] * 9 for _ in range(9)]col = [[False] * 9 for _ in range(9)]sub = [[False] * 9 for _ in range(9)]for i in range(9):for j in range(9):c = board[i][j]if c == '.':continuenum = int(c) - 1k = i // 3 * 3 + j // 3if row[i][num] or col[j][num] or sub[k][num]:return Falserow[i][num] = Truecol[j][num] = Truesub[k][num] = Truereturn True