每日一題_36. 有效的數獨

leetcode_36

題目：

題意分析：
這一題是一個常規題吧，就是讓我們判斷一個數獨題目是不是正確的，但是注意這不是讓我們判斷數獨本省有沒有解，只是讓我們判斷這個數獨題目本身滿不滿足數獨的條件。

這道題沒什么太多的算法，就是有兩個技巧吧，一個是記錄每行每列九宮格里字符出現的個數，因為范圍固定在字符1-9，因此可以用一個int數組來當作hash表，鍵值就是ch(char) - ‘0’。

另一個處理的就是遍歷九宮格了，官方答案給的是一次遍歷，但是我一開始想的就是分開遍歷，在遍歷九宮格，有思考一會兒。官答是直接開了一個三維數組([3][3][9])來記錄每行每列的九宮格，我思維比較直接就用一個一維數組，單獨遍歷每個九宮格進行檢驗，遍歷的時候找到每個小九宮的起點，也就是（0，0），（0，3），（0，6）… … 找到起點之后，每個九宮格有九個數，遍歷然后在起點的基礎上加上偏移就行了（k / 3, k % 3）。

代碼：

class Solution { public:bool isValidSudoku(vector<vector<char>>& board) {int a[10];for (int i = 0; i < 9; i ++){memset(a, 0, sizeof a);for (int j = 0; j < 9; j ++)if ((board[i][j] != '.') && ++ a[board[i][j] - '0'] > 1) return false;}for (int i = 0; i < 9; i ++){memset(a, 0, sizeof a);for (int j = 0; j < 9; j ++)if ((board[j][i] != '.') && (++ a[board[j][i] - '0'] > 1)) return false;}for (int i = 0; i < 9; i += 3)for (int j = 0; j < 9; j += 3){memset(a, 0, sizeof a);for (int k = 0; k < 9; k ++){int row = i + k / 3, col = j + k % 3;if (board[row][col] != '.' && ++ a[board[row][col] - '0'] > 1) return false;}}return true;} };

總結

以上是生活随笔為你收集整理的每日一题_36. 有效的数独的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。