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如下的题解
更多题解可以查看： https://www.hrwhisper.me/leetcode-algorithm-solution/
