创办一个网站能够做那些事,物业公司和开发公司哪个好,wordpress修改数据库,gpl2 wordpress优质博文#xff1a;IT-BLOG-CN 一、题目
请你判断一个9 x 9的数独是否有效。只需要根据以下规则#xff0c;验证已经填入的数字是否有效即可。
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一… 优质博文IT-BLOG-CN 一、题目
请你判断一个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或者 ‘.’ 二、代码
思路
可以使用哈希表记录每一行、每一列和每一个小九宫格中每个数字出现的次数。只需要遍历数独一次在遍历的过程中更新哈希表中的计数并判断是否满足有效的数独的条件即可。
对于数独的第i行第j列的单元格其中0≤i,j9该单元格所在的行下标和列下标分别为i和j该单元格所在的小九宫格的行数和列数分别为⌊i/3⌋和⌊j/3⌋其中0≤⌊i/3⌋,⌊j/3⌋3。
由于数独中的数字范围是1到9因此可以使用数组代替哈希表进行计数。
具体做法是创建二维数组rows和columns分别记录数独的每一行和每一列中的每个数字的出现次数创建三维数组subboxes记录数独的每一个小九宫格中的每个数字的出现次数其中rows[i][index]、columns[j]和subboxes[⌊i/3⌋][⌊j/3⌋][index]分别表示数独的第i行第j列的单元格所在的行、列和小九宫格中数字index1出现的次数其中0≤index9对应的数字index1满足1≤index1≤9。
如果board[i][j]填入了数字n则将rows[i][n−1]、columns[j][n−1]和subboxes[⌊i/3⌋][⌊j/3⌋][n−1]各加1。如果更新后的计数大于1则不符合有效的数独的条件返回false。
如果遍历结束之后没有出现计数大于1的情况则符合有效的数独的条件返回true。
class Solution {public boolean isValidSudoku(char[][] board) {// X轴数字出现的次数int[][] rows new int[9][9];// y轴数字出现的次数int[][] columns new int[9][9];// 九宫格内出现的次数int[][][] subboxes new int[3][3][9];// 遍历 9*9 表格for (int i 0; i 9; i ) {for (int j 0; j 9; j) {char element board[i][j];if (element ! .) {int index element - 1;// x轴中的元素1rows[i][index];// y轴中的元素1columns[j][index];// 九宫格中的元素1subboxes[i/3][j/3][index];//次数大于1直接退出if (rows[i][index] 1 || columns[j][index] 1 || subboxes[i/3][j/3][index] 1) return false;}}}return true;}
}
