【LeetCode】No.36. Valid Sudoku -- Java Version

题目链接： https://leetcode.com/problems/valid-sudoku/

1. 题目介绍（有效数独）

Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

【Translate】： 确定9 x 9的 sudoku board是否有效。仅需要根据以下规则对填充的单元进行验证：

1. Each row must contain the digits 1-9 without repetition.
2. Each column must contain the digits 1-9 without repetition.
3. Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.

【Translate】：

1. 每一行必须包含数字1 ~ 9，不能重复。
2. 每列必须包含数字1 ~ 9，不能重复。
3. 网格的9个3 × 3子框中的每一个都必须包含数字1-9，不能重复。

Note:

• A Sudoku board (partially filled) could be valid but is not necessarily solvable.
• Only the filled cells need to be validated according to the mentioned rules.

【Translate】：

• Sudoku board (部分填满)可能是有效的，但不一定能解决。
• 只有填充好的单元才需要根据上述规则进行验证。

【测试用例】：


【约束】：

2. 题解 2.1 HashSet()去重 – O(n)

StefanPochmann 提供的题解 Short+Simple Java using Strings，想法非常好，直接一波遍历，利用HashSet自动去重的特性，反向求解，谁见了不说一声xiuer！

public boolean isValidSudoku(char[][] board) {
    Set seen = new HashSet();
    for (int i=0; i<9; ++i) {
        for (int j=0; j<9; ++j) {
            char number = board[i][j];
            if (number != '.')
                if (!seen.add(number + " in row " + i) ||
                    !seen.add(number + " in column " + j) ||
                    !seen.add(number + " in block " + i/3 + "-" + j/3))
                    return false;
        }
    }
    return true;
}

Lorraine921 提供的题解 Shared my concise Java code，目前在Discuss中的Most Vote排名第二，仅次于StefanPochmann 。该题解的思想内核和上面StefanPochmann 的是一样的，但是让人疑惑的是速度为什么会快这么多？是分开存储搜索速度相对会更快一点，还是因为add()添加的元素大小的耗时差距比较大？

    public boolean isValidSudoku(char[][] board) {
        for(int i = 0; i<9; i++){
            HashSet<Character> rows = new HashSet<Character>();
            HashSet<Character> columns = new HashSet<Character>();
            HashSet<Character> cube = new HashSet<Character>();
            for (int j = 0; j < 9;j++){
                if(board[i][j]!='.' && !rows.add(board[i][j]))
                    return false;
                if(board[j][i]!='.' && !columns.add(board[j][i]))
                    return false;
                int RowIndex = 3*(i/3);
                int ColIndex = 3*(i%3);
                if(board[RowIndex + j/3][ColIndex + j%3]!='.' && !cube.add(board[RowIndex + j/3][ColIndex + j%3]))
                    return false;
            }
        }
        return true;
    }

2.2 Bitwise operator – O(n)

hsmishka 提供的题解 Yet another java 2ms solution，其思想是跟踪每一行、每列和3x3块(桶)。整数中的每1位表示:在这行/列/桶中找到了对应于这个位置的数字。公式(i / 3) * 3 + j / 3产生给定行和列的桶的索引。不得不说，位运算永远最神速！hset[i]用于当前行的重复元素检索，因为是|运算，所以它最终会包含该行所有数字对应的位数，逐次遍历就能筛选出是否有重复元素，其它case也同理。

    public boolean isValidSudoku(char[][] board) {
        int [] vset = new int [9];  // 列
        int [] hset = new int [9];  // 行
        int [] bckt = new int [9];  // 3x3块
        int idx = 0;
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    idx = 1 << (board[i][j] - '0') ;
                    if ((hset[i] & idx) > 0 ||
                        (vset[j] & idx) > 0 ||
                        (bckt[(i / 3) * 3 + j / 3] & idx) > 0) return false;
                    hset[i] |= idx;
                    vset[j] |= idx;
                    bckt[(i / 3) * 3 + j / 3] |= idx;
                }
            }
        }
        return true;
    }

3. 可参考

[1] Java™ Platform Standard Ed. 7 Class HashSet
[2] Java HashSet类