北京网站建设比较好的公司,网站目录有什么意义,wordpress友情链接插件,博物馆网站建设LeetCode 36. 有效的数独
难度#xff1a;middle\color{orange}{middle}middle 题目描述
请你判断一个 9x99 x 99x9 的数独是否有效。只需要 根据以下规则 #xff0c;验证已经填入的数字是否有效即可。
数字 1−91-91−9 在每一行只能出现一次。数字 1−91-91−9 在每一列…LeetCode 36. 有效的数独
难度middle\color{orange}{middle}middle 题目描述
请你判断一个 9x99 x 99x9 的数独是否有效。只需要 根据以下规则 验证已经填入的数字是否有效即可。
数字 1−91-91−9 在每一行只能出现一次。数字 1−91-91−9 在每一列只能出现一次。数字 1−91-91−9 在每一个以粗实线分隔的 3x33x33x3 宫内只能出现一次。请参考示例图
注意
一个有效的数独部分已被填充不一定是可解的。只需要根据以上规则验证已经填入的数字是否有效即可。空白格用 ′.′.′.′ 表示。
示例 1 输入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]]
输出true示例 2
输入board
[[8,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]]
输出false
解释除了第一行的第一个数字从 5 改为 8 以外空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。提示
board.length9board.length 9board.length9board[i].length9board[i].length 9board[i].length9board[i][j]board[i][j]board[i][j] 是一位数字1−91-91−9或者 ′.′.′.′ 算法
(暴力枚举)
判断每一行是否存在相同的数字。判断每一列是否存在相同的数字。判断每一个单独的小方格是否存在相同的数字。
复杂度分析 时间复杂度O(1)O(1)O(1)数独共有 81 个单元格只需要对每个单元格遍历即可。 空间复杂度 : O(1)O(1)O(1)只需要一个判重数组即可。
C 代码
class Solution {
public:bool isValidSudoku(vectorvectorchar board) {bool st[9];//判断行for (int i 0; i 9; i ) {memset(st, 0, sizeof st);for (int j 0; j 9; j ) {if (board[i][j] ! .) {int t board[i][j] - 1;if (st[t]) return false;st[t] true;}}}//判断列for (int i 0; i 9; i ) {memset(st, 0, sizeof st);for (int j 0; j 9; j ) {if (board[j][i] ! .) {int t board[j][i] - 1;if (st[t]) return false;st[t] true;}}}//判断小方格for (int i 0; i 9; i 3) {for (int j 0; j 9; j 3) {memset(st, 0, sizeof st);for (int x 0; x 3; x ) {for (int y 0; y 3; y ) {if (board[i x][j y] ! .) {int t board[i x][j y] - 1;if (st[t]) return false;st[t] true;}}}}}return true;}
};
