一、题目描述
判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
上图是一个部分填充的有效的数独。
数独部分空格内已填入了数字，空白格用 '.' 表示。
示例 1: 输入: [ ["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"] ] 输出: true
示例 2: 输入: [ ["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"] ] 输出: false
解释: 除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。 说明:
一个有效的数独（部分已被填充）不一定是可解的。 只需要根据以上规则，验证已经填入的数字是否有效即可。 给定数独序列只包含数字 1-9 和字符 '.' 。 给定数独永远是 9x9 形式的。
二、解题思路
1、验证数字 1-9 在每一行只能出现一次。
2、验证数字 1-9 在每一列只能出现一次。
3、验证数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
三、代码
代码语言：javascript复制package is_valid_sudoku;
import java.util.HashMap;
import java.util.Map;
public class Solution {
public boolean isValidSudoku(char[][] board) {
int len=board.length;
for(int i=0;i<len;i ){
if(!checkRow(board,i)){
System.out.println("第" i "行验证失败");
return false;
}else{
System.out.println("第" i "行验证成功");
}
}
for(int i=0;i<len;i ){
if(!checkColumn(board,i)){
System.out.println("第" i "列验证失败");
return false;
}
else{
System.out.println("第" i "列验证成功");
}
}
for(int i=0;i<3;i ) {
for(int j=0;j<3;j ){
if (!checkMatrix(board, i*3, j*3)) {
return false;
}
else{
System.out.println("第" i*3 "," j*3 "矩阵验证成功");
}
}
}
return true;
}
public boolean checkRow(char[][] board,int row){
int len=board.length;
Map<Character, Integer> map=new HashMap<>();
for(int i=0;i<10;i ){
map.put(Character.forDigit(i,10),0);
}
for(int i=0;i<len;i ){
if(board[row][i]!='.'){
if(map.get(board[row][i])>=1){
return false;
}else{
map.put(board[row][i],map.get(board[row][i]) 1);
}
}
}
return true;
}
public boolean checkColumn(char[][] board,int column){
int len=board.length;
Map<Character, Integer> map=new HashMap<>();
for(int i=0;i<10;i ){
map.put(Character.forDigit(i,10),0);
}
for(int i=0;i<len;i ){
if(board[i][column]!='.'){
if(map.get(board[i][column])>=1){
return false;
}else{
map.put(board[i][column],map.get(board[i][column]) 1);
}
}
}
return true;
}
public boolean checkMatrix(char[][] board,int rowStart,int columnStart){
int len=board.length;
Map<Character, Integer> map=new HashMap<>();
for(int n=0;n<10;n ){
map.put(Character.forDigit(n,10),0);
}
int rowEnd=rowStart 3;
int columnEnd=columnStart 3;
for(int i=rowStart;i<rowEnd;i ){
for(int j=columnStart;j<columnEnd;j ) {
if(board[i][j]!='.'){
if (map.get(board[i][j]) >= 1) {
return false;
} else {
map.put(board[i][j], map.get(board[i][j]) 1);
System.out.println(map);
}
}
}
}
System.out.println(map);
return true;
}
public static void main(String[] args) {
Solution solution=new Solution();
char[][] board={
{'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'}
};
System.out.println(solution.isValidSudoku(board));
}
}四、复杂度分析
时间复杂度：O(1)，只对 81 个单元格进行了3次迭代。
空间复杂度：O(1)，只需要常数空间存放若干变量。
