題目描述
請你判斷一個 9 x 9 的數獨是否有效，只需要 根據以下規則 ，驗證已經填入的數字是否有效即可，
數字 1-9 在每一行只能出現一次，
數字 1-9 在每一列只能出現一次，
數字 1-9 在每一個以粗實線分隔的 3x3 宮內只能出現一次，
作者：力扣 (LeetCode)
鏈接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2f9gg/
來源：力扣（LeetCode）
著作權歸作者所有，商業轉載請聯系作者獲得授權，非商業轉載請注明出處，
題目決議
例，輸入如下資料
輸入：board =
[["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
這個題目怎么去分析呢？首先它有9行，9列，9個小四方塊，最簡單的方法我們弄27個HashMap也能解決該問題，但它不是最優解，怎樣才能找到最優解呢？先分拆問題，將問題簡單化，解決簡單問題找到規律后再解決原有問題，如果只有一行9個數字，我們怎么判斷它是否有重復的呢？我們順著前面那個暴力破解的思路來分析，當然我們可以使用HashMap來解決，但是組合問題后，解題方式又變成剛才的解法了，
為了引出解題方法，我們先將一個故事，前些日子我陪女兒玩過一個這樣的游戲：面前有7個杯子和七個球，杯子和球的顏色一一對應，需要把球放到相同顏色的杯子了，對這個游戲我們做一下延申，標有1-9的數字的杯子和標有1-9的數字的小球，將小球放到相同數字的杯子里，如果有很多小球呢？我們是不是能夠快速的確定手里的小球有沒有重復的呢？
通過上面的游戲，我們可以想象到如果把數獨里的數字當成Key存在HashMap中，如果把這個數字當成Index索引，作為陣列的下標也可以解決這個問題，這樣我們只需要三個9*9的二位陣列即可，我們首先定義一個代表所有行的陣列：row[9][9]，用i表示哪一行，用數獨里的字符表示j，如果原始陣列中存在i上不等于'.'的數字num，那么將num放著i行的num列，這里我們將row[i][num]置為1，代表這個行列已經存在值了，同理，我們定義colunm[9][9] ,用j表示第幾列，賦值給該陣列的行下標，num的處理同row，
接下來我們定義9個區塊的陣列：block[9][9]，首先，我們用block的每一行放置每一小塊的原始元素，其次，我們要確認原始陣列的那個元素屬于哪一行block，通過分析可以得到index=i/3+j/3*3,index表示block那一行
最后我們需要注意一點，原始陣列的元素為char型別，因此我們想要得到對應的int型別的數字需要進行acsii轉換num=char-'0'-1;我們用原始元素-1，是為了將元素轉為數字下標，這樣處理不應用驗證重復的邏輯
題目解答
演算法1，時間復雜度為 o(n2),直接上代碼如下：
int row[9][9];
int colunm[9][9];
int block[9][9];
bool isValidSudoku(vector<vector<char>>& board) {
for(int i=0;i<9;i++)
{
for(int j=0;j<9;j++)
{
if(board[i][j]=='.')
{
continue;
}
int num=board[i][j]-'0'-1;
int bindex=i/3+j/3*3;
if(row[i][num]!=0 || colunm[j][num]!=0 || block[bindex][num]!=0)
{
return false;
}
row[i][num]=colunm[j][num]=block[bindex][num]=1;
}
}
return true;
}
解題思路：解題思路再題目分析中已經詳細闡明，此次不再累述，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/378086.html
標籤：C++