題目描述：

判斷一個(gè) 9x9 的數(shù)獨(dú)是否有效。只需要根據(jù)以下規(guī)則，驗(yàn)證已經(jīng)填入的數(shù)字是否有效即可。

數(shù)字 1-9 在每一行只能出現(xiàn)一次。
數(shù)字 1-9 在每一列只能出現(xiàn)一次。
數(shù)字 1-9 在每一個(gè)以粗實(shí)線分隔的 3x3 宮內(nèi)只能出現(xiàn)一次。

上圖是一個(gè)部分填充的有效的數(shù)獨(dú)。

數(shù)獨(dú)部分空格內(nèi)已填入了數(shù)字，空白格用 '.' 表示。

示例 1:

輸入:
[
["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"]
]
輸出: true

示例 2:

輸入:
[
["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"]
]
輸出: false
解釋: 除了第一行的第一個(gè)數(shù)字從 5 改為 8 以外，空格內(nèi)其他數(shù)字均與 示例1 相同。
但由于位于左上角的 3x3 宮內(nèi)有兩個(gè) 8 存在, 因此這個(gè)數(shù)獨(dú)是無效的。

說明:

一個(gè)有效的數(shù)獨(dú)（部分已被填充）不一定是可解的。
只需要根據(jù)以上規(guī)則，驗(yàn)證已經(jīng)填入的數(shù)字是否有效即可。
給定數(shù)獨(dú)序列只包含數(shù)字 1-9 和字符 '.' 。
給定數(shù)獨(dú)永遠(yuǎn)是 9x9 形式的。

?

思想：

由于board中的整數(shù)限定在1到9的范圍內(nèi)，因此可以分別建立哈希表來存儲(chǔ)任一個(gè)數(shù)在相應(yīng)維度上是否出現(xiàn)過。維度有3個(gè)：所在的行，所在的列，所在的box，注意box的下標(biāo)也是從左往右、從上往下的。

遍歷到每個(gè)數(shù)的時(shí)候，例如boar[i][j]，我們判斷其是否滿足三個(gè)條件：

在第 i 個(gè)行中是否出現(xiàn)過
在第 j 個(gè)列中是否出現(xiàn)過
在第 j/3 (i/3)*3個(gè)box中是否出現(xiàn)過.為什么是j/3 (i/3)*3呢？
關(guān)于從數(shù)組下標(biāo)到box序號(hào)的變換
?重述一遍問題：給定i和j，如何判定board[i][j]在第幾個(gè)box呢？
?顯然屬于第幾個(gè)box由i和j的組合唯一確定，例如board[2][2]一定是第0個(gè)box，board[4][7]一定是第5個(gè)box，可以畫出來看一下，但是規(guī)律在哪里呢？
我們可以考慮一種簡單的情況： 一個(gè)3x9的矩陣，被分成3個(gè)3x3的box，如圖：

顯然每個(gè)數(shù)屬于哪個(gè)box就只取決于縱坐標(biāo)，縱坐標(biāo)為0/1/2的都屬于box[0],縱坐標(biāo)為3/4/5的都屬于box[1],縱坐標(biāo)為6/7/8的都屬于box[2].也就是j/3.
而對(duì)于9x9的矩陣，我們光根據(jù)j/3得到0/1/2還是不夠的，可能加上一個(gè)3的倍數(shù)，例如加0x3,表示本行的box，加1x3，表示在下一行的box，加2x3，表示在下兩行的box， 這里的0/1/2怎么來的？和j/3差不多同理，也就是i/3。

代碼：

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        int row[9][10] = {0};// 哈希表存儲(chǔ)每一行的每個(gè)數(shù)是否出現(xiàn)過，默認(rèn)初始情況下，每一行每一個(gè)數(shù)都沒有出現(xiàn)過
        // 整個(gè)board有9行，第二維的維數(shù)10是為了讓下標(biāo)有9，和數(shù)獨(dú)中的數(shù)字9對(duì)應(yīng)。
        int col[9][10] = {0};// 存儲(chǔ)每一列的每個(gè)數(shù)是否出現(xiàn)過，默認(rèn)初始情況下，每一列的每一個(gè)數(shù)都沒有出現(xiàn)過
        int box[9][10] = {0};// 存儲(chǔ)每一個(gè)box的每個(gè)數(shù)是否出現(xiàn)過，默認(rèn)初始情況下，在每個(gè)box中，每個(gè)數(shù)都沒有出現(xiàn)過。整個(gè)board有9個(gè)box。
        for(int i=0; i<9; i  ){
            for(int j = 0; j<9; j  ){
                // 遍歷到第i行第j列的那個(gè)數(shù),我們要判斷這個(gè)數(shù)在其所在的行有沒有出現(xiàn)過，
                // 同時(shí)判斷這個(gè)數(shù)在其所在的列有沒有出現(xiàn)過
                // 同時(shí)判斷這個(gè)數(shù)在其所在的box中有沒有出現(xiàn)過
                if(board[i][j] == '.') continue;
                int curNumber = board[i][j]-'0';
                if(row[i][curNumber]) return false; 
                if(col[j][curNumber]) return false;
                if(box[j/3   (i/3)*3][curNumber]) return false;

                row[i][curNumber] = 1;// 之前都沒出現(xiàn)過，現(xiàn)在出現(xiàn)了，就給它置為1，下次再遇見就能夠直接返回false了。
                col[j][curNumber] = 1;
                box[j/3   (i/3)*3][curNumber] = 1;
            }
        }
        return true;
    }
};

?