leetcode 36

感觉就是遍历。

保存好状态，就是各行各列还有各分区divide的情况

用数组做。

空间小时间大

class Solution {

public:

    bool isValidSudoku(vector<vector<char>>& board) {

        int row[9][9]={0},col[9][9]={0},div[9][9]={0};

        int temp=0,dnum;

    for(int i=0;i<9;i++){

        for(int j=0;j<9;j++){

            if(board[i][j]!='.'){

                temp=board[i][j]-'0'-1;

                row[i][temp]++;

                col[j][temp]++;

                dnum=(i/3)*3+j/3;

                div[dnum][temp]++;

               if(row[i][temp]==2||col[j][temp]==2||div[dnum][temp]==2)

                return false;

            }

        }

    }

    return true;

    }

};

然后

学到了用unordered_set unordersd_map加速。

空间大时间小

class Solution {

public:

    bool isValidSudoku(vector<vector<char>>& board) {

        vector<unordered_set<int>> row(9), col(9), block(9);

        for(int i = 0; i < 9; ++ i){

            for(int j = 0; j < 9; ++ j){

                int bindex =  (i / 3)* 3 + j / 3;

                char cur = board[i][j];

                if(cur == '.')  continue;

                if(row[i].count(cur) || col[j].count(cur) || block[bindex].count(cur))  return false;

                row[i].insert(cur);

                col[j].insert(cur);

                block[bindex].insert(cur);

            }

        }

        return true;

    }

};

leetcode 37

做之前还百度了一下有没有解数独的技巧。。。 OxO

上一道题保存了行列块的状态，这里也可以保留，保留的不再是出现与否而是可用数字

回溯就完事了

class Solution {

public:

    vector<unordered_set<int>> row, col, block;

    void solveSudoku(vector<vector<char>>& board) {

        // 预处理，初始状态

        int t=0;

        unordered_set<int> tp={1,2,3,4,5,6,7,8,9};

        for(int i=0;i<9;i++)

            {row.push_back(tp);col.push_back(tp);block.push_back(tp);}

        for( int i = 0; i < 9; i++)

            for( int j = 0; j < 9; j++)

                if( board[i][j] != '.'){

                    t = board[i][j] - '0';

                    row[i].erase(t), col[j].erase(t), block[(i/3)*3 + j/3].erase(t);

                }

        int flag=0;

        dfs(board,0,flag);

        if(flag==0)  //题目说明有唯一解，不会出现

            cout<<"wrong"<<endl;

    }

    bool check(vector<vector<char>>& board,int i,int j,int num){

        if(row[i].find(num)!= row[i].end()&& col[j].find(num) != col[j].end()

         && block[(i/3)*3 + j/3].find(num) != block[(i/3)*3 + j/3].end())

         return true;

        return false;

    }

    void dfs(vector<vector<char>>& board,int cnt,int &flag){

        if( cnt == 81){

            flag = 1;

            return ;

        }

        int i = cnt / 9, j = cnt % 9;

        if( board[i][j] == '.'){

            for( int k = 1; k < 10; k++)

                if(check(board, i, j, k)){

                    row[i].erase(k), col[j].erase(k), block[(i/3)*3 + j/3].erase(k);

                    board[i][j] = '0'+k;

                    dfs(board, cnt+1,flag);

                    if(flag)

                        return;

                    else{

                        row[i].insert(k), col[j].insert( k), block[(i/3)*3 + j/3].insert(k);

                        board[i][j] = '.';

                    }

                }

                else

                    continue;

        }

        else

            dfs(board, cnt+1,flag);

        return ;

    }

};

然后效率很差。。时间和空间上

改成数组

class Solution {

public:

    int row[10][10], col[10][10], block[10][10];

    void solveSudoku(vector<vector<char>>& board) {

        // 预处理，初始状态

        int t=0;

        for( int i = 0; i < 9; i++)

            for( int j = 1; j < 10; j++)

            {

                row[i][j]=0, col[i][j]=0, block[i][j]=0;

            }

        for( int i = 0; i < 9; i++)

            for( int j = 0; j < 9; j++)

                if( board[i][j] != '.'){

                    t = board[i][j] - '0';

                    row[i][t]=1, col[j][t]=1, block[(i/3)*3 + j/3][t]=1;

                }

        int flag=0;

        dfs(board,0,flag);

        if(flag==0)  //题目说明有唯一解，不会出现

            cout<<"wrong"<<endl;

    }

    void dfs(vector<vector<char>>& board,int cnt,int &flag){

        if( cnt == 81){

            flag = 1;

            return ;

        }

        int i = cnt / 9, j = cnt % 9;

        if( board[i][j] == '.'){

            for( int k = 1; k < 10; k++)

                if(row[i][k]==0 && col[j][k]==0 && block[(i/3)*3 + j/3][k]==0){

                    row[i][k]=1, col[j][k]=1, block[(i/3)*3 + j/3][k]=1;

                    board[i][j] = '0'+k;

                    dfs(board, cnt+1,flag);

                    if(flag)

                        return;

                    else{

                        row[i][k]=0, col[j][k]=0, block[(i/3)*3 + j/3][k]=0;

                        board[i][j] = '.';

                    }

                }

                else

                    continue;

        }

        else

            dfs(board, cnt+1,flag);

        return ;

    }

};

我好了

然后，不传引用而是copy可以再节省一点空间

然后剪枝，没考虑 OxO

巴特西

leetcode 36 有效的数独哈希表 unordered_set unordersd_map 保存状态 leetcode 37 解数独

leetcode 36

leetcode 37

最新文章

热门文章

巴特西

leetcode 36 有效的数独 哈希表 unordered_set unordersd_map 保存状态 leetcode 37 解数独

leetcode 36

leetcode 37

最新文章

热门文章

leetcode 36 有效的数独哈希表 unordered_set unordersd_map 保存状态 leetcode 37 解数独