給你一個(NxN)二維陣列表示的圖，請你將它向右旋轉90度。
請不要宣告另一個二維陣列來做這件事!你要in-place達成此事，也就是在原本的陣列修改這個圖
Given input matrix = [ [ 5, 1, 9,11], [ 2, 4, 8,10], [13, 3, 6, 7], [15,14,12,16] ], rotate the input matrix in-place such that it becomes: [ [15,13, 2, 5], [14, 3, 4, 1], [12, 6, 8, 9], [16, 7,10,11] ]https://leetcode.com/problems/rotate-image/description/
[思路]
旋轉就是把四角形的四個角交換
上例中
5,11,16,15是一組四角形
1,10,12,2是一組四角形
9,7,14,2是一組四角形
4,8,6,3是一組四角形
分別做完這四組的四角交換，就完成了整張圖的旋轉。
"過程中誰會被覆蓋掉?" 這影響你要宣告多大的變數暫存被蓋掉的人
"要暫存多久?" 這影響你用來暫存的memory，甚麼時候可以被釋放
這題的in-place並不難，假設四個角分別是a,b,c,d旋轉後變成d,a,b,c
那就是
int tmp=a;
a=d;
d=c;
c=b;
b=tmp;//原本要寫b=a，但a早已經被覆蓋掉了，幸好我們有把a暫存在tmp裡，此時拿出來用
然後回答上面的問題
"過程中誰會被覆蓋掉?" a會被覆蓋掉，要宣告一個int tmp暫存它
"要暫存多久?" 處理一個四角形的時間，處理完後tmp就可以釋放掉
因此我們需要的額外memory只有一個int，而不是一個NxN陣列，這有達到in-place的要求。
void rotate(vector<vector<int>>& matrix)
{
int n = matrix.size();
for(int y=0,x=0; y<n/2 ;y++,x++)
{
int len=n-y*2;
for(int k=0;k<len-1;k++)
{
int a = matrix[y][x+k];
matrix[y][x+k] = matrix[y+len-1-k][x];
matrix[y+len-1-k][x] = matrix[y+len-1][x+len-1-k];
matrix[y+len-1][x+len-1-k] = matrix[y+k][x+len-1];
matrix[y+k][x+len-1] = a;
}
}
}
