[LeetCode] 36. Valid Sudoku 驗(yàn)證數(shù)獨(dú)

Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

1. Each row must contain the digits 1-9without repetition.
2. Each column must contain the digits 1-9 without repetition.
3. Each of the 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.

A partially filled sudoku which is valid.

The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

Example 1:

Input:

[

     ["5","3",".",".","7",".",".",".","."], 

     ["6",".",".","1","9","5",".",".","."],

     [".","9","8",".",".",".",".","6","."],

     ["8",".",".",".","6",".",".",".","3"],

     ["4",".",".","8",".","3",".",".","1"],

     ["7",".",".",".","2",".",".",".","6"],

     [".","6",".",".",".",".","2","8","."],

     [".",".",".","4","1","9",".",".","5"], 

     [".",".",".",".","8",".",".","7","9"]

]

Output: true

Example 2:

Input:

[

    ["8","3",".",".","7",".",".",".","."],

    ["6",".",".","1","9","5",".",".","."],

    [".","9","8",".",".",".",".","6","."],

    ["8",".",".",".","6",".",".",".","3"],

    ["4",".",".","8",".","3",".",".","1"],

    ["7",".",".",".","2",".",".",".","6"],

    [".","6",".",".",".",".","2","8","."],

    [".",".",".","4","1","9",".",".","5"],

    [".",".",".",".","8",".",".","7","9"]

]

Output: false

Explanation: Same as Example 1, except with the 5 in the top left corner being

modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.

Note:

• A Sudoku board (partially filled) could be valid but is not necessarily solvable.
• Only the filled cells need to be validated according to the mentioned rules.
• The given board contain only digits 1-9and the character '.'.
• The given board size is always 9x9.

這道題讓驗(yàn)證一個(gè)方陣是否為數(shù)獨(dú)矩陣，想必?cái)?shù)獨(dú)游戲我們都玩過(guò)，就是給一個(gè) 9x9 大小的矩陣，可以分為9個(gè) 3x3 大小的矩陣，要求是每個(gè)小矩陣內(nèi)必須都是1到9的數(shù)字不能有重復(fù)，同時(shí)大矩陣的橫縱列也不能有重復(fù)數(shù)字，是一種很經(jīng)典的益智類游戲，經(jīng)常在飛機(jī)上看見有人拿著紙筆在填數(shù)，感覺(jué)是消磨時(shí)光的利器。這道題給了一個(gè)殘缺的二維數(shù)組，讓我們判斷當(dāng)前的這個(gè)數(shù)獨(dú)數(shù)組是否合法，即要滿足上述的條件。判斷標(biāo)準(zhǔn)是看各行各列是否有重復(fù)數(shù)字，以及每個(gè)小的 3x3 的小方陣?yán)锩媸欠裼兄貜?fù)數(shù)字，如果都無(wú)重復(fù)，則當(dāng)前矩陣是數(shù)獨(dú)矩陣，但不代表待數(shù)獨(dú)矩陣有解，只是單純的判斷當(dāng)前未填完的矩陣是否是數(shù)獨(dú)矩陣。那么根據(jù)數(shù)獨(dú)矩陣的定義，在遍歷每個(gè)數(shù)字的時(shí)候，就看看包含當(dāng)前位置的行和列以及 3x3 小方陣中是否已經(jīng)出現(xiàn)該數(shù)字，這里需要三個(gè) boolean 型矩陣，大小跟原數(shù)組相同，分別記錄各行，各列，各小方陣是否出現(xiàn)某個(gè)數(shù)字，其中行和列標(biāo)志下標(biāo)很好對(duì)應(yīng)，就是小方陣的下標(biāo)需要稍稍轉(zhuǎn)換一下，具體代碼如下：

解法一：

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

我們也可以對(duì)空間進(jìn)行些優(yōu)化，只使用一個(gè) HashSet 來(lái)記錄已經(jīng)存在過(guò)的狀態(tài)，將每個(gè)狀態(tài)編碼成為一個(gè)字符串，能將如此大量信息的狀態(tài)編碼成一個(gè)單一的字符串還是需要有些技巧的。對(duì)于每個(gè)1到9內(nèi)的數(shù)字來(lái)說(shuō)，其在每行每列和每個(gè)小區(qū)間內(nèi)都是唯一的，將數(shù)字放在一個(gè)括號(hào)中，每行上的數(shù)字就將行號(hào)放在括號(hào)左邊，每列上的數(shù)字就將列數(shù)放在括號(hào)右邊，每個(gè)小區(qū)間內(nèi)的數(shù)字就將在小區(qū)間內(nèi)的行列數(shù)分別放在括號(hào)的左右兩邊，這樣每個(gè)數(shù)字的狀態(tài)都是獨(dú)一無(wú)二的存在，就可以在 HashSet 中愉快地查找是否有重復(fù)存在啦，參見代碼如下：

解法二：

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        unordered_set<string> st;
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] == '.') continue;
                string t = "(" + to_string(board[i][j]) + ")";
                string row = to_string(i) + t, col = t + to_string(j), cell = to_string(i / 3) + t + to_string(j / 3);
                if (st.count(row) || st.count(col) || st.count(cell)) return false;
                st.insert(row);
                st.insert(col);
                st.insert(cell);
            }
        }
        return true;
    }
};

到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(36.驗(yàn)證數(shù)獨(dú))的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)驗(yàn)證數(shù)獨(dú)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！