Rotate Image

Q:
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: