leetcode：36. 有效的数独

题目来源

• leetcode：36. 有效的数独

题目描述

class Solution {
    
public:
    bool isValidSudoku(vector<vector<char>>& board) {
    

    }
};

题目解析

有效的数独满足以下三个条件：

• 同一个数字在每一行只能出现一次；
• 同一个数字在每一列只能出现一次；
• 同一个数字在每一个小九宫格只能出现一次。

直观上，我们很容易想到使用 哈希表 来记录某行/某列/某个小方块出现过哪些数字，来帮助我们判断是否符合「有效数独」的定义。

这道题唯一的难点可能是在于如何确定某个数落在哪个小方块中，我们可以去小方块进行编号：

怎么找规律呢？举个简单的例子， 一个3x9的矩阵，被分成3个3x3的box，如图：

• 可以看出，每个数属于哪个桶只取决于纵坐标：
  • 纵坐标为0/1/2的都属于桶[0]
  • 纵坐标为3/4/5的都属于桶[1]
  • 纵坐标为6/7/8的都属于桶[2]
  • 即： $j/3$
• 而对于9*9的矩阵，我们光根据j/3得到0/1/2还是不够的，还需要加上一个三的倍数

综上，可以 $idx=[i/3]\ast 3+j/3$

class Solution {
    
public:
    bool isValidSudoku(vector<vector<char>>& board) {
    
        bool row[9][10] = {
    false};// 哈希表存储每一行的每个数是否出现过，默认初始情况下，每一行每一个数都没有出现过
                             // 整个board有9行，第二维的维数10是为了让下标有9，和数独中的数字9对应。
        bool col[9][10] = {
    false};// 存储每一列的每个数是否出现过，默认初始情况下，每一列的每一个数都没有出现过
        bool box[9][10] = {
    false};// 存储每一个box的每个数是否出现过，默认初始情况下，在每个box中，每个数都没有出现过。整个board有9个box。


        for (int i = 0; i < 9; ++i) {
    
            for (int j = 0; j < 9; ++j) {
    
                int bid = 3 * (i / 3) + (j / 3);
                if(board[i][j] != '.'){
    
                    int num = board[i][j] - '0';
                    if(row[i][num] || col[j][num] || box[bid][num]){
    
                        return false;
                    }
                    row[i][j] = true;
                    col[j][num] = true;
                    box[bid][num] = true;
                }
            }
        }
        
        return true;
    }
};

其实，另外，我们可以将box定义成三维数组，更好理解

class Solution {
    
public:
    bool isValidSudoku(vector<vector<char>>& board) {
    
        bool row[9][10] = {
    false};// 哈希表存储每一行的每个数是否出现过，默认初始情况下，每一行每一个数都没有出现过
                             // 整个board有9行，第二维的维数10是为了让下标有9，和数独中的数字9对应。
        bool col[9][10] = {
    false};// 存储每一列的每个数是否出现过，默认初始情况下，每一列的每一个数都没有出现过
        bool box[3][3][10] = {
    false};// 存储每一个box的每个数是否出现过。


        for (int i = 0; i < 9; ++i) {
    
            for (int j = 0; j < 9; ++j) {
    
                if(board[i][j] != '.'){
    
                    int num = board[i][j] - '0';
                    if(row[i][num] || col[j][num] || box[i / 3][j / 3][num]){
    
                        return false;
                    }
                    row[i][j] = true;
                    col[j][num] = true;
                    box[i / 3][j / 3][num]= true;
                }
            }
        }
        
        return true;
    }
};