友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
48. Rotate Image
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] ]
思路分析
将矩阵周围一圈，划分成四个区域。如下图所示：
这样每个区域长度相等，使用循环做数字交换即可。另外，借助回溯思想，利用递归推进层次。
下面辅助矩阵的方案也不错：
官方题解中的翻转矩阵的方案也不错！
-
一刷
-
二刷
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/**
* Runtime: 0 ms, faster than 100.00% of Java online submissions for Rotate Image.
*
* Memory Usage: 36.3 MB, less than 100.00% of Java online submissions for Rotate Image.
*
* @author D瓜哥 · https://www.diguage.com
* @since 2019-10-24 00:57:55
*/
public void rotate(int[][] matrix) {
if (Objects.isNull(matrix) || matrix.length == 0) {
return;
}
int length = matrix.length;
// 先交换行，这样操作更方便，但是也会有更多的额外空间。
for (int i = 0; i < length / 2; i++) {
int[] temp = matrix[i];
matrix[i] = matrix[length - 1 - i];
matrix[length - 1 - i] = temp;
}
// printMatrix(matrix);
for (int i = 0; i < length; i++) {
for (int j = 0; j < i; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
}
/**
* Runtime: 0 ms, faster than 100.00% of Java online submissions for Rotate Image.
*
* Memory Usage: 36.2 MB, less than 100.00% of Java online submissions for Rotate Image.
*/
public void rotate1(int[][] matrix) {
if (Objects.isNull(matrix) || matrix.length == 0) {
return;
}
int length = matrix.length;
for (int i = 0; i < length; i++) {
for (int j = 0; j < i; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
printMatrix(matrix);
for (int i = 0; i < length; i++) {
for (int j = 0; j < length / 2; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[i][length - j - 1];
matrix[i][length - j - 1] = temp;
}
}
}
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
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2024-09-19 17:35:53
*/
public void rotate(int[][] matrix) {
backtrack(matrix, 0, 0,
matrix.length, matrix.length);
}
private void backtrack(int[][] matrix,
int row, int column,
int rLen, int cLen) {
if (rLen <= 1) {
return;
}
// 旋转
for (int i = 0; i < cLen - 1; i++) {
int tmp = matrix[row][column + i];
matrix[row][column + i] = matrix[row + rLen - 1 - i][column];
matrix[row + rLen - 1 - i][column] = matrix[row + rLen - 1][column + cLen - 1 - i];
matrix[row + rLen - 1][column + cLen - 1 - i] = matrix[row + i][column + cLen - 1];
matrix[row + i][column + cLen - 1] = tmp;
}
backtrack(matrix, row + 1, column + 1, rLen - 2, cLen - 2);
}