Rotate Image

顺时针90度旋转矩阵
要求就地更改(不能创建另外一个矩阵)

我的做法

思路:

使用下标来获取元素更方便
从外层到内层, 一层层旋转, 每次旋转n个, 每层旋转4次
不可避免需要保存一组数值

具体代码:

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();

        for (int i = 0; i < n / 2; ++i){
            // backup first stream
            vector<int> backup ((matrix.begin() + i)->begin() + i + 1, 
                (matrix.begin() + i)->end() - i);

                for (int col = i + 1, row = n - i - 2; col < n - i; ++col, --row)
                    matrix[i][col] = matrix[row][i];

                for (int row = i, col = i; row < n - i - 1; ++row, ++col)
                    matrix[row][i] = matrix[n - 1 - i][col];

                for (int col = i, row = n - i - 1; col < n - i - 1; ++col, --row)
                    matrix[n - 1 - i][col] = matrix[row][n - i - 1];

                for (int row = n - 1 - i, t = backup.size() - 1; t >= 0; --row, --t)
                    matrix[row][n - i - 1] = backup[t];
        }
    }
};

最后结果:

dalao的做法

class Solution {
public:
    void swapLR(vector<vector<int>>& matrix) {
        int n = matrix.size();
        for (int i = 0; i < n; i++) {
            int l = 0;
            int r = n-1;
            while(l<r) {
                int temp = matrix[i][l];
                matrix[i][l++] = matrix[i][r];
                matrix[i][r--] = temp;
            }
        }
    }

    void swapdig(vector<vector<int>>& matrix) {
        int n = matrix.size();
        for (int i = 0; i < n-1; i++) {
            for (int j = 0; j < n-1-i; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n-1-j][n-1-i];
                matrix[n-1-j][n-1-i] = temp;
            }
        }
    }

    void rotate(vector<vector<int>>& matrix) {
        swapLR(matrix);
        swapdig(matrix);
    }
};

首先分析 swapLR 函数:

emmmm, 它好像将左右的数据对换了

emmm, 还是看不懂有什么规律,

6啊…, 更改后的行就是最终结果的列, 只要遍历倒叙一遍就可以了
这种思路是如何得出的? 需要哪方面的知识么?
思路这种东西好难弥补, 我自认为不出意外的话, 是无法想到这一点的