969
CareerCup之1.6 Rotate Image
【題目】
原文：
1.6 Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. Can you do this in place?
譯文：
一張圖像表示成NxN的矩陣，圖像中每個像素是4個字節，寫一個函數把圖像旋轉90度。 你能原地進行操作嗎？(即不開辟額外的存儲空間)
【分析】
【代碼一】
/*********************************
* 日期：2014-05-14
* 作者：SJF0115
* 題目: Rotate Image
* 來源：CareerCup
**********************************/
#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
using namespace std;
//旋轉圖片
void RotateImage(vector<vector<int> > &matrix){
int i,j,temp;
int N = matrix.size();
// 沿著副對角線反轉
for(i = 0; i < N;i++){
for(j = 0;j < N - i;j++){
temp = matrix[i][j];
matrix[i][j] = matrix[N - 1 - j][N - 1 - i];
matrix[N - 1 - j][N - 1 - i] = temp;
}
}
// 沿著水平中線反轉
for(i = 0; i < N / 2;i++){
for (j = 0; j < N;j++){
temp = matrix[i][j];
matrix[i][j] = matrix[N - 1 - i][j];
matrix[N - 1 - i][j] = temp;
}
}
}
int main(){
vector<int> row1 = {1,2,3};
vector<int> row2 = {4,5,6};
vector<int> row3 = {7,8,9};
vector<vector<int>> matrix;
matrix.push_back(row1);
matrix.push_back(row2);
matrix.push_back(row3);
RotateImage(matrix);
for(int i = 0;i < 3;i++){
for(int j = 0;j < 3;j++){
cout<<matrix[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
【代碼二】
/*********************************
* 日期：2014-05-14
* 作者：SJF0115
* 題目: Rotate Image
* 來源：CareerCup
**********************************/
#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
using namespace std;
//旋轉圖片
void RotateImage(vector<vector<int> > &matrix){
int layer,i,top;
int n = matrix.size();
//一層一層旋轉
for(layer = 0;layer < n/2;layer++){
//第layer層第一個元素
int first = layer;
//第layer層最後一個個元素
int last = n -1 - layer;
for(i = first;i < last;i++){
//偏移量
int offset = i - first;
top = matrix[first][i];
//left-top
matrix[first][i] = matrix[last-offset][first];
//bottom-left
matrix[last-offset][first] = matrix[last][last-offset];
//right-bottom
matrix[last][last-offset] = matrix[i][last];
//top-right
matrix[i][last] = top;
}//for
}//for
}
int main(){
vector<int> row1 = {1,2,3};
vector<int> row2 = {4,5,6};
vector<int> row3 = {7,8,9};
vector<vector<int>> matrix;
matrix.push_back(row1);
matrix.push_back(row2);
matrix.push_back(row3);
RotateImage(matrix);
for(int i = 0;i < 3;i++){
for(int j = 0;j < 3;j++){
cout<<matrix[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
最後更新：2017-04-03 12:56:39