美文网首页
每天一题LeetCode【第27天】

每天一题LeetCode【第27天】

作者: 草稿纸反面 | 来源:发表于2017-02-16 00:01 被阅读72次

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

    相关文章

      网友评论

          本文标题:每天一题LeetCode【第27天】

          本文链接:https://www.haomeiwen.com/subject/nqscwttx.html