欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【leetcode】36. Valid Sudoku

程序员文章站 2022-07-15 12:31:57
...

题目:
【leetcode】36. Valid Sudoku


思路:
用map<int, vector>(其实用vector也行),将所有“1”出现的位置及其块号都保存起来;将所有“2”出现的位置及其块号都保存起来;将所有“3”出现的位置及其块号都保存起来······每添加一个新的数字时,都看看与已保存的其他等值数字的位置是否冲突。


代码实现:

class Solution {
public:
    struct Point{
        int r;
        int c;
        int block;
    };
    
    int getBlockIndex(int r, int c){
        // todo
        return r/3 * 3 + c/3;
    }
    
    bool isInt(char c){
        return c >= '0' && c <= '9';
    }
    
    int char2Int(char c){
        return c - '0';
    }
    
    bool isValidSudoku(vector<vector<char>>& board) {
        map<int, vector<Point>> hash;
        
        for (int i = 1; i <= 9; ++i){
            vector<Point> t;
            hash[i] = t;
        }
        
        for (int i = 0; i < board.size(); ++i){
            for (int j = 0; j < board[i].size(); ++j){
                if (isInt(board[i][j]) == true){
                    vector<Point> &t = hash[char2Int(board[i][j])];
                    
                    int blockIndex = getBlockIndex(i,j);
                    for (int k = 0; k < t.size(); ++k){
                        if (t[k].r == i || t[k].c == j || t[k].block == blockIndex){
                            return false;
                        }
                    }
                    
                    t.push_back({i,j,blockIndex});
                }
            }
        }
        
        return true;
    }
};

思路2:

  1. 一行一行地检查
  2. 一列一列地检查
  3. 一块一块地检查

这三部分代码可以写在一起,参考https://www.cnblogs.com/ganganloveu/p/4170632.html