网站访客qq抓取统计系统,网站建设 云计算,网站建设小程序,wordpress源码商城模板一、题目描述
请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 #xff0c;验证已经填入的数字是否有效即可。
数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。#xff08;请参考示例图…一、题目描述
请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 验证已经填入的数字是否有效即可。
数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。请参考示例图
注意
一个有效的数独部分已被填充不一定是可解的。只需要根据以上规则验证已经填入的数字是否有效即可。空白格用 ‘.’ 表示。
二、测试用例
示例 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.length 9
board[i].length 9
board[i][j] 是一位数字1-9或者 .三、解题思路
基本思路 一力破万法检查是否满足数独的三个条件就可以了。具体思路一次遍历就可以检查三个条件就是需要一些技巧。 行唯一判断每一行中出现的数字是否唯一 【正常遍历】列唯一判断每一列中出现的数字是否唯一 【行列交换】九宫格唯一判断每一个九宫格中出现的数字是否唯一 【特殊映射】
四、参考代码
时间复杂度 O ( 1 ) \Omicron(1) O(1)【数独是固定大小的所以都是常数级复杂度】 空间复杂度 O ( 1 ) \Omicron(1) O(1)【数独是固定大小的所以都是常数级复杂度】
class Solution {
public:bool isValidSudoku(vectorvectorchar board) {int n board.size(), m board[0].size();for (int i 0; i n; i) {vectorvectorbool num(3, vectorbool(m, false));for (int j 0; j m; j) { // 行唯一if (board[i][j] ! .) {if (num[0][board[i][j] - 1]) {return false;} else {num[0][board[i][j] - 1] true;}}if (board[j][i] ! .) { // 列唯一if (num[1][board[j][i] - 1]) {return false;} else {num[1][board[j][i] - 1] true;}}int r i / 3 * 3 j / 3, c (i % 3) * 3 j % 3;if (board[r][c] ! .) { // 九宫格唯一if (num[2][board[r][c] - 1]) {return false;} else {num[2][board[r][c] - 1] true;}}}}return true;}
};
