https://leetcode.com/problems/rotate-image/
https://www.jianshu.com/p/afd50b2b22ea
- precheck
https://zhuhan0.blogspot.com/2017/04/leetcode-48-rotate-image.html
X.
http://bangbingsyb.blogspot.com/2014/11/leetcode-rotate-image.htm
觉得“剥洋葱”法一层一层地旋转最容易理解和写对。注意这里offset的使用以及中止条件start<end
https://zhuhan0.blogspot.com/2017/04/leetcode-48-rotate-image.html
X.
http://buttercola.blogspot.com/2014/08/leetcode-rotate-image.html
http://www.voidcn.com/article/p-tohbealf-bko.html
The problem is that Java is pass by value not by refrence! “matrix” is just a reference to a 2-dimension array. If “matrix” is assigned to a new 2-dimension array in the method, the original array does not change. Therefore, there should be another loop to assign each element to the array referenced by “matrix”. Check out “ Java pass by value .”
You are given an n x n 2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).
Note:
You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.
Example 1:
Given input matrix = [ [1,2,3], [4,5,6], [7,8,9] ], rotate the input matrix in-place such that it becomes: [ [7,4,1], [8,5,2], [9,6,3] ]
Example 2:
Given input matrix = [ [ 5, 1, 9,11], [ 2, 4, 8,10], [13, 3, 6, 7], [15,14,12,16] ], rotate the input matrix in-place such that it becomes: [ [15,13, 2, 5], [14, 3, 4, 1], [12, 6, 8, 9], [16, 7,10,11] ]https://www.cnblogs.com/grandyang/p/4389572.html
在计算机图像处理里，旋转图片是很常见的，由于图片的本质是二维数组，所以也就变成了对数组的操作处理，翻转的本质就是某个位置上数移动到另一个位置上，比如用一个简单的例子来分析：
1 2 3 7 4 1
4 5 6 --> 8 5 2
7 8 9 9 6 3
对于90度的翻转有很多方法，一步或多步都可以解，我们先来看一种直接的方法，对于当前位置，计算旋转后的新位置，然后再计算下一个新位置，第四个位置又变成当前位置了，所以这个方法每次循环换四个数字，如下所示：
1 2 3 7 2 1 7 4 1
4 5 6 --> 4 5 6 --> 8 5 2
7 8 9 9 8 3 9 6 3
void rotate(vector<vector<int> > &matrix) { int n = matrix.size(); for (int i = 0; i < n / 2; ++i) { for (int j = i; j < n - 1 - i; ++j) { int tmp = matrix[i][j]; matrix[i][j] = matrix[n - 1 - j][i]; matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j]; matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i]; matrix[j][n - 1 - i] = tmp; } } }
- precheck
https://zhuhan0.blogspot.com/2017/04/leetcode-48-rotate-image.html
纯模拟，从外到内一圈一圈的转，但这个方法太慢。
A[i][j] -> A[j][n-1-i] -> A[n-1-i][n-1-j] -> A[n-1-j][i] -> A[i][j]
public void rotate(int[][] matrix) { for (int i = 0; i < matrix.length / 2; i++) { for (int j = i; j < matrix.length - i - 1; j++) { rotate(matrix, i, j); } } } private void rotate(int[][] matrix, int i, int j) { int n = matrix.length; int temp = matrix[i][j]; matrix[i][j] = matrix[n - 1 - j][i]; matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j]; matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i]; matrix[j][n - 1 - i] = temp; }
X.
最后再来看一种方法，这种方法首先对原数组取其转置矩阵，然后把每行的数字翻转可得到结果，如下所示(其中蓝色数字表示翻转轴)：
1 2 3 1 4 7 7 4 1
4 5 6 --> 2 5 8 --> 8 5 2
7 8 9 3 6 9 9 6 3
void rotate(vector<vector<int> > &matrix) {
int n = matrix.size();
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
swap(matrix[i][j], matrix[j][i]);
}
reverse(matrix[i].begin(), matrix[i].end());
}
}
觉得“剥洋葱”法一层一层地旋转最容易理解和写对。注意这里offset的使用以及中止条件start<end
void rotate(vector<vector<int> > &matrix) { int start = 0, end = matrix.size()-1; while(start<end) { for(int i=start; i<end; i++) { // rotate a layer int offset = i - start; int temp = matrix[start][i]; matrix[start][i] = matrix[end-offset][start]; matrix[end-offset][start] = matrix[end][end-offset]; matrix[end][end-offset] = matrix[start+offset][end]; matrix[start+offset][end] = temp; } start++; end--; } }X. https://leetcode.com/problems/rotate-image/discuss/18872/A-common-method-to-rotate-the-image
* clockwise rotate
* first reverse up to down, then swap the symmetry
* 1 2 3 7 8 9 7 4 1
* 4 5 6 => 4 5 6 => 8 5 2
* 7 8 9 1 2 3 9 6 3
*/
void rotate(vector<vector<int> > &matrix) {
reverse(matrix.begin(), matrix.end());
for (int i = 0; i < matrix.size(); ++i) {
for (int j = i + 1; j < matrix[i].size(); ++j)
swap(matrix[i][j], matrix[j][i]);
}
}
/*
* anticlockwise rotate
* first reverse left to right, then swap the symmetry
* 1 2 3 3 2 1 3 6 9
* 4 5 6 => 6 5 4 => 2 5 8
* 7 8 9 9 8 7 1 4 7
*/
void anti_rotate(vector<vector<int> > &matrix) {
for (auto vi : matrix) reverse(vi.begin(), vi.end());
for (int i = 0; i < matrix.size(); ++i) {
for (int j = i + 1; j < matrix[i].size(); ++j)
swap(matrix[i][j], matrix[j][i]);
}
} public void rotate(int[][] matrix) { // check if matrix is null or empty or length equals to 1 if (matrix == null || matrix.length < 2) return; int n = matrix.length; for (int layer = 0; layer < n/2; layer++) { int first = layer; int last = n - layer - 1; for (int i = first; i < last; i++) { int offset = i - first; int top = matrix[first][i]; // left -> top matrix[first][i] = matrix[last - offset][first]; // bottom -> left matrix[last - offset][first] = matrix[last][last - offset]; // right -> bottom matrix[last][last - offset] = matrix[i][last]; // top - > right; matrix[i][last] = top; } } }public void rotate(int[][] matrix) { for (int i = 0; i < matrix.length / 2; i++) { for (int j = i; j < matrix.length - i - 1; j++) { rotate(matrix, i, j); } } } private void rotate(int[][] matrix, int i, int j) { int n = matrix.length; int temp = matrix[i][j]; matrix[i][j] = matrix[n - 1 - j][i]; matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j]; matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i]; matrix[j][n - 1 - i] = temp; }
X.
http://buttercola.blogspot.com/2014/08/leetcode-rotate-image.html
http://www.voidcn.com/article/p-tohbealf-bko.html
public void rotate(int[][] matrix) {
if(matrix == null || matrix.length==0)
return ;
int m = matrix.length;
int[][] result = new int[m][m];
for(int i=0; i<m; i++){
for(int j=0; j<m; j++){
result[j][m-1-i] = matrix[i][j];
}
}
for(int i=0; i<m; i++){
for(int j=0; j<m; j++){
matrix[i][j] = result[i][j];
}
}
}
In the following solution, a new 2-dimension array is created to store the rotated matrix, and the result is assigned to the matrix at the end. This is WRONG! Why?
public class Solution {
public void rotate(int[][] matrix) {
if(matrix == null || matrix.length==0)
return ;
int m = matrix.length;
int[][] result = new int[m][m];
for(int i=0; i<m; i++){
for(int j=0; j<m; j++){
result[j][m-1-i] = matrix[i][j];
}
}
matrix = result;
}
}
The problem is that Java is pass by value not by refrence! “matrix” is just a reference to a 2-dimension array. If “matrix” is assigned to a new 2-dimension array in the method, the original array does not change. Therefore, there should be another loop to assign each element to the array referenced by “matrix”. Check out “ Java pass by value .”
