LeetCode Valid Sudoku：位運算高效驗證數獨合法性

題目描述

判斷一個 9×9 數獨盤面（部分填充）是否合法。合法條件：每行、每列、每個 3×3 子區塊中，數字 1-9 不重複（空格 '.' 忽略）。注意：合法不代表可解，只需驗證已填數字無衝突。

位運算優化方案

核心思想

用整數的二進制位表示數字是否出現：第 k 位為 1 表示數字 k 已出現。
三個陣列：
- row[9]：每行的數字掩碼
- col[9]：每列的數字掩碼
- block[9]：每個 3×3 區塊的掩碼（索引 (r/3)*3 + c/3）

操作封裝

bool isExist(int &mask, int num) { // num 1~9
    if (mask & (1 << num)) return true;
    mask |= (1 << num);
    return false;
}

完整代碼

#include <iostream>
#include <vector>
using namespace std;
class Solution {
    bool isExist(int &mask, int num) {
        if (mask & (1 << num)) return true;
        mask |= (1 << num);
        return false;
    }
public:
    bool isValidSudoku(vector<vector<char>> &board) {
        int row[9] = {0}, col[9] = {0}, block[9] = {0};
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') continue;
                int val = board[i][j] - '0';
                if (isExist(row[i], val)) return false;
                if (isExist(col[j], val)) return false;
                int bIdx = (i/3)*3 + j/3;
                if (isExist(block[bIdx], val)) return false;
            }
        }
        return true;
    }
};

複雜度分析

• 時間：O(81) = O(1)，單次遍歷常數操作。
• 空間：O(27) = O(1)，三個長度 9 的整數陣列。

優勢總結

• 位運算極快，無哈希表開銷。
• 代碼簡潔，邏輯清晰，易於擴展（如求解器）。
• 面試首選方案，展示底層優化能力。