(LeetCode 每日一题) 36. 有效的数独 (数组、哈希表)

思路：哈希表+数组，时间复杂度0(n^2)。

用哈希表来维护数组元素在每行、每列、和3x3宫格内的分布情况。

C++版本：

class Solution {
public:bool isValidSudoku(vector<vector<char>>& board) {vector<vector<bool>> row(9,vector<bool>(9,false));vector<vector<bool>> col(9,vector<bool>(9,false));bool single_range[3][3][9];memset(single_range,false,sizeof single_range);for(int i=0;i<9;i++){for(int j=0;j<9;j++){char c=board[i][j];if(c=='.') continue;int t=c-'1';if(row[i][t]==true || col[j][t]==true || single_range[i/3][j/3][t]==true){return false;}row[i][t]=true;col[j][t]=true;single_range[i/3][j/3][t]=true;}}return true;}
};

JAVA版本：

class Solution {public boolean isValidSudoku(char[][] board) {boolean[][] row=new boolean[9][9];boolean[][] col=new boolean[9][9];boolean[][][] single_range=new boolean[3][3][9];for(int i=0;i<9;i++){for(int j=0;j<9;j++){char c=board[i][j];if(c=='.') continue;int t=c-'1';if(row[i][t]==true || col[j][t]==true || single_range[i/3][j/3][t]==true){return false;}row[i][t]=true;col[j][t]=true;single_range[i/3][j/3][t]=true;}}return true;}
}

GO版本：

func isValidSudoku(board [][]byte) bool {row:=[9][9]bool{}col:=[9][9]bool{}single_range:=[3][3][9]bool{}for i:=0;i<9;i++{for j:=0;j<9;j++{c:=board[i][j]if c=='.' {continue}t:=c-'1';if row[i][t]==true || col[j][t]==true || single_range[i/3][j/3][t]==true {return false}row[i][t]=truecol[j][t]=truesingle_range[i/3][j/3][t]=true}}return true
}