Note: This article is available in Chinese only. 本文暂无英文版本。
View original
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
1A
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)
15D E F G //只搞四分之一角落
16
17 0 1 2 3
18D 9 5 1
19E A 6 2
20F B 7 3
21G 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
36
37
38
39
40
41
42
43
44
45
46
47/* ***********************************************
48Author :111qqz
49Created Time :2017年04月12日 星期三 19时56分40秒
50File Name :48.cpp
51************************************************ */
52class Solution {
53
54public:
55 int n;
56 void rotate(int &x,int &y,int n)
57 {
58 int nx,ny;
59 nx = y;
60 ny = n-1-x;
61 //printf("(%d,%d)->(%d,%d)\n",x,y,nx,ny);
62 x = nx;
63 y = ny;
64 }
65 void pr(vector<vector<int> >&maze)
66 {
67 for ( int i = 0 ; i < n ; i++)
68 for ( int j = 0 ; j < n ; j++)
69 printf("%c%c",maze[i][j]>9?char(maze[i][j]-10+'A'):maze[i][j]+'0',j==n-1?'\n':' ');
70 }
71 void rotate(vector<vector<int>>& maze) {
72 n = maze.size();
73// pr(maze);
74 int hn = (n+1)/2;
75 int tmp=-1;
76 int curx=0,cury=0;
77
78 for ( int i = 0 ; i < hn ; i++ )
79 {
80 for ( int j = 0 ; j < hn-n%2 ; j++) //根据奇偶分情况
81 {
82 curx = i;
83 cury = j;
84 rotate(curx,curx,n);
85 tmp = maze[curx][cury];
86 maze[curx][cury] = maze[i][j];
87 for ( int k = 0 ; k < 4 ; k++) //环的长度固定为4.
88 {
89 rotate(curx,cury,n);
90 swap(tmp,maze[curx][cury]);
91 // printf("%d\n",tmp);
92 }
93
94 }
95 }
96
97
98}
99
100};