?LeetCode刷題實戰(zhàn)48：旋轉(zhuǎn)圖像
算法的重要性，我就不多說了吧，想去大廠，就必須要經(jīng)過基礎(chǔ)知識和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個公眾號后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選 ！
今天和大家聊的問題叫做?旋轉(zhuǎn)圖像，我們先來看題面：
https://leetcode-cn.com/problems/rotate-image/
You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).
You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.
題意
樣例
示例 1:
給定 matrix =
[
??[1,2,3],
??[4,5,6],
??[7,8,9]
],
原地旋轉(zhuǎn)輸入矩陣，使其變?yōu)?
[
??[7,4,1],
??[8,5,2],
??[9,6,3]
]
示例 2:
給定 matrix =
[
??[ 5, 1, 9,11],
??[?2, 4, 8,10],
??[13, 3, 6, 7],
??[15,14,12,16]
],
原地旋轉(zhuǎn)輸入矩陣，使其變?yōu)?
[
??[15,13, 2, 5],
??[14, 3, 4, 1],
??[12, 6, 8, 9],
??[16, 7,10,11]
]
我們來看兩個動態(tài)圖：
題解
https://www.cnblogs.com/techflow/p/12687271.html
這個動圖一看就明白了，也就是說我們需要將一個二維矩陣順時針旋轉(zhuǎn)90度。這個題意我們都很好理解，但是題目當(dāng)中還有一個限制條件：我們不能額外申請其他的數(shù)組來輔助，也就是對我們的空間利用進(jìn)行了限制。
如果沒有這個條件限制其實很容易，我們只需要算出每一個坐標(biāo)旋轉(zhuǎn)之后的位置，我們重新創(chuàng)建一個數(shù)組然后依次填充就行了。
我們忽略矩陣當(dāng)中具體的數(shù)據(jù)，而來看看矩陣旋轉(zhuǎn)前后的坐標(biāo)變化。這是矩陣旋轉(zhuǎn)之前的坐標(biāo)：
旋轉(zhuǎn)之后，坐標(biāo)變成了：
我們對照上面兩張圖觀察一下，可以看出對于坐標(biāo)(i, j)來說，它旋轉(zhuǎn)90度之后得到的結(jié)果應(yīng)該是(j, n-1-i)。這里的n是行數(shù)。
我們有了這個式子之后，我們可以繼續(xù)推廣。我們發(fā)現(xiàn)(i, j)位置的點旋轉(zhuǎn)之后到了(j, n-1-i)。而(j, n-1-i)位置的點旋轉(zhuǎn)之后到了(n-1-i, n-1-j)，同理(n-1-i, n-1-j)旋轉(zhuǎn)之后到了(n-1-j, i)，最后我們發(fā)現(xiàn)(n-1-j, i)旋轉(zhuǎn)之后回到了(i, j)。
也就是說對于一次旋轉(zhuǎn)來說，(i, j), (j,n-1-i), (n-1-i, n-1-j), (n-1-j, i)這四個位置的元素互相交換了位置，并沒有影響到其他位置。其實這個也是很容易想明白的，因為題目給定的是一個方陣。
我們看下下圖就理解了：
也就是說我們只需要遍歷矩陣四分之一的部分，然后通過坐標(biāo)拿到互相交換的4個位置，然后交換它們的元素即可。
代碼
代碼真的很簡單，只有幾行：
class?Solution:
????def?rotate(self,?matrix:?List[List[int]])?->?None:
????????"""
????????Do?not?return?anything,?modify?matrix?in-place?instead.
????????"""
????????n?=?len(matrix)
????????
????????#?注意一下范圍和下標(biāo)即可
????????for?i?in?range(n//2):
????????????for?j?in?range(i,?n-1-i):
????????????????matrix[i][j],?matrix[j][n-1-i],?matrix[n-1-i][n-1-j],?matrix[n-1-j][i]?=?\
????????????????matrix[n-1-j][i],?matrix[i][j],?matrix[j][n-1-i],?matrix[n-1-i][n-1-j]上期推文：