T36. Valid Sudoku【Medium】
题目
这是一道数独题,如何确定数独有效,参考 数独规则
数独板可以是部分填充的,其中空单元填充字符'.'。
以上是一个部分填充了的有效的数独游戏。
注意:
有效的 数独游戏 板(部分填充)不一定可解。需要验证的只有已经填充的单元格。
思路
首先,审题,不用算是否可解,那题目一下子就变得简单了起来,这时候就是理解规则并且按规则来判断就可以了。
总的来说,要判断三个方面:
① 同行有没有重复
② 同列有没有重复
③ 同九宫格有没有重复
(不知道为什么的看数独规则哈:))
代码很巧妙,
① 通过 给数字编码(加标签)来限定范围
② 依靠了 HashSet 来判断重复
编码方式:
- 第 7 行的数字 '4' 编码以后是 "(4)7"
- 第 7 列的数字 '4' 编码以后是 "7(4)"
- 右上方九宫格(第 1 行 第 3 列)的数字 '4' 编码以后是 "0(4)2"
具体看代码以及注释~
代码
代码取自 Top Solution,稍作注释
public boolean isValidSudoku(char[][] board) {
Set seen = new HashSet();
for (int i=0; i<9; ++i) {
for (int j=0; j<9; ++j) {
if (board[i][j] != '.') {
//给数字加()
String b = "(" + board[i][j] + ")";
//先编码再加入数组,然后若重复,则 add() 方法返回false,然后进入 if,return false
if (!seen.add(b + i) || !seen.add(j + b) || !seen.add(i/3 + b + j/3))
return false;
}
}
}
return true;
}
补充
① 先补充一下 HashSet 的 add() 方法:
public boolean add(Object o)方法用来在Set中添加元素,当元素值重复时则会立即返回false,如果成功添加的话会返回true。
② 然后总结收获 (*•̀ㅂ•́)و。
这题让我学到了:
-
判断是否重复可以用 HashSet 的 add() 方法的返回值来判断。
-
同时,自己制定规则通过给 String 加上特定编码也是一种简单好用的分类方法。
网友评论