36.Valid Sudoku

题目大意：输入一个含有部分数据的数独数组，查验是否这个数组中的数是否满足数独条件，即行、列、小3*3框没有重复数值。37题是构造数独解。

法一：直接逐一判断即可。代码如下（耗时20ms）：

 1     public boolean isValidSudoku(char[][] board) {
 2         for(int i = 0; i < 9; i++) {
 3             for(int j = 0; j < 9; j++) {
 4                 if(check(i, j, board) == false) {
 5                     return false;
 6                 }
 7             }
 8         }
 9         return true;
10     }
11     private boolean check(int x, int y, char[][] board) {
12         if(board[x][y] != '.') {
13             for(int i = 0; i < 9; i++) {
14                 //判断行
15                 if(i != y && board[x][i] == board[x][y]) {
16                     return false;
17                 }
18                 //判断列
19                 if(i != x && board[i][y] == board[x][y]) {
20                     return false;
21                 }
22             }
23         }
24         x = x / 3 * 3;
25         y = y / 3 * 3;
26         HashSet<Character> set = new HashSet<Character>();
27         //判断3*3的框
28         for(int i = x; i < x + 3; i++) {
29             for(int j = y; j < y + 3; j++) {
30                 if(board[i][j] != '.') {
31                     if(set.contains(board[i][j])) {
32                         return false;
33                     }
34                     else {
35                         set.add(board[i][j]);
36                     }
37                 }
38             }
39         }
40         return true;
41     }

View Code

法二：下面的判断更快一些，直接判断。代码如下（耗时18ms）：

 1     public boolean isValidSudoku(char[][] board) {
 2         //第一个[]是本行，第二个[]是本行中是否存在num
 3         boolean[][] row = new boolean[9][9];
 4         //第二个[]是本列 ，第二个[]是本列中是否存在num
 5         boolean[][] col = new boolean[9][9];
 6         boolean[][] cell = new boolean[9][9];
 7         for(int i = 0; i < 9; i++) {
 8             for(int j = 0; j < 9; j++) {
 9                 if(board[i][j] != '.') {
10                     int num = board[i][j] - '1';
11                     //行，列，小三角是否有重复
12                     if(row[i][num] || col[num][j] || cell[3 * (i / 3) + j / 3][num]) {
13                         return false;
14                     }
15                     //标记
16                     row[i][num] = true;
17                     col[num][j] = true;
18                     cell[3 * (i / 3) + j / 3][num] = true;
19                 }
20             }
21         }
22         return true;
23     }

View Code