leetcode Rotate Image

leetcode Rotate Image

You are given an n x n 2D matrix representing an image. Rotate the image by 90 degrees (clockwise). Follow up: Could you do this in-place?

题目地址：leetcode Rotate Image 题意：给你一个矩阵，让你顺时针旋转90° 思路： 不讨论复制一个数组然后在旋转的方法，因为太简单了。 下面的方法都是in-place的：

1. 直接设置top, bottom, left, right四个变量，表示圈定当前要旋转的正方形范围，然后按偏移计算位置，比如左上角的先和右上角交换，然后继续左上角和右下角交换这样即可。
2. 观察规律，(x,y)要变为(y, n - 1 - x)，为了不丢失元素，我逆序的来，先把(x,y)的值给temp，然后把之后要到(x,y)坐标的(就是(n - 1 - y, x))值给(x,y)，然后为了不重复计算，第一行列的范围[0, n- 2], 第二行[1,n-3]一次类推即可。
3. 看到别人的，沿着 这样的 / 对称轴交换，之后只要最后一行变为第一行，倒数第二行变为第二行即进行的逆序即可。

方法1：

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        if(matrix.empty())
            return;
        int top = 0, bottom = matrix.size() - 1;
        int left = 0, right = matrix[0].size() - 1;
        for(;top < bottom && left < right; ++top, ++left, --bottom, --right){
            for(int i = left; i < right; ++i){
                int dis = i - left;
                
                int row = top + dis;
                int col = right;
                swap(matrix[top][i], matrix[row][col]);
                
                row = bottom;
                col = right - dis;
                swap(matrix[top][i], matrix[row][col]);
                
                row = bottom - dis;
                col = left;
                swap(matrix[top][i], matrix[row][col]);
            }
        }
    }
};

C++思路1

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        int start = 0, end = n - 2;
        while(start <= end){
            int i = start;
            for(int j = start; j <= end; ++j){
                int cx = start, cy = j;
                int temp = matrix[cx][cy];
                for(int k = 0; k < 3; ++k){
                    int nx = n - 1 - cy, ny = cx;
                    matrix[cx][cy] = matrix[nx][ny];
                    cx = nx;
                    cy = ny;
                }
                matrix[cx][cy] = temp;
            }
            ++start;
            end = n - 2 - start;
        }
    }
};

C++ 思路2

class Solution {
public:
	void rotate(vector<vector<int> > &matrix){
		int n = matrix.size();
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n - i - 1; j++)
				swap(matrix[i][j], matrix[n - j - 1][n - i - 1]);
		reverse(matrix.begin(), matrix.end());
	}
};

  python 思路2

class Solution(object):
    def rotate(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: void Do not return anything, modify matrix in-place instead.
        """
        n = len(matrix)
        for i in range(len(matrix)):
            for j in range(len(matrix) - i - 1):
                matrix[i][j], matrix[n - j - 1][n - i - 1] = matrix[n - j - 1][n - i - 1], matrix[i][j]
        matrix.reverse()

本文是leetcode如下的题解

• 48. Rotate Image

更多题解可以查看： https://www.hrwhisper.me/leetcode-algorithm-solution/