目前做批發(fā)比較好的b2b網(wǎng)站百度免費(fèi)發(fā)布信息
LeetCode:48. 旋轉(zhuǎn)圖像
受到力扣hot100:54. 螺旋矩陣的啟發(fā),我們可以對旋轉(zhuǎn)圖像按層旋轉(zhuǎn),我們只需要記錄四個(gè)頂點(diǎn),并且本題是一個(gè)方陣,四個(gè)頂點(diǎn)就能完成圖像的旋轉(zhuǎn)操作。
1、逐層旋轉(zhuǎn)
注意到,一層的四個(gè)頂點(diǎn)存在一定的位置關(guān)系,我們只需要記錄四個(gè)值:
top_row
、bottom_row
、left_col
、right_col
,則上右下左四個(gè)頂點(diǎn)分別為:
(top_row,left_col)、(top_row,right_col)、(bottom_row,right_col)、(bottom_row,left_col)
當(dāng)我們需要更新層時(shí),注意矩陣的下標(biāo),只需進(jìn)行如下操作:
top_row++
bottom_row--
left_col++
right_col--
這樣我們就找到了一層的四個(gè)頂點(diǎn),以及更新層的操作。
現(xiàn)在我們只需要逐層更新即可。
時(shí)間復(fù)雜度: O ( n 2 ) O(n^2) O(n2)
空間復(fù)雜度: O ( 1 ) O(1) O(1)
class Solution {
public:void rotate(vector<vector<int>>& matrix) {int top_row = 0, left_col = 0;int bottom_row = matrix.size() - 1, right_col = matrix.size() - 1;//由于size() > 1,所以可以這樣做while(top_row < bottom_row){//方陣,結(jié)束條件int step = right_col - left_col;for(int i = 0; i < step; ++ i){int temp;//上換到右temp = matrix[top_row + i][right_col];matrix[top_row + i][right_col] = matrix[top_row][left_col + i];//右換到下int temp2 = temp;temp = matrix[bottom_row][right_col - i];matrix[bottom_row][right_col - i] = temp2;//下?lián)Q到左temp2 = temp;temp = matrix[bottom_row - i][left_col];matrix[bottom_row - i][left_col] = temp2;//左換到上matrix[top_row][left_col + i] = temp;}//更新層top_row++;bottom_row--;left_col++;right_col--;}return ;}
};
- 我們需要注意一個(gè)問題,判斷結(jié)束條件時(shí),由于方陣行數(shù)是
n
可以是偶數(shù)也可以是奇數(shù),奇數(shù)時(shí),上行和下行相等則結(jié)束。但如果是偶數(shù)時(shí),他倆會交叉,因此是下行大于上行時(shí)結(jié)束!- 為了在編程時(shí)忽略奇偶數(shù)的這個(gè)問題,我們可以編程時(shí)將判斷條件更寬泛
- 如果
top_row > bottom_row
也不滿足條件,那不要寫top_row == bottom_row
,而是將兩者結(jié)合起來寫,這樣可以避免自己的遺漏。
為了節(jié)省臨時(shí)變量,我們也可以按左下轉(zhuǎn)到左上,右下轉(zhuǎn)到左下,右上轉(zhuǎn)到右下,左上轉(zhuǎn)到右上的順序旋轉(zhuǎn),這樣只需要存儲左上的值即可。
class Solution {
public:void rotate(vector<vector<int>>& matrix) {int top_row = 0, left_col = 0;int bottom_row = matrix.size() - 1, right_col = matrix.size() - 1;//由于size() > 1,所以可以這樣做while(top_row < bottom_row){//方陣,結(jié)束條件int step = right_col - left_col;for(int i = 0; i < step; ++ i){int temp = matrix[top_row][left_col + i];matrix[top_row][left_col + i] = matrix[bottom_row - i][left_col];左換到上matrix[bottom_row - i][left_col] = matrix[bottom_row][right_col - i];//下?lián)Q到左matrix[bottom_row][right_col - i] = matrix[top_row + i][right_col];//右換到下matrix[top_row + i][right_col] = temp;//上換到右}//更新層top_row++;bottom_row--;left_col++;right_col--;}return ;}
};
和官解的方法二類似。
2、兩次翻轉(zhuǎn)等于旋轉(zhuǎn)
class Solution {
public:void rotate(vector<vector<int>>& matrix) {int n = matrix.size();// 水平翻轉(zhuǎn)for (int i = 0; i < n / 2; ++i) {for (int j = 0; j < n; ++j) {swap(matrix[i][j], matrix[n - i - 1][j]);}}// 主對角線翻轉(zhuǎn)for (int i = 0; i < n; ++i) {for (int j = 0; j < i; ++j) {swap(matrix[i][j], matrix[j][i]);}}}
};