牛易疯先森的开发记录
0%

矩阵翻转

发表于

在做今天的每日一题：832. 翻转图像时，看到了之前的笔记，里面提到了一道类似的题目48. 旋转图像，如果没记错的话，它应该是去年的一道每日一题。当时还想着要把沿对角线翻转的代码给记住的，但是现在也不记得了，为了完成去年前的任务，晚上花了点时间把相关翻转代码记录一下。

经验

给定一个 n × n 的二维矩阵 matrix(eg: [[1,2,3],[4,5,6],[7,8,9]])，在遍历中分别输出行下标(i)和列表(j)的值。
以下的代码，记住画个图再来推理一篇，记忆效果会更好。

水平上下翻转

行和是 n-1, 遍历一半；列正常处理。

1
2
3
4
5
6
7
8
9
10
11
for (int i = 0; i < n/2; i++) {
    for (int j = 0; j < n; j++) {
        swap(matrix[i][j], matrix[n-i-1][j]);
        cout << '[' << i << ',' << j << ']'<< endl;
    }
}
/*
[0,0]
[0,1]
[0,2]
*/

垂直左右翻转

行正常处理；列和是 n-1, 遍历一半。

1
2
3
4
5
6
7
8
9
10
11
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n/2; j++) {
        swap(matrix[i][j], matrix[i][n-j-1]);
        cout << '[' << i << ',' << j << ']'<< endl;        
    }
}
/*
[0,0]
[1,0]
[2,0]
*/

主对角线（左上-右下）翻转

交换i, j.

1
2
3
4
5
6
7
8
9
10
11
for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++) {
        swap(matrix[i][j], matrix[j][i]);
        cout << '[' << i << ',' << j << ']'<< endl;
    }
}
/*
[1,0]
[2,0]
[2,1]
*/

副对角线（右上-左下）翻转

交换i, j.

1
2
3
4
5
6
7
8
9
10
11
for (int i = 0; i < n-1; i++) {
    for(int j = 0; j < n-i-1; j++) {
        swap(matrix[i][j], matrix[n-j-1][n-i-1]);
        cout << "[" << i << "," << j << "]" << endl;
    }
}
/*
[0,0]
[0,1]
[1,0]
*/

套路

  1. 顺时针90度：主对角线（左上-右下）翻转，再垂直左右翻转
  2. 逆时针90度：主对角线（左上-右下）翻转，再水平上下翻转
  3. 顺时针180度：主对角线（左上-右下）翻转，再副对角线（右上-左下）翻转
  4. 逆时针180度：主对角线（左上-右下）翻转，再副对角线（右上-左下）翻转

48. 旋转图像

顺时针旋转 90 度。

用套路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
class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        if (!n) return;
        // 主对角线翻转
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                myswap(matrix[i][j], matrix[j][i]);
            }
        }
        // 垂直左右翻转
        int mid = n >> 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < mid; j++) {
                myswap(matrix[i][j], matrix[i][n-j-1]);
            }
        }
    }

    void myswap(int& a, int& b) {
        a = a ^ b;
        b = a ^ b;
        a = a ^ b;
    }
};