[leetcode] Valid Sudoku


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 '.'.

A partially filled sudoku which is valid.

Note:
A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.

tag: hashtable

给定一个数独,验证每行是否合法,每列是否合法,每个9宫格是否合法。

我们把这三个验证写在三个函数中。

tag中有hashtable,我想是想让我们在检测某个数字是否重复时,用哈希表来检测。但我们也可以用一个bool型的数组来简单标记是否重复,这样可以更简单一些。

需要指出的是,在验证每个9宫格是否合法时,我们需要把i,j映射到rowOffset和columnOffset,这样当ij遍历[0,9),[0,9)时,保证我们可以读取到正确的对应格子的值。

class Solution {
public:
    bool isValidSudoku(vector<vector<char> > &board) {
        return checkRow(board) && checkColumn(board) && checkCell(board);
    }
    bool checkCell(vector<vector<char > > &board){
        bool flag[9];
        for(int i = 0; i < 9; i++){
            for(int j = 0; j < 9; j++){
                flag[j] = false;//not visited
            }
            for(int j = 0; j < 9; j++){
                int columnOffset =  i % 3 * 3;
                int rowOffset = i / 3 * 3;
                char c = board[rowOffset + j / 3][columnOffset + j % 3];
                if(c == '.'){
                    continue;
                }
                else{
                    if(flag[c - '1'] == true){//duplicated
                        return false;
                    }
                    else{
                        flag[c - '1'] = true;
                    }
                }
            }
        }
        return true;
    }
    bool checkColumn(vector<vector<char> > &board){
        bool flag[9];
        for(int i = 0; i < 9; i++){
            for(int j = 0; j < 9; j++){
                flag[j] = false;
            }
            for(int j = 0; j < 9; j++){
                char c = board[j][i];
                if(c == '.'){
                    continue;
                }
                else{
                    if(flag[c - '1'] == true){
                        return false;
                    }
                    else{
                        flag[c - '1'] = true;
                    }
                }
            }
        }
        return true;
    }
    bool checkRow(vector<vector<char> > &board ){
        bool flag[9];
        for(int i = 0; i < 9; i++){
            for(int j = 0; j < 9; j++){
                flag[j] = false;
            }
            for(int j = 0; j < 9; j++){
                char c = board[i][j];
                if(c == '.'){
                    continue;
                }
                else{
                    if(flag[c - '1'] == true){
                        return false;
                    }
                    else{
                        flag[c - '1'] = true;
                    }
                }
            }
        }
        return true;
    }
};

Untitled

Leave a comment

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.