每日一題
題目描述
36.有效的數獨
請你判斷一個 9x9 的數獨是否有效，只需要 根據以下規則 ，驗證已經填入的數字是否有效即可，
數字 1-9 在每一行只能出現一次，
數字 1-9 在每一列只能出現一次，
數字 1-9 在每一個以粗實線分隔的 3x3 宮內只能出現一次，（請參考示例圖）
數獨部分空格內已填入了數字，空白格用 ‘.’ 表示，
注意：
一個有效的數獨（部分已被填充）不一定是可解的，
只需要根據以上規則，驗證已經填入的數字是否有效即可，
示例 1：
輸入：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
示例 2：
輸入：board =
[[“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
解釋：除了第一行的第一個數字從 5 改為 8 以外，空格內其他數字均與 示例1 相同， 但由于位于左上角的 3x3 宮內有兩個 8 存在, 因此這個數獨是無效的，
作者：LeetCode-Solution
鏈接：https://leetcode-cn.com/problems/valid-sudoku/solution/you-xiao-de-shu-du-by-leetcode-solution-50m6/
來源：力扣（LeetCode）
著作權歸作者所有，商業轉載請聯系作者獲得授權，非商業轉載請注明出處，
演算法思路
一次遍歷：
利用哈希表記錄每一行，每一列，每一個小九宮格的數字出現的個數，
只需要一次遍歷，有重復的數字就回傳false，沒有則回傳true，
代碼實作
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board)
{
int a[9][9] = { 0 };
int b[9][9] = { 0 };
int box[3][3][9] = { 0 };
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
int c = board[i][j];
if (c != '.')
{
int index = c - '0' - 1;
a[i][index]++;
b[j][index]++;
box[i / 3][j / 3][index]++;
if (a[i][index] > 1 || b[j][index] > 1 || box[i / 3][j / 3][index] > 1)
{
return false;
}
}
}
}
return true;
}
};
復雜度分析
-
時間復雜度：O(1)，數獨共有 81 個單元格，只需要對每個單元格遍歷一次即可，
-
空間復雜度：O(1)，由于數獨的大小固定，因此哈希表的空間也是固定的，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/342128.html
標籤：其他