Share some knowledge, post study notes or talk nonsense.

0%

[LeetCode 36] Valid Sudoku (验证数独)

Description

Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

  1. Each row must contain the digits 1-9 without repetition.
  2. Each column must contain the digits 1-9 without repetition.
  3. Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.

Solutions

Solution 0

naive的思路,将程序分为独立的三步:

  1. 查看每行是否有相同的元素
  2. 查看每列是否有相同的元素
  3. 查看每个3*3的block有没有相同的元素

具体实现细节上:

  • 使用**unorderd_set(hash的方法)**来分别判断每行每列每个block中是否有相同的元素,这样以上的每一步就只需O(n2)O(n^2)的时间复杂度

  • 注意"."的处理

Solution 1

由于数字是1-9(有9个位置),每行每列都有9个位置,每个block规定为3*3(也有9个位置),因此在每行或每列或每个block内,可以构建从数字到位置的一一映射,因此相同的数字会被映到相同的位置,而如果那个位置已经被其它数字“占据”了,那就说明有重复的数字。其实这也是哈希的思想,哈希就是将数字经一个函数映射到代表位置的index,再在那个index对应的位置里插入数字即可。

具体实现上:创建三个二维布尔型数组v1、v2、v3,分别记录各行,各列,各小方阵是否出现某个数字。在遍历9*9的矩阵的时候,将每个数字分别映射到这三个布尔型数组相应的位置上,检查那个位置是否已经1,若为1就return false。其中,将数字映射到v1和v2只需做这样的映射即可:num->(r, num)num->(num, c),而将数字映射到v3就需要做一定的转换了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
vector<vector<bool>> rowFlag(9, vector<bool>(9));
vector<vector<bool>> colFlag(9, vector<bool>(9));
vector<vector<bool>> cellFlag(9, vector<bool>(9));
for (int i = 0; i < 9; ++i) {
for (int j = 0; j < 9; ++j) {
if (board[i][j] == '.') continue;
int c = board[i][j] - '1';
if (rowFlag[i][c] || colFlag[c][j] || cellFlag[3 * (i / 3) + j / 3][c]) return false;
rowFlag[i][c] = true;
colFlag[c][j] = true;
cellFlag[3 * (i / 3) + j / 3][c] = true;
}
}
return true;
}
};

Solution 2

由于Solution 1需要创建三个和原数组相同大小的数组,我们可以简化一下,只用一个hash table就搞定(不过实际上并没有节省空间)。

由于我们要分别检查每行、每列、每个block是否有相同的元素,因此每个数字可以认为有三种互不联系的状态:在行中,在列中,在block中。我们可以将每个状态编码为1个字符串,而且只要状态不同,字符串也不同,只要状态相同,字符串也相同,具体做法为:将数字放在一个括号中,每行上的数字就将行号放在括号左边,每列上的数字就将列数放在括号右边,每个小区间内的数字就将在小区间内的行列数分别放在括号的左右两边。

具体实现上:在遍历9*9的矩阵的时候,将每个元素的三种状态编码成三个string,先判断unorderd_set有没有这三个状态,没有就加到unordered_set里面,有就return false

其实这个idea本质上和Solution 1是一样的,只不过这个解法将Solution 1的三个二维数组合在一起了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
unordered_set<string> st;
for (int i = 0; i < 9; ++i) {
for (int j = 0; j < 9; ++j) {
if (board[i][j] == '.') continue;
string t = "(" + to_string(board[i][j]) + ")";
string row = to_string(i) + t, col = t + to_string(j), cell = to_string(i / 3) + t + to_string(j / 3);
if (st.count(row) || st.count(col) || st.count(cell)) return false;
st.insert(row);
st.insert(col);
st.insert(cell);
}
}
return true;
}
};

Reference: https://github.com/grandyang/leetcode/issues/36

Summary

  1. Solution1、2是遍历一次数组,判断每个数字是否在它所在的行或列或块上唯一;而Solution 0是遍历三次数组,每次只判断一类
  2. 用字符串来哈希的技巧可以借鉴