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的：
- 直接设置top, bottom, left, right四个变量，表示圈定当前要旋转的正方形范围，然后按偏移计算位置，比如左上角的先和右上角交换，然后继续左上角和右下角交换这样即可。
- 观察规律，(x,y)要变为(y, n – 1 – x)，为了不丢失元素，我逆序的来，先把(x,y)的值给temp，然后把之后要到(x,y)坐标的(就是(n – 1 – y, x))值给(x,y)，然后为了不重复计算，第一行列的范围[0, n- 2], 第二行[1,n-3]一次类推即可。
- 看到别人的，沿着 这样的 / 对称轴交换，之后只要最后一行变为第一行，倒数第二行变为第二行即进行的逆序即可。
方法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) { 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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
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
|
1 2 3 4 5 6 7 8 9 10 |
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
|
1 2 3 4 5 6 7 8 9 10 11 |
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/
本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处：细语呢喃 > leetcode Rotate Image
本文地址：https://www.hrwhisper.me/leetcode-rotate-image/