36. Valid Sudoku
Analysis
看到这个题目，立马去玩了一局数独。
好在这个题目并不是求解，而是只用判断给定数独矩阵的合法性即可。也就是说，对于矩阵中存在的元素而言，必须满足：
- 这一行只有这一个元素
- 这一列只有这一个元素
- 9 宫格只有这一个元素
当且仅当这 3 个条件都满足，这个数独矩阵才合法。
Code
method 1
按照上面的思路，逐个判断就可以了。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
27class Solution {
public:
bool isvalid(vector<vector<char>>& board, int r, int c) {
for(int i = 0; i < 9; i++) {
if(i != c && board[r][i] == board[r][c]) return false;
}
for(int i = 0; i < 9; i++) {
if(i != r && board[i][c] == board[r][c]) return false;
}
int R = r >= 3 ? r >= 6 ? 9 : 6 : 3;
int C = c >= 3 ? c >= 6 ? 9 : 6 : 3;
for(int i = R - 3; i < R; i++) {
for(int j = C - 3; j < C; j++) {
if(i != r && j != c && isdigit(board[i][j]) && board[i][j] == board[r][c]) return false;
}
}
return true;
}
bool isValidSudoku(vector<vector<char>>& board) {
for(int i = 0; i < 9; i++) {
for(int j = 0; j < 9; j++) {
if(isdigit(board[i][j]) && !isvalid(board, i, j)) return false;
}
}
return true;
}
};
把行与列的判断放在前面，并且先对下标进行判断的目的，是为了能在一定程度上减少判断的次数。
method 2
回过头来看这道题的话，其实不算难题，就是比较麻烦。按照上面的代码，可以发现有很多重复判断的地方，可以使用哈希表优化一下。对于每一个元素而言，需要满足 3 个条件，按照这样的思路，需要维护的哈希表个数一共是：9 + 9 + 9 = 18。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
int rows[9][9] = {0};
int columns[9][9] = {0};
int submatrix[3][3][9] = {0};
for(int i = 0; i < 9; i++) {
for(int j = 0; j < 9; j++) {
char c = board[i][j];
if(c != '.') {
int index = c - '0' - 1;
rows[i][index]++;
columns[j][index]++;
submatrix[i / 3][j / 3][index]++;
if(rows[i][index] > 1 || columns[j][index] > 1 || submatrix[i / 3][j / 3][index] > 1) {
return false;
}
}
}
}
return true;
}
};
虽然使用哈希表很简洁，但是就这个问题而言，一共要维护 27 个哈希表。这与 $9×9$ 矩阵的遍历所消耗的时间相比，感觉实际上还不如直接暴力来的划算？实际生产环境中多等个零点几秒估计也不会造成什么经济损失？😂
73. Set Matrix Zeroes
Analysis
这个题最容易想到的做法应该是先找到所有 0 的位置，然后根据这些位置再来将符合条件的元素置零即可。尽管题目要求原地算法，但是先把想到的办法写出来吧
Code
method 1
按照上面的思路，很容易就可以得到暴力解法。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
vector<pair<int, int>> zeropoints;
int m = matrix.size(), n = matrix[0].size();
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(matrix[i][j] == 0) zeropoints.push_back(make_pair(i, j));
}
}
for(auto it: zeropoints) {
int x = it.first, y = it.second;
for(int i = 0; i < n; i++) {
matrix[x][i] = 0;
}
for(int i = 0; i < m; i++) {
matrix[i][y] = 0;
}
}
}
};
之所以要先将点挑出来，是因为置零之后会影响后面的判断，所以要分开进行。另外，从上面的代码中，可以很容易的发现，在遍历 0 点的坐标时，x、y 可能会出现相等的情况，这样就会产生很多重复操作。
method 2
按照上面的思路，借助哈希表来优化一下。$m×n$ 的矩阵一共需要 $m + n$个哈希表来维护。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
28class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
vector<pair<int, int>> zeropoints;
int m = matrix.size(), n = matrix[0].size();
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(matrix[i][j] == 0) zeropoints.push_back(make_pair(i, j));
}
}
int rows[201] = {0}, columns[201] = {0};
for(auto it: zeropoints) {
int x = it.first, y = it.second;
if(!rows[x]) {
rows[x] = 1;
for(int i = 0; i < m; i++) {
if(i != y) matrix[x][i] = 0;
}
}
if(!columns[y]) {
columns[y] = 1;
for(int i = 0; i < n; i++) {
if(i != x) matrix[i][y] = 0;
}
}
}
}
};
实际上，也可以不用存储每个点的坐标，只需要分别存储行号和列号即可，那么不妨用 set 来存储，这样还可以自动去除重复的行、列。然后遍历 set，将符合要求的行、列的所有元素全部置为零即可。偷一下懒，这段代码就不写了。
method 3
但是不管是用 set 还是 pair，需要的存储空间都是 $O(m + n)$，有什么办法能原地进行呢？
答案是用第一行和第一列来更新矩阵剩余的元素，再用剩余的元素来更新第一行和第一列的元素。但是，这样会改变第一行和第一列的元素，会无法判断其本身是否存在 0，所以需要用 2 个变量来记录第一行和第一列是否含 0。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
31class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
bool frow0 = false, fcol0 = false;
for(int i = 0; i < n; i++) {
if(!matrix[0][i]) frow0 = true;
}
for(int i = 0; i < m; i++) {
if(!matrix[i][0]) fcol0 = true;
}
for(int i = 1; i < m; i++) {
for(int j = 1; j < n; j++) {
if(!matrix[i][j]) {
matrix[i][0] = matrix[0][j] = 0;
}
}
}
for(int i = 1; i < m; i++) {
for(int j = 1; j < n; j++) {
if(!matrix[i][0] || !matrix[0][j]) matrix[i][j] = 0;
}
}
if(frow0) {
for(int i = 0; i < n; i++) matrix[0][i] = 0;
}
if(fcol0) {
for(int i = 0; i < m; i++) matrix[i][0] = 0;
}
}
};
回过头来看的话，这种解法就是将第一行、第一列当成了散列表。那还能不能更优化呢？
当然可以，不妨设 fcol0 是用来记录第一列是否存在 0，与上面的思路类似，在设置好 fcol0 后，用剩余的元素处理第一行和第一列的元素（这两件事可以同时进行）。然后，再用处理后的第一行、第一列元素来处理剩余的元素。这里可以发现，第一行是否存在 0 的信息会被记录在 $matrix[0][0]$ 中。接下来，按照上面的思路来修改矩阵的值就可以了。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
26class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
bool fcol0 = false;
for(int i = 0; i < m; i++) {
if(!matrix[i][0]) fcol0 = true;
for(int j = 1; j < n; j++) {
if(!matrix[i][j]) {
matrix[i][0] = matrix[0][j] = 0;
}
}
}
for(int i = 1; i < m; i++) {
for(int j = 1; j < n; j++) {
if(!matrix[i][0] || !matrix[0][j]) matrix[i][j] = 0;
}
}
if(!matrix[0][0]) {
for(int i = 1; i < n; i++) matrix[0][i] = 0;
}
if(fcol0) {
for(int i = 0; i < m; i++) matrix[i][0] = 0;
}
}
};
需要注意的是，最后单独处理第一行第一列时，一定要先判断第一行是否全为 0，因为 fcol0 可能会使不为 0 的 $matrix[0][0]$ 变为 0，这就影响了后面的判断了。
事实上，也可以用 $matrix[0][0]$ 来记录列是否存在 0，这样就需要设置一个 frow0 来记录第一行是否存在 0 了。同样地，也需要先用 $matrix[0][0]$ 判断。
Summary
今天的 2 个题都挺有意思的。第一个题数组下标的转换是需要体会的点，这种做法其实很方便的。第二个题对空间的优化也很不错，不过理解起来可能没有那么容易，得仔细体会下。
