[LeetCode] 36. Valid Sudoku 驗證數(shù)獨

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.

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

解法一：

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;
    }
};

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

解法二：

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;
    }
};

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

最新評論