SamJ's blog

leetcode:有效的数独

algorithm,c++
Word count: 1kReading time: 5 min
2019/10/24 Share

初级算法篇

有效的数独

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

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

这道题主要的问题就是坐标变换，考虑如何在相同的循环次数条件下的同时以三种方式进行遍历。

首先建立三个数组row(验证行) col（验证列） cube （验证宫）。

他们都是int类型且大小为10且初始值为0的数组。当遍历到的元素不是'.'时，判断数组相应位置是否为1，若为1表示数独无效，返回false，若不为1，将相应位置的值设为一。

示例 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
输入:
[
  ["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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
输入:
[
  ["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 存在, 因此这个数独是无效的。

本题的难点在于坐标变换，在相同的i,j值得情况下，实现三种遍历的方式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//对于行的验证可以写为
for(int i = 0; i < 9; ++i)
{
    int row[10] = 0;
    for(int j = 0; j < 9; ++j)
    {
        if(board[i][j] != '.')
        {
            if(row[board[i][j] - '1'] == 1)
                return false;
            else
                row[board[i][j] - '1'] = 1;
        } 
        //....验证列，验证宫
    }
}

验证列时，由于i不变，j变，只要将board[i][j] 换成board[j][i] 即可对列进行验证。

比较难的一点是如何遍历宫的元素。即将i和j转换为每个宫的坐标。

有转换关系：

cubeX = 3 * (i / 3) + j / 3

cubeY = 3 *(i % 3) + j % 3

可以得到全部代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        for(int i = 0; i < 9; ++i)
        {
            int row[10] = {0};
            int col[10] = {0};
            int cube[10] = {0};
            int cubeX, cubeY;
            for(int j = 0; j < 9; ++j)
            {
                //对row
                if(board[i][j] != '.')
                {
                    if(row[board[i][j] - '1'] == 1)
                         return false;
                    else
                        row[board[i][j] - '1'] = 1;
                }
                //对col
                if(board[j][i] != '.')
                {
                    if(col[board[j][i] - '1'] == 1)
                        return false;
                    else
                        col[board[j][i] - '1'] = 1;
                }
                //对宫
                cubeX = 3 * (i / 3) + j / 3;
                cubeY = 3 * (i % 3) + j % 3;
                if(board[cubeX][cubeY] != '.')
                {
                    if(cube[board[cubeX][cubeY] - '1'] == 1)
                        return false;
                    else
                        cube[board[cubeX][cubeY] - '1'] = 1;
                }
            }
        }
        return true;
    }
};
CATALOG
  1. 1. 初级算法篇
    1. 1.1. 有效的数独
Total : 27
2021
2019
C++ paper hexo algorithm algorithm,c++ linux, C japanese,anime