leetcode36.Valid Sudoku

发表于 更新于 分类于 ，

题目要求

Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.
The Sudoku board could be partially filled, where empty cells are filled with the character '.'.
    
Note:
A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.

一个数独合法的标准如下

  1. 每一行每一列必须包含1-9之间的每一个数字（包括1和9）
  2. 每一个小的正方形矩阵中必须包含1-9之间的每一个数字（包括1和9）

所以总体思路就是遍历数独，判断行、列以及每一个小的正方形中的数字是否合法

如图所示的数独就是一个合法的数独

思路一：使用StringBuilder API

假设我们持有已经遍历过的小方格所在的行列以及正方形的所有值，那么我们只需要判断当前值在自己所在的行、列和小正方形是否有重复。如果重复则不合法，否则极为合法。
在这里我们使用StringBuilder数组代替Map作为存储行列和小正方形的值得数据结构。我们只需要利用StringBuilder的API来判断当前的值是否有重复即可。

注：如果字符串在新建以后被更改的可能性较大，建议不要使用String而是使用StringBuilder，可以明显提高效率

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public boolean isValidSudoku(char[][] board) {
    //9个StringBuilder分别代表9个小正方形
    StringBuilder[] squares = new StringBuilder[]{new StringBuilder(""),new StringBuilder(""),new StringBuilder(""),new StringBuilder(""),new StringBuilder(""),new StringBuilder(""),new StringBuilder(""),new StringBuilder(""),new StringBuilder("")};
    //9列
    StringBuilder[] columns = new StringBuilder[]{new StringBuilder(""),new StringBuilder(""),new StringBuilder(""),new StringBuilder(""),new StringBuilder(""),new StringBuilder(""),new StringBuilder(""),new StringBuilder(""),new StringBuilder("")};
    //当前行
    StringBuilder line;
    for(int i = 0 ; i<board.length ; i++){
        line = new StringBuilder();
        for(int j = 0 ; j<board[i].length ; j++){
            
            if(board[i][j] == '.'){
                continue;
            }
            String currentChar = board[i][j]+"";
            if(line.indexOf(currentChar) != -1){
                return false;
            }
            if(columns[j].indexOf(currentChar) != -1){
                return false;
            }
            //计算当前小方格所在的正方形
            int squareNum = (i/3)*3 + (j/3);
            if(squares[squareNum].indexOf(currentChar) != -1){
                return false;
            }
            line.append(currentChar);
            columns[j].append(currentChar);
            squares[squareNum].append(currentChar);
        }
    }
    return true;
}

思路二：利用下标

上一个方法的思路是相当直观的。我存储这所有的行列小正方形的情况，并判断当前值是否重复。但是，很明显我们并不需要一直关注所有的行和列，这样当我们关注某一行或者某一列时，无需存储其他的行列或是小正方形的值。所以我们转而利用二重循环的下标来表示行、列和小正方形，减少不必要的数据存储，每一次内循环都代表着对一行或是一列或是一个小正方形的遍历。外循环则代表对下一行，下一列和下一个小正方形的遍历。
代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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;
            
}