LeetCode 36：有效的數獨——行、列、九宮格唯一性檢查

題目描述

判斷 9×9 數獨盤面是否合法：每行、每列、每 3×3 子區塊包含數字 1-9 且不重複（空格用 '.' 表示）。

算法思路

三次遍歷，每次用大小為 10 的布爾陣列/位掩碼記錄出現情況：

1. 行檢查：for i: check row i
2. 列檢查：for j: check col j
3. 子區塊檢查：for bi=0,3,6; bj=0,3,6: check 3x3 block

C++ 實現（位掩碼優化）

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        int row[9] = {}, col[9] = {}, box[9] = {};
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                char c = board[i][j];
                if (c == '.') continue;
                int bit = 1 << (c - '1');
                int b = (i/3)*3 + j/3;
                if (row[i] & bit) return false; row[i] |= bit;
                if (col[j] & bit) return false; col[j] |= bit;
                if (box[b] & bit) return false; box[b] |= bit;
            }
        }
        return true;
    }
};

關鍵點

• 位掩碼 int 替代 bool[10]，常數因子極小。
• 子區塊索引 (i/3)*3 + j/3 映射 0-8。
• 單次雙重循環同時完成三項檢查，時間 O(81)。

複雜度

• 時間：O(1)（固定 9×9）。
• 空間：O(1)。