【LeetCode36】有效的數獨（哈希表）

一、題目

二、思路

• 在第 i 個行中是否出現過：使用​

  ​row[9][10]​

  ​​，注意第二次元是裝的數字，即哈希表的​

  ​key​

  ​​為數字（1-9範圍内），​

  ​value​

  ​​為是否出現過，出現過則為1（此時就直接傳回​

  ​false​

  ​了），沒出現過即保持為0（事後要置為1）。
• 在第 j 個列中是否出現過：使用​

  ​col[9][10]​

  ​
• 在第​

  ​j/3 + (i/3)*3​

  ​​個box中是否出現過：使用​

  ​box[9][10]​

  ​

三、代碼

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        //存儲每一行的每一個數是否都出現過
        int row[9][10] = {0};
        int col[9][10] = {0};
        //存儲每一個box的每個數是否出現過
        int box[9][10] = {0};
        for(int i = 0; i < 9; i++){
            for(int j = 0; j < 9; j++){
                if(board[i][j] == '.') continue;
                int num_temp = board[i][j] - '0';
                //哈希表，判斷該數是否在所在的行出現過
                if(row[i][num_temp]) return false;
                if(col[j][num_temp]) return false;
                if(box[j/3 + (i / 3) * 3][num_temp]) return false;
                
                //現在出現了，對應哈希表的value要置為1
                row[i][num_temp] = 1;
                col[j][num_temp] = 1;
                box[j/3 + (i / 3) * 3][num_temp] = 1;
            }
        }
        return true;
    }
};