Sunday, November 23, 2014

[LeetCode] 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?

思路:

这题概念上很简单,有几种方法可以做。比如将每个[i, j]对应旋转对称的四个点的坐标算出来,然后pixel by pixel的旋转。但个人感觉这种计算面试中比较容易出错。想了看了几种方法后,觉得“剥洋葱”法一层一层地旋转最容易理解和写对。注意这里offset的使用以及中止条件start<end。


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    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--;
        }
    }
};

1 comment: