快捷導(dǎo)航

C++實(shí)現(xiàn)LeetCode(36.驗(yàn)證數(shù)獨(dú))

更新時間：2021年07月14日 15:21:39 作者：Grandyang

這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(36.驗(yàn)證數(shù)獨(dú)),本篇文章通過簡要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下

[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:

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

我們也可以對空間進(jìn)行些優(yōu)化，只使用一個 HashSet 來記錄已經(jīng)存在過的狀態(tài)，將每個狀態(tài)編碼成為一個字符串，能將如此大量信息的狀態(tài)編碼成一個單一的字符串還是需要有些技巧的。對于每個1到9內(nèi)的數(shù)字來說，其在每行每列和每個小區(qū)間內(nèi)都是唯一的，將數(shù)字放在一個括號中，每行上的數(shù)字就將行號放在括號左邊，每列上的數(shù)字就將列數(shù)放在括號右邊，每個小區(qū)間內(nèi)的數(shù)字就將在小區(qū)間內(nèi)的行列數(shù)分別放在括號的左右兩邊，這樣每個數(shù)字的狀態(tài)都是獨(dú)一無二的存在，就可以在 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)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: