48. Rotate Image
Analysis
题意很简单，将矩阵顺时针旋转 90° 即可。
Code
method 1
尽管题目限定了原地交换，但还是先不按照要求做一下。
抛开限制条件之后，这实际上就是矩阵的行转列问题。1
2
3
4
5
6
7
8
9
10
11
12
13
14class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size(), r = 0, c = 0;
vector<vector<int>> ret(n, vector<int>(n));
for(int i = n - 1; i >= 0; i--) {
for(int j = 0; j < n; j++) {
ret[r++][c] = matrix[i][j];
}
r = 0, c++;
}
matrix = ret;
}
};
虽然这段代码也能过，但是没有找出转换规律，把行列互换的思想带入到代码内：1
2
3
4
5
6
7
8
9
10
11
12
13class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size();
vector<vector<int>> ret(n, vector<int>(n));
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
ret[j][n - 1 - i] = matrix[i][j];
}
}
matrix = ret;
}
};
这样就可以看出 matrix 与转换后的矩阵的坐标规律了。
method 2
现在，再来思考一下加入限制条件后的方法。
按照前面的思路，对于矩阵中的任意元素，可以得到：$ret[c][n - 1 - r] = matrix[r][c]$，也就是说，需要在 $(c, n - 1 - r)$ 这个位置填入 $matrix[r][c]$。这样，如果直接交换 $matrix[r][c]$ 和 $matrix[c][n - 1 - r]$ 不就可以达到原地交换的效果了吗？但问题是 $matrix[c][n - 1 - r]$ 转换后的位置不是 $(r, c)$，那是什么？按照前面的思路，$matrix[c][n - 1 - r]$ 的位置应该是 $matrix[n - 1 - r][n - 1 - c]$。
此时，可以发现由于矩阵有 4 条边，所以每一轮交换中也是 4 个数在进行交换。按照规律，可以很容易的找到这 4 个数，并且相互交换，这样可以得到下面的过程：1
2
3swap(matrix[r][c], matrix[c][n - 1 - r])
swap(matrix[r][c], matrix[n - 1 - r][n - 1 - c])
swap(matrix[r][c], matrix[n - 1 - c][r])
注意因为交换位置之后，原来位于其他位置的元素在进行交换后都到了 $(r, c)$ 这个位置，所以实际上每次都是这个位置在进行交换。
明确交换过程后，还需要解决一个问题，那就是如何枚举需要交换的元素呢？
此时，按照矩阵的边长又可以分成 2 种情况：
- 奇数，矩阵中心的元素不用交换，剩余元素需要交换。
- 偶数，矩阵所有元素都需要交换。
另外，由于每次交换是 4 个元素一起交换，所以枚举了 1 个之后，剩下的元素是已经交换完成了，就不用再枚举了，那也就是说实际上只用枚举的元素个数是：
$$\begin{cases}
\frac {n^2}{4} & n 是偶数 \\
\frac {n^2 - 1}{4} & n 是奇数 \\
\end{cases}
$$
显然，r 的取值范围是 $[0, n / 2)$，那 c 呢？
实际上，枚举的方法也有多种，所以 c 的范围也有区别。这里举两种枚举方法：
一种是从外层枚举到内层的方法（也可以认为是顺时针交换），此时 c 的范围是 $[r, end - 1)$，end - 1 就是内层矩阵列的边界，end 这个值一开始是等于 n 的，但是交换完一层元素后，需要减 1，再把坐标移到内层进行交换。1
2
3
4
5
6
7
8
9
10
11
12
13
14class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size(), end = n;
for(int r = 0; r < n / 2; r++) {
for(int c = r; c < end - 1; c++) {
swap(matrix[r][c], matrix[c][n - 1 - r]);
swap(matrix[r][c], matrix[n - 1 - r][n - 1 - c]);
swap(matrix[r][c], matrix[n - 1 - c][r]);
}
end--;
}
}
};
这种思路稍微可能稍微有点绕...
还有一种是将矩阵分块，将矩阵按照元素个数相等的规则分成 4 块，这样只用枚举第一块的元素，就可以完成整个矩阵的交换了，此时 c 的范围就是 $[0, \frac{n + 1}{2})$ 了。1
2
3
4
5
6
7
8
9
10
11
12
13class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size();
for(int r = 0; r < n / 2; r++) {
for(int c = 0; c < (n + 1) / 2; c++) {
swap(matrix[r][c], matrix[c][n - 1 - r]);
swap(matrix[r][c], matrix[n - 1 - r][n - 1 - c]);
swap(matrix[r][c], matrix[n - 1 - c][r]);
}
}
}
};
感觉这种思路更直接一点。
method 3
现在再来回头看这个问题，利用矩阵变换（前面提到的行列互换），可以很轻松的得到结果，但需要消耗额外空间；为了不消耗额外空间，就无法行列互换，只能找出坐标规律，直接交换。如果能把矩阵的变换与找规律结合起来，能不能实现原地交换呢？
答案是可以的...
以样例中的矩阵
$$\begin{bmatrix}
5 & 1 & 9 & 11 \\
2 & 4 & 8 & 10 \\
13 & 3 & 6 & 7 \\
15 & 14 & 12 & 16 \\
\end{bmatrix}$$
按照水平轴翻转，得到
$$\begin{bmatrix}
15 & 14 & 12 & 16 \\
13 & 3 & 6 & 7 \\
2 & 4 & 8 & 10 \\
5 & 1 & 9 & 11 \\
\end{bmatrix}$$
再按主对角线翻转（也就是求矩阵的转置矩阵），得到
$$\begin{bmatrix}
15 & 13 & 2 & 5 \\
14 & 3 & 4 & 1 \\
12 & 6 & 8 & 9 \\
16 & 7 & 10 & 11 \\
\end{bmatrix}$$
这就是需要的结果...😂
水平轴翻转只需要枚举一半的矩阵元素即可：1
2
3
4
5for(int i = 0; i < n / 2; i++) {
for(int j = 0; j < n; j++) {
swap(matrix[i][j], matrix[n - 1 - i][j]);
}
}
同样，主对角线翻转也只需要枚举一半的矩阵元素：1
2
3
4
5for(int i = 0; i < n; i++) {
for(int j = i; j < n; j++) {
swap(matrix[i][j], matrix[j][i]);
}
}
联立起来，就可以得到完整的通过代码了：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size();
for(int i = 0; i < n / 2; i++) {
for(int j = 0; j < n; j++) {
swap(matrix[i][j], matrix[n - 1 - i][j]);
}
}
for(int i = 0; i < n; i++) {
for(int j = i; j < n; j++) {
swap(matrix[i][j], matrix[j][i]);
}
}
}
};
为什么可以这样做呢？
水平轴翻转时坐标的变换规律是：$matrix[r][c] <=> matrix[n - 1 - r][c]$。
主对角线翻转时坐标的变换规律是：$matrix[r][c] <=> matrix[c][r] = matrix[c][n - 1 - r]$。
这与前面的规律实际上是一致的...只不过水平轴翻转时，只有主对角线上的元素被交换到了最终位置。
再回头想想，如果一开始将矩阵转置，然后再将矩阵竖直翻转不也可以得到最终结果吗？哈哈
另外，再说点题外话。按照线性代数的理论，像这样的矩阵变换应该可以通过乘以一个特殊的单位矩阵得到...也许还有更简单的方法吧...
1886. Determine Whether Matrix Can Be Obtained By Rotation
Analysis
这个题有点像上面那个题的升级版，依次顺时针转换 90°，如果与给定矩阵相同，就返回 true，否则返回 false。
有了前面的思考，这个题简直不要太简单哈。
一个矩阵最多按 90° 旋转 4 次就回到它最初的样子了，所以，这个题最多旋转 3 次就可以得到结果了。
Code
直接复制粘贴了😁...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
41class Solution {
public:
bool findRotation(vector<vector<int>>& mat, vector<vector<int>>& target) {
if(mat == target) return true;
int n = mat.size();
for(int i = 0; i < n / 2; i++) {
for(int j = 0; j < n; j++) {
swap(mat[i][j], mat[n - 1 - i][j]);
}
}
for(int i = 0; i < n; i++) {
for(int j = i; j < n; j++) {
swap(mat[i][j], mat[j][i]);
}
}
if(mat == target) return true;
for(int i = 0; i < n / 2; i++) {
for(int j = 0; j < n; j++) {
swap(mat[i][j], mat[n - 1 - i][j]);
}
}
for(int i = 0; i < n; i++) {
for(int j = i; j < n; j++) {
swap(mat[i][j], mat[j][i]);
}
}
if(mat == target) return true;
for(int i = 0; i < n / 2; i++) {
for(int j = 0; j < n; j++) {
swap(mat[i][j], mat[n - 1 - i][j]);
}
}
for(int i = 0; i < n; i++) {
for(int j = i; j < n; j++) {
swap(mat[i][j], mat[j][i]);
}
}
if(mat == target) return true;
return false;
}
};
把上面写的函数抄过来，封装一下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size();
for(int i = 0; i < n / 2; i++) {
for(int j = 0; j < n; j++) {
swap(matrix[i][j], matrix[n - 1 - i][j]);
}
}
for(int i = 0; i < n; i++) {
for(int j = i; j < n; j++) {
swap(matrix[i][j], matrix[j][i]);
}
}
}
bool findRotation(vector<vector<int>>& mat, vector<vector<int>>& target) {
if(mat == target) return true;
for(int i = 0; i < 3; i++) {
rotate(mat);
if(mat == target) return true;
}
return false;
}
};
嗯，看起来舒服多了...
Summary
不知道这种矩阵变换的实际应用场景是什么...突然有点好奇了...
