Valid Sudoku

標(biāo)簽： C++ 算法 LeetCode

每日算法——leetcode系列

問題 Valid Sudoku

Difficulty: Easy

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

<small> A partially filled sudoku which is valid.</small>
Note:
A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        
    }
};

翻譯

數(shù)獨有效性驗證

難度系數(shù)：容易

根據(jù)Sudoku Puzzles - The Rules規(guī)則來判定數(shù)獨的有效性。
數(shù)獨板可以被部分填充，空格部分用'.'來填充。

注意
不一定要這個數(shù)獨是有解，只要當(dāng)前已經(jīng)填充的數(shù)字是合法的就可以。

思路

玩游戲先弄懂規(guī)則最重要。數(shù)獨好像國處很受歡迎，但我還沒見過人玩。

由于只要當(dāng)前已經(jīng)填充的數(shù)字是合法的就可以，因此只需要判斷9*9網(wǎng)格的每一行、每一列、9個小九宮格是否合法。如果在每一行、每一列、每個9個小九宮格內(nèi)有重復(fù)數(shù)字則不合法。

三個循環(huán)，各判斷行、列、小九宮格是否合法，為了節(jié)省時間，可以用bitmap來代表這個數(shù)字是否出現(xiàn)，bitmap可以用數(shù)組，只有0到9的數(shù)字為index，false和true為值，出現(xiàn)過值為true， 關(guān)于vector里面裝bool類型，在<<Effective STL>> 這本書里有說明，最好不要在vector裝bool類型。
由于有規(guī)律，三個在不同循環(huán)判斷的可以寫在一個里面。

代碼

class Solution {
public:
    bool isValidSudoku(vector<vector<char> > &board) {
        const int cnt = 9;
        bool rowMap[cnt][cnt] = {false};
        bool colMap[cnt][cnt] = {false};
        bool smallBoardMask[cnt][cnt] = {false};
        
        for(int i = 0; i < board.size(); ++i){
            for (int j = 0; j < board[i].size(); ++j){
                if (board[i][j] == '.'){
                    continue;
                }
                int idx =  board[i][j] - '0' - 1;
                
                // 行
                if (rowMap[i][idx] == true){
                    return false;
                }
                rowMap[i][idx] = true;
                
                // 列
                if (colMap[j][idx] == true) {
                    return false;
                }
                colMap[j][idx] = true;
                
                // 小區(qū)域
                int area = (i/3) * 3 + (j/3);
                if (smallBoardMask[area][idx] == true) {
                    return false;
                }
                smallBoardMask[area][idx] = true;
            }
        }
        
        return true;
    }
};