leetcode-36-有效的数独

chenjx85

发布于 2018-08-16 11:29:51

3720

发布于 2018-08-16 11:29:51

文章被收录于专栏：chenjx85的技术专栏chenjx85的技术专栏

题目描述：

判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

上图是一个部分填充的有效的数独。

数独部分空格内已填入了数字，空白格用 '.' 表示。

示例 1:

输入:
[
  ["5","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
输出: true

示例 2:

输入:
[
  ["8","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
输出: false
解释: 除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。
     但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

说明:

一个有效的数独（部分已被填充）不一定是可解的。
只需要根据以上规则，验证已经填入的数字是否有效即可。
给定数独序列只包含数字 1-9 和字符 '.' 。
给定数独永远是 9x9 形式的。

要完成的函数：

bool isValidSudoku(vector<vector<char>>& board)

说明：

1、这道题给定一个二维的vector，里面存放着char类型的元素，元素只可能是1-9或者‘.’

这个二维的vector的行数和列数都是9，要求根据以下规则判断填入的数字是否有效：

①一共9行，1-9的数字在每一行中，每个数字只能出现一次。

②一共9列，1-9的数字在每一列中，每个数字只能出现一次。

③一共9个方块，每个方块都是3行3列的，1-9的数字在每个方块中，每个数字只能出现一次。

2、这道题不难，判断三个规则是否成立，我们只需用暴力解法。

一个四重循环，用来判断每个方块是否1-9的数字只出现一次。

一个双重循环用来判断每一行是否1-9的数字只出现一次。

一个双重循环用来判断每一列是否1-9的数字只出现一次。

代码如下：（附详解）

    bool isValidSudoku(vector<vector<char>>& board) 
    {
        unordered_set<char>s1;//定义一个不排序的set，用来存储char类型的数字
        int count;//用来记录有多少个数字
        for(int i=0;i<3;i++)//把9行分成3块
        {
            for(int j=0;j<3;j++)//把9列分成3块
            {
                count=0;
                s1.clear();
                for(int k=0;k<3;k++)//每个方块内部分为3行
                {
                    for(int l=0;l<3;l++)//每个方块内部分为3列
                    {
                        if(board[i*3+k][j*3+l]!='.')//如果是数字
                        {
                            s1.insert(board[i*3+k][j*3+l]);//插入存储到set中
                            count++;//记录有多少个数字出现
                        }
                    }
                }
                if(s1.size()!=count)//如果不相等，说明有重复的数字出现
                    return false;
            }
        }
        for(int i=0;i<9;i++)//9行
        {
            s1.clear();
            count=0;
            for(int j=0;j<9;j++)//9列，判断每一行是否出现了重复的数字
            {
                if(board[i][j]!='.')
                {
                    s1.insert(board[i][j]);
                    count++;
                }
            }
            if(s1.size()!=count)
                return false;
        }
        for(int j=0;j<9;j++)//9列
        {
            s1.clear();
            count=0;
            for(int i=0;i<9;i++)//9行，判断每一列有没有出现重复的数字
            {
                if(board[i][j]!='.')
                {
                    s1.insert(board[i][j]);
                    count++;
                }
            }
            if(s1.size()!=count)
                return false;
        }
        return true;//如果都没有返回false，那么说明三个规则都满足，那么返回true
    }

上述代码实测16ms，beats 86.53% of cpp submissions。

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2018-08-13 ，如有侵权请联系 cloudcommunity@tencent.com 删除

其他

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

其他

登录后参与评论

0 条评论

热度