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

leetcode题集: 36. Valid Sudoku

程序员文章站 2022-07-15 12:28:50
...

第15题:36. Valid Sudoku

leetcode题集: 36. Valid Sudoku

leetcode题集: 36. Valid Sudoku

题目大意:检查数独是否有效; 即每行,每列和每个3x3小格子是否存在重复的数字。

注意要点

1. 数独有效并不等同于有解(开始以为是要解出数独,还以为难度有点大)

2. 只有提到的单元需要进行规则检测,也即是row,col和3x3 box需要做这些检测

3. 所给字符只会有数组1-9和 '.'

4. 边界大小9x9

题目分析:题目这么读下来,既然只是检测简单的当前是否有效,而不是数独是否有解,那么思路倒是很清晰的。总共是三个部分需要检测,行,列和3x3格子;既然是检测数字是否重复,我首先想到的就是填表,1-9的数字,由于有多行多列,所以肯定是二维表。那就三个部分分别检测就好了,三个二维表填表;数独边界大小也都固定成了9x9,这意味着行,列,box大小都是9个。直接上代码:

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        int row[9][9] = {0};
        int col[9][9] = {0};
        int box[9][9] = {0};    // 三个二维数组
        int tem = 0;
        for(int i=0;i<9;i++){
            for(int j=0;j<9;j++){
                if(board[i][j]=='.') continue;
                tem = board[i][j] - '1';    // 将数字字符 1-9 转化成 0-8
                row[tem][i]--;
                col[tem][j]--;
                box[tem][(i/3)*3 + j/3]--;    // 二维数组行表示数字,列表示第几行,第几列等
                if(row[tem][i]<-1 || col[tem][j]<-1 || box[tem][(i/3)*3 + j/3]<-1)
                    return false;
            }
        }
        return true;
    }
};

 

相关标签: C++ leetcode