友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
48. 旋转图像
给定一个 n×n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出：[[7,4,1],[8,5,2],[9,6,3]]
示例 2：
输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]] 输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
提示：
-
n == matrix.length == matrix[i].length -
1 <= n <= 20 -
-1000 <= matrix[i][j] <= 1000
思路分析
将矩阵周围一圈，划分成四个区域。如下图所示：
这样每个区域长度相等，使用循环做数字交换即可。另外，借助回溯思想，利用递归推进层次。
下面辅助矩阵的方案也不错：
官方题解中的翻转矩阵的方案也不错！
-
一刷
-
二刷
-
三刷
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);
}
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
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-04-25 17:00:44
*/
public void rotate(int[][] matrix) {
dfs(matrix, 0, 0,
matrix.length - 1, matrix[matrix.length - 1].length - 1);
}
private void dfs(int[][] matrix,
int startRow, int startColumn,
int endRow, int endColumn) {
if (startRow >= endRow || startColumn >= endColumn) {
return;
}
int length = endRow - startRow;
for (int i = 0; i < length; i++) {
// 左上角： matrix[startRow][startColumn + i] // 向右 column 增加
// 右上角： matrix[startRow + i][endColumn] // 向下 row 增加
// 右下角： matrix[endRow][endColumn - i] // 向左 column 减少
// 左下角： matrix[endRow - i][startColumn] // 向上 row 减少
int temp = matrix[startRow][startColumn + i];
matrix[startRow][startColumn + i] = matrix[endRow - i][startColumn];
matrix[endRow - i][startColumn] = matrix[endRow][endColumn - i];
matrix[endRow][endColumn - i] = matrix[startRow + i][endColumn];
matrix[startRow + i][endColumn] = temp;
}
dfs(matrix, startRow + 1, startColumn + 1,
endRow - 1, endColumn - 1);
}