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?
A:
关键点, 也是难点,在于,任给一个topLeft的index, 我们怎么计算出它的其余3个对应点。
一定要画图,示意。 自己刚开始的想象是错误的。
两种方案可以选择:
1. 利用图片矩形的特性,将其剥洋葱一样,一层一层处理,每一层逐个将四条边顺时针交换; (例如上面的实现)
---------------------------第二遍 ---------第二个实现-----------------class Solution { public: void rotate(vector<vector<int>>& matrix) { int n = matrix.size(); // peel off the onion layer by layer for(int i =0;i<n/2;++i) { for(int j =i; j<n-1-i;++j) { int tmp = matrix[i][j]; matrix[i][j] = matrix[n-1-j][i]; matrix[n-1-j][i] = matrix[n-1-i][n-1-j]; matrix[n-1-i][n-1-j] = matrix[j][n-1-i]; matrix[j][n-1-i] = tmp; } } } };
先将图片上下翻转矩阵,所有元素再在沿着主对角线交换位置即可。(当然,也可以先沿着主对角线交换,再左右翻转矩阵)
设(x,y)关于直线y=x的对称点坐标为(x1y1)
x+x1=y+y1
(y-y1)/(x-x1)=-1
算出 关于y=x的对称点是(y,x)
同理 关于y=-x的对称点是(-y,-x)
class Solution { public: void rotate(vector<vector<int>>& matrix) { int n = matrix.size(); // flip along the midlle row for(int i =0;i<n/2;++i) { for(int j=0;j<n;++j) { int tmp = matrix[i][j]; matrix[i][j] = matrix[n-1-i][j]; matrix[n-1-i][j] = tmp; } } // flip along the road for(int i =0;i<n;++i) { for(int j=0;j<i;++j) { int tmp = matrix[i][j]; matrix[i][j] = matrix[j][i]; matrix[j][i] = tmp; } } } };
这里,犯得错误是: 当对于row = n/2 来flip的时候,把对应的行数算错了,应该是n-1-i的,而不是n/2+i
另一遍的时候,没弄明白,去搞成对于\ 和/这两个对角线翻去了。
Mistakes:
Learned:
No comments:
Post a Comment