Leetcode: Valid Sudoku

题目: 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;
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券