网站制作公司哪儿济南兴田德润有活动吗,飞鸽网站建设,o2o网站建设新闻,宁波免费网页制作模板题目描述#xff1a;
请你判断一个 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 9board[i].length 9board[i][j] 是一位数字1-9或者 .
通过次数
396.1K
提交次数
627.9K
通过率
63.1%
思路和题解
题目已经给出了数独有效的三个规则并且这三个规则都满足才能保证数独有效我们可以针对每一个规则都判断一遍。对于规则1我们可以把每一行都判断一遍由于给出的是一个不完整的数独所以只要查看每一行是否有重复即可不用判断是否每一个都刚好出现一次。对于规则2只是把行换成了列而已。对于规则3我们只要判断每个九宫格就行了。下面是这种方法的代码
class Solution {
public:bool isValidSudoku(vectorvectorchar board) {//判断3*3宫格int i0,j0;int row0,col0;while(row7){col0;while(col7){int visited[10]{0};for(irow;irow3;i){for(jcol;jcol3;j)if(board[i][j]1board[i][j]9)visited[board[i][j]-0];}for(i1;i9;i)if(visited[i]1)return false;col3;}row3;}//判断每一行for(row0;row9;row){int visited[10]{0};for(col0;col9;col){if(board[row][col]1board[row][col]9)visited[board[row][col]-0];}for(i1;i9;i)if(visited[i]1)return false;}//判断每一列for(col0;col9;col){int visited[10]{0};for(row0;row9;row){if(board[row][col]1board[row][col]9)visited[board[row][col]-0];}for(i1;i9;i)if(visited[i]1)return false;}return true;}
};
对于上述的方法如果运气不好的话我们要遍历三次九宫格才能判断出一个九宫格是否有效。如果我们用三个数组分别记住每一行的数字1-9出现的次数、每一列的数字1-9出现的次数、每一个九宫格的数字1-9出现的次数每次遍历的时候如果遍历的是.那就直接遍历下一个如果出现的是数字num那么就对应行的数字1对应列的数字1对应九宫格的数字1在1后如果对应行的数字1或对应列的数字1或对应九宫格的数字1那就放回false。遍历结束返回true。由于官方题解的代码我和的思路差不多而且可读性更强所以我就直接给出了官方题解代码。
class Solution {
public:bool isValidSudoku(vectorvectorchar board) {int rows[9][9];int columns[9][9];int subboxes[3][3][9];memset(rows,0,sizeof(rows));memset(columns,0,sizeof(columns));memset(subboxes,0,sizeof(subboxes));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;}
};
