返回
22
05/2015

[LeetCode] Rotate Image

分类： c/c++, oj | 浏览 (2528) | 评论 (0)

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?

解题思路：


题目要求原地算法。假设坐标轴如上所示。顺时针旋转90度，相当于先将图片沿着x=n/2翻转，然后再将图片沿着斜对角线y=x翻转。代码如下：

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
class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int len = matrix.size();
        //先将矩阵左右翻转
        for(int i = 0; i<len; i++){
            reverse(matrix[i]);
        }
        //再将矩阵沿着x=y翻转
        for(int i=0; i<len; i++){
            for(int j=0; j<len - i; j++){
                int temp = matrix[i][j];
                matrix[i][j]=matrix[len-j-1][len-i-1];
                matrix[len-j-1][len-i-1]=temp;
            }
        }
    }
     
    void reverse(vector<int>& v){
        int len = v.size();
        int i=0, j=len-1;
        while(i<j){
            swap(v, i, j);
            i++;
            j--;
        }
    }
     
    void swap(vector<int>& v, int i, int j){
        int temp = v[i];
        v[i] = v[j];
        v[j] = temp;
    }
};


« [LeetCode] House Robber II
[LeetCode] Contains Duplicate »

0 条评论

    暂无评论。

    发表评论

    电子邮件地址不会被公开。 必填项已用 * 标注