AlgoPressAppearance
0036-有效的数独
https://leetcode.cn/problems/valid-sudoku
请你判断一个9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。
数字1-9在每一行只能出现一次。 数字1-9在每一列只能出现一次。 数字1-9在每一个以粗实线分隔的3x3宫内只能出现一次。（请参考示例图）
注意：
- 一个有效的数独（部分已被填充）不一定是可解的。
- 只需要根据以上规则，验证已经填入的数字是否有效即可。
- 空白格用'.'表示。
示例 1：
输入：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"]]
输出：true
示例 2：
输入：board =
[["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 存在, 因此这个数独是无效的。
提示：
board.length == 9
board[i].length == 9
board[i][j] 是一位数字（1-9）或者 '.'
思路1：暴力法
依次检测 行，列，9宫格是否合法
参考代码
csharp
public class Solution {
private bool IsValid(char[][] board, int row, int col, int endRow, int endCol){
Dictionary<int,int> dict = new Dictionary<int,int>();
for(int i=row; i<=endRow; i++){
for(int j=col; j<=endCol; j++){
if(board[i][j] != '.'){
if(dict.ContainsKey(board[i][j])){
return false;
}
dict.Add(board[i][j],board[i][j]);
}
}
}
return true;
}
public bool IsValidSudoku(char[][] board) {
//验证行,列
for(int i=0; i<board.Length; i++){
if(!IsValid(board,i,0,i,8)){
return false;
}
if(!IsValid(board,0,i,8,i)){
return false;
}
}
//验证9宫格
for(int i=0; i<3; i++){
for(int j=0; j<3; j++){
int startRow = i * 3;
int startCol = j * 3;
if(!IsValid(board,startRow,startCol,startRow+2,startCol+2)){
return false;
}
}
}
return true;
}
}
思路2：hash表缓存
一次遍历，将行对应的数字缓存，列对应的数字缓存，9宫格对应的数字缓存，如果发现缓存次数超过1，则返回false，循环结束说明合法，返回true 这里Hash表直接用数组表示 注意 board[i][j] 需要 ToString() 在转回为数字，否则会按照 ASCII 转换为数字
csharp
public class Solution {
public bool IsValidSudoku(char[][] board) {
int[,] row = new int[9,9]; //第一个表示行数，第二个表示数字的个数
int[,] col = new int[9,9]; //第一个表示列数，第二个表示数字的个数
int[,,] subboard = new int[3,3,9]; //前面表示棋盘坐标，后面表示个数
for(int i=0; i < 9; i++){
for(int j=0; j < 9; j++){
if(board[i][j] != '.'){
//Console.WriteLine("checking i:{0},j:{1}",i,j);
int num = Convert.ToInt32(board[i][j].ToString())-1;
//Console.WriteLine("checking num:{0}",num);
row[i,num]++;
col[j,num]++;
subboard[i/3,j/3,num]++;
if(row[i,num] > 1 || col[j,num] > 1 || subboard[i/3,j/3,num] > 1){
return false;
}
}
}
}
return true;
}
}
复习 : 20220604
csharp
public class Solution {
public bool IsValidSudoku(char[][] board) {
//创建哈希表缓存保存数据
int[,] cols = new int[9,10];
int[,] rows = new int[9,10];
int[,,] subs = new int[3,3,10];
for(int i=0; i<9; i++){
for(int j=0; j<9; j++ ){
if(board[i][j] != '.'){
int num = board[i][j] - '0';
rows[i,num] += 1;
cols[j,num] += 1;
subs[i/3,j/3,num] += 1;
if(rows[i,num] > 1 || cols[j,num] > 1 || subs[i/3,j/3,num] > 1 ){
return false;
}
}
}
}
return true;
}
}