LeetCode第[36]题(Java)：Valid Sudoku

题目：有效的数独表

难度：Medium

题目内容：

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

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

A partially filled sudoku which is valid.

The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

Example 1:

Input:
[
  ["5","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
Output: true

Example 2:

Input:
[
  ["8","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being 
    modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.

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.
The given board contain only digits 1-9 and the character '.'.
The given board size is always 9x9.

翻译：简单翻译下就是，给出一张数独表，判断是否有效。

不需要判断是否有解，只需判断它的三个标准内已经出现的数字是否唯一即可。

我的思路：本题其实不难，不过题目的意思很难懂，仔细理解了就好了。

　　　　在三个标准内判断是否唯一，那么就需要三个数组，并且每一个数组都应该是二维的，第一维表示是第几个长条（方形），第二维度表示是长条（方形）内的第几个元素。

　　　　三个标准分别是，行、列、块。

　　　　对数独表的每一个元素进行循环，每一个元素都在三个标准内都有对应的元素，每次循环都对此三个标准内对应的值设置为true（已经使用），如果发现对应的值已经被设置为true，则立即返回flase表明此表是无效的。

　　　　当前值减去“1”则能表示第二维度的值

问题在于如何用元素在数独表的位置【i】【j】表示三个标准第一维度的值：

行：【i】

列：【j】

块：行数与列数不一样，行数对三的商决定了是从第几个三开始往后数，列数决定了数几个所以为【i/3*3 + j/3】

MyCode：

 1     public boolean isValidSudoku(char[][] board) {
 2         
 3        boolean[][] row = new boolean[9][9];
 4        boolean[][] column = new boolean[9][9];
 5        boolean[][] block = new boolean[9][9];
 6        
 7        for(int i = 0;i<9;i++){
 8            for(int j=0;j<9;j++){
 9                 int c = board[i][j] - '1';       
10                 if(board[i][j]=='.'){
11                     continue;
12                 }
13                 int loc = i/3*3 + j/3;
14                 if(row[i][c]||column[j][c]||block[loc][c]){
15                     return false;
16                 }
17                 row[i][c] = column[j][c] = block[loc][c] = true;
18            }
19        }
20        return true;
21     }

我的算法复杂度：O（N²）

编码过程中出现的问题：

1、一开始想用一维数组，然后每个元素都是set，用set来判断，但是发现操作起来比较麻烦。当已经知道要放入的元素的范围，且范围不大的时候应该用数组代替Set。

2、想第二维度如何取值的时候想了很久。当元素为char或者String的数字，用来计数（判唯一）的时候，可以考虑减去“<最小值>”，转为相对值。此处最小值为1。

答案代码：

略，和我的一样。