大佬教程收集整理的这篇文章主要介绍了LeetCode36. 有效的数独,大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
/**
* 请你判断一个 9x9 的数独是否有效。只需要 根据以下规则 ,
* 验证已经填入的数字是否有效即可。
* <p>
* 数字 1-9 在每一行只能出现一次。
* 数字 1-9 在每一列只能出现一次。
* 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。(请参考示例图)
* 数独部分空格内已填入了数字,空白格用 '.' 表示。
* <p>
* 注意:
* <p>
* 一个有效的数独(部分已被填充)不一定是可解的。
* 只需要根据以上规则,验证已经填入的数字是否有效即可。
*/
判断是否是一个有效的数独,需要满足三个条件
判断元素是否重复,自然而然想到散列表,因为它的去重功能
因为数独有9行9列 还有9个子数独,因此共需要27个hash表
9个用来判断每行的元素是否重复,9个用来判断每列的元素是否重复,另外9个用来判断每个子数独元素是否重复
对于行和列的判断比较容易,因为在遍历的过程中,其索引就是对应的hash表的索引,但是子数独的索引呢
哈希表的getOrDefault()函数用于判断散列表中是否存在某元素,如果存在则取出其键对应的值,如果不存在则拿到默认值
源码见下
/**
*
* @param board 二维数组
* @return 返回判断的结果
*/
public Boolean isValidSudoku(char[][] board) {
//创建三个hash数组分别用于判断每行 每列 每个子数独是否有重复元素
HashMap<Integer, Integer>[] row = new HashMap[9];
HashMap<Integer, Integer>[] col = new HashMap[9];
HashMap<Integer, Integer>[] box = new HashMap[9];
//hash表的键用于存储当前数字,值用于存储该数字出现的次数
//创建每个hash表
for (int i = 0; i < 9; i++) {
row[i] = new HashMap<Integer, Integer>();
col[i] = new HashMap<Integer, Integer>();
box[i] = new HashMap<Integer, Integer>();
}
//遍历board
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[i].length; j++) {
if (board[i][j] != '.') {
//当前数字
int num = (int) board[i][j];
//子数独对应的索引
int box_index = (i / 3) * 3 + j / 3;
//判断num是否已经在hash表中,如果在,则将其对应的值 + 1,否则将其加入哈希表
row[i].put(num, row[i].getOrDefault(num, 0) + 1);
col[j].put(num, col[j].getOrDefault(num, 0) + 1);
box[box_index].put(num, box[box_index].getOrDefault(num, 0) + 1);
//判断每个hash表中的元素个数是否超过 1 ,如果超过1 说明有重复的,直接返回
if (row[i].get(num) > 1 || col[j].get(num) > 1 || box[box_index].get(num) > 1){
return false;
}
}
}
}
return true;
}
以上是大佬教程为你收集整理的LeetCode36. 有效的数独全部内容,希望文章能够帮你解决LeetCode36. 有效的数独所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。