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

题目：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]=true
            col[j][t]=true
            single_range[i/3][j/3][t]=true
        }
    }
    return true
}