首页 > itarticle > 【leetcode】48. rotate image

【leetcode】48. rotate image

admin 12月 02, 2020 0

1.题目描述

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

给定一个 n × n 的二维矩阵表示一个图像。

将图像顺时针旋转 90 度。

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.

说明：

你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。

示例 1:

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
 
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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
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]
]

2.Solutions

here give a common method to solve the image rotation problems.

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
 

 * 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 (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]);
    }
}

Java Code

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
 

 * 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
 */
public static void (int[][] matrix) {
    // reverse each row of the image
    int startRow = 0,endRow = matrix[startRow].length - 1;
    for (; startRow < endRow; startRow++,endRow--) {
        for (int col = 0; col < matrix.length; col++) {
            int temp = matrix[startRow][col];
            matrix[startRow][col] = matrix[endRow][col];
            matrix[endRow][col] = temp;
        }
    }

    // Turns rows into cols and vice versa
    for(int i = 0; i < matrix.length; i++) {
        for(int j = i + 1; j < matrix[i].length; j++) {
            int tmp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = tmp;
        }
    }
}

（完）

微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能