leetcode 48. Rotate Image (旋转方阵(in place))

2017-04-12 · 2 min read · leetcode

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?

题意：给一个n*n的方阵，要求顺时针旋转90度。

思路：(x,y)->(y,n-1-x);

要求in-place的做法的话，其实是若干长度为4的环，保护一个节点，然后顺次做就好了。

然后对于那些标记已经做过选旋转的问题，实际上没有必要进行标记。

对于偶数，只需要处理左上角hf * hf个,奇数只需要处理左上角hf*(hf-1)个。

其中hf = (n+1)/2

 11 2 3      (0,0) ->(0,2)
 24 5 6
 37 8 9                    
 4
 5
 6
 77 4 1
 88 5 2
 99 6 3
10
11  0 1 2 3
120 1 2 3 4   (0,0)->(0,3)  (0,1)->(1,3)  (0,2)->(2,3) (0,3)->(3,3)
131 5 6 7 8   (1,1)->(1,2)  (1,2)->(2,2)  (2,2)->(2,1)  
142 9 A B C   (1,0)->(0,2) (2,0)->(0,1) 
153 D E F G   //只搞四分之一角落
16
17  0 1 2 3
180 D 9 5 1
191 E A 6 2
202 F B 7 3
213 G C 8 4
22
23
241 2
253 4
26
27
283 1
294 2
30
311  2  3  4  5
326  7  8  9  10
3311 12 13 14 15
3416 17 18 19 20
3521 22 23 24 25

1/* ***********************************************
2Author :111qqz
3Created Time :2017年04月12日 星期三 19时56分40秒
4File Name :48.cpp
5************************************************ */
6class Solution {

 1public:
 2    int n;
 3    void rotate(int &x,int &y,int n)
 4    {
 5    int nx,ny;
 6    nx = y;
 7    ny = n-1-x;
 8    //printf("(%d,%d)->(%d,%d)\n",x,y,nx,ny);
 9    x = nx;
10    y = ny;
11    }
12    void pr(vector<vector<int> >&maze)
13    {
14    for ( int i = 0 ; i < n ; i++)
15        for ( int j = 0 ; j < n ; j++)
16        printf("%c%c",maze[i][j]>9?char(maze[i][j]-10+'A'):maze[i][j]+'0',j==n-1?'\n':' ');
17    }
18    void rotate(vector<vector<int>>& maze) {
19    n = maze.size();
20//    pr(maze);
21    int hn = (n+1)/2;
22    int tmp=-1;
23    int curx=0,cury=0;
24
25    for ( int i = 0 ; i < hn ; i++ )
26    {
27        for ( int j = 0 ; j < hn-n%2 ; j++) //根据奇偶分情况
28        {
29        curx = i;
30        cury = j;
31        rotate(curx,curx,n);
32        tmp = maze[curx][cury];
33        maze[curx][cury] = maze[i][j];
34        for ( int k = 0 ; k < 4 ; k++) //环的长度固定为4.
35        {
36            rotate(curx,cury,n);
37            swap(tmp,maze[curx][cury]);
38    //      printf("%d\n",tmp);
39        }
40
41        }
42    }  
43
44
45}
46
47};