leetcode 36 有效的数独

佚名 6年前 (2019-04-14) 随笔 1717人围观抢沙发百度已收录

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

即定义三个哈希表来判断数独有效性空间复杂度O(3*10*n)时间O（n2），这道题和37是相关的题目，这道题的有效性为下一题填数独创造了条件；

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