Leetcode: Valid Sudoku

忘是亡心i 2022-08-07 05:41 11阅读 0赞

题目：  
Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.

The Sudoku board could be partially filled, where empty cells are filled with the character ‘.’.

Sudoku规则：

在一个9\*9的区域内，  
每行1-9出现且只出现一次，  
每列1-9出现且只出现一次，  
在9个子3\*3的区域内1-9出现且只出现一次。

C++参考代码：

class Solution
    {
    public:
        bool isValidSudoku(vector<vector<char> > &board)
        {
            //row和column分别记录行和列中元素出现的次数
            int row[9], column[9];
    
            //判断行和列是否满足要求
            for (int i = 0; i < 9; i++)
            {
                //将row和column赋值为0
                memset(row, 0, sizeof(int) * 9);
                memset(column, 0, sizeof(int) * 9);
                for (int j = 0; j < 9; j++)
                {
                    //对行的判断
                    if (board[i][j] != '.')
                    {
                        //board[i][j] - '1'是计算board[i][j]这个数在row中对应的下标
                        //如果board[i][j]这个数字出现的次数大于1次，即row[board[i][j] - '1'] > 0则返回false
                        if (row[board[i][j] - '1'] > 0) return false;
                        else row[board[i][j] - '1']++;
                    }
                    //对列的判断（同理）
                    if (board[j][i] != '.')
                    {
                        if (column[board[j][i] - '1'] > 0) return false;
                        else column[board[j][i] - '1']++;
                    }
                }
            }
    
            //判断3*3的区域是否满足要求
            int block[9];
            //外层的两个for循环控制对block的移动遍历
            for (int i = 0; i < 9; i += 3)
            {
                for (int j = 0; j < 9; j += 3)
                {
                    memset(block, 0, sizeof(int) * 9);
                    //内层的两个for循环控制对block内部的数据进行遍历判断
                    for (int m = 0; m < 3; m++)
                    {
                        for (int n = 0; n < 3; n++)
                        {
                            //判断方法和对行列的判断方法一样
                            if (board[i + m][j + n] != '.')
                            {
                                if (block[board[i + m][j + n] - '1'] > 0) return false;
                                else block[board[i + m][j + n] - '1']++;
                            }
                        }
                    }
                }
            }
            return true;
        }
    };