Valid Sudoku

NO IMAGE
1 Star2 Stars3 Stars4 Stars5 Stars 給文章打分!
Loading...

每日演算法——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 '.'

翻譯

數獨有效性驗證

難度係數:容易

根據Sudoku Puzzles – The Rules規則來判定數獨的有效性。
數獨板可以被部分填充,空格部分用’.’來填充。

注意
不一定要這個數獨是有解,只要當前已經填充的數字是合法的就可以。

思路

玩遊戲先弄懂規則最重要。數獨好像國處很受歡迎,但我還沒見過人玩。

由於只要當前已經填充的數字是合法的就可以,因此只需要判斷9*9網格的每一行、每一列、9個小九宮格是否合法。如果在每一行、每一列、每個9個小九宮格內有重複數字則不合法。

三個迴圈,各判斷行、列、小九宮格是否合法,為了節省時間,可以用bitmap來代表這個數字是否出現,bitmap可以用陣列,只有0到9的數字為index,false和true為值,出現過值為true, 關於vector裡面裝bool型別,在<<Effective STL>> 這本書裡有說明,最好不要在vector裝bool型別。
由於有規律,三個在不同迴圈判斷的可以寫在一個裡面。

程式碼

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;
// 小區域
int area = (i/3) * 3   (j/3);
if (smallBoardMask[area][idx] == true) {
return false;
}
smallBoardMask[area][idx] = true;
}
}
return true;
}
};

相關文章

程式語言 最新文章