每天一题LeetCode【第27天】

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 加上特定编码也是一种简单好用的分类方法。