思想
看看矩阵。矩阵是一种特殊的场景，二维数组。所以我觉得这种题目更多是练习 vector<vector<int>> 的各种 API 操作。有些解法没做过，真的很难想。
题目
48. Rotate Image
将图形顺时针旋转 $90^{\circ}$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
for (int i = 0; i < m; i++) {
for (int j = i + 1; j < n; j++) {
swap(matrix[i][j], matrix[j][i]);
}
}
for (int i = 0; i < m; i++) {
reverse(matrix[i].begin(), matrix[i].end());
}
return;
}
};
|
顺时针旋转 $90^{\circ}$ 可以拆分为两个操作：主对角线翻转，随后逐行逆序。只要知道这个数学规则就能够完成这道题。
那么，变体就可以有逆时针旋转 $90^{\circ}$，以及各种各样的角度。
54. Spiral Matrix
螺旋地读取一个矩阵的内容。
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
43
44
45
46
47
48
49
50
| class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
int top = 0, bottom = m - 1, left = 0, right = n - 1;
vector<int> ans;
while (true) {
for (int j = left; j <= right; j++) {
ans.push_back(matrix[top][j]);
}
top++;
if (top > bottom) break;
for (int i = top; i <= bottom; i++) {
ans.push_back(matrix[i][right]);
}
right--;
if (left > right) break;
for (int j = right; j >= left; j--) {
ans.push_back(matrix[bottom][j]);
}
bottom--;
if (top > bottom) break;
for (int i = bottom; i >= top; i--) {
ans.push_back(matrix[i][left]);
}
left++;
if (left > right) break;
}
return ans;
}
};
|
这题要模拟缩圈。最直白的想法是，用上下左右四个边界表示圈，随后边读取，边改变，边判断圈的范围即可。
73. Set Matrix Zeroes
这题要求我们对于矩阵中值为 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
26
27
28
29
30
31
32
33
34
35
36
37
| class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
bool col0 = false;
for (int i = 0; i < m; i++) {
if (matrix[i][0] == 0) {
col0 = true;
}
for (int j = 1; j < n; j++) {
if (matrix[i][j] == 0) {
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
for (int i = m - 1; i >= 0; i--) {
for (int j = n - 1; j >= 1; j--) {
if (matrix[i][0] == 0 || matrix[0][j] == 0) {
matrix[i][j] = 0;
}
}
if (col0) {
matrix[i][0] = 0;
}
}
return;
}
};
|
一个基本的思路是，用 $O(m + n)$ 空间复杂度的标记，记录行/列是否含有 0。可是题目要求要 $O(1)$ 的空间复杂度。
我们可以用第 [0] 行和第 [0] 列记录该行或该列是否含有 0，但棘手的地方是，对于 matrix[0][0] 位置，有二义性。所以这段代码最绕的地方是如何处理这个二义性。
我们需要单独用一个变量 col0 记录第 0 列是否有 0，当然也可以选 row0，那逻辑稍微有些变化，道理相同，总之 [0][0] 和另一个变量分别表示行和列。
那么，该如何遍历呢？假如让 i 和 j 都从 1 开始，绝大多数的标记都可以正确处理，除了第 0 行和第 0 列。这是因为假如标记所在的位置就是 0，如果没有遍历到其他的 0，没关系，标记位置就是 0 可以被表示。如果标记位置是 1，那其余位置遍历到 0/1 会被反映到标记中。
那么为了记录第 0 行和第 0 列的情况，需要稍微修改遍历的起始位置。为了记录第 0 行的情况，还是要把 i 从 0 开始；而为了记录第 0 列的情况，每访问新的一行，先判断该行第 0 列是否为 0，而后处理第 i 行的下标。这样可以保证标记不会污染值。
标记处理完毕，而后进行 0 的传播。需要遍历每个位置，应该从右下角开始，这样可以避免值污染标记的情况。对于第 0 列的情况，需要特殊处理，同时这一次，需要放到遍历其他列的后方，否则标记会被值覆盖。
我觉得比较绕，思维量不大。为了这个 $O(1)$ 的空间复杂度付出了太多。生产中是垃圾代码。
240. Search a 2D Matrix II
这题给了一个有规律的矩阵，它的每一行都是递增的，每一列也是递增的。不过和 I 不同，I 还要求每行的首元素大于上一行的尾元素。所以 I 用的是二分查找的思路，因为整体有序，这题不是这种思路。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m = matrix.size(), n = matrix[0].size();
int i = m - 1, j = 0;
while (i >= 0 && j < n) {
if (matrix[i][j] == target) return true;
else if (matrix[i][j] > target) i--;
else j++;
}
return false;
}
};
|
比较巧妙。发现，如果选择左下角或者右上角，有一个不错的寻路算法。
以左下角为例吧，从这个点开始。如果矩阵元素值大于目标，说明该行右侧一定不会有可行解了，该往上走。而如果矩阵元素值小于目标，说明该列上方不会有可行解了，该往右走。这样对于向上和向右就有两种不存在交集的判断方法。
在右上角出发则也是同理。
如果没见过这类题，我觉得很难想出来。所以总而言之，矩阵这类题目就是，见过了就会做，没见过，需要想很久。
