內容目錄
題目出處
https://leetcode.com/problems/rotate-image/
難度
Medium (但我覺得其實很難想XDD)
題目分類
Array
特別注意題目說的「inplace」
特別注意題目說的「inplace」，基本上就是希望不要用到額外儲存空間，
可以當作不能「製造出新的矩陣」，只能單純的「矩陣內位置互換」
- 換成程式碼的意思就是：「一個個index去換值」，不要對整個矩陣操作
先講點題外話(喂
這題基本上就是真正實作「圖片的旋轉」了！
(不能靠 OpenCV 或 Numpy 幫助的那種XDD)
學起來這題後，我有體會到 OpenCV 中旋轉圖片的函數實作有多偉大與困難XDD
真心更尊敬 OpenCV 的開發者惹 (人家本來就超強XDD)
個人推薦可以先思考轉180度，再來考慮90度
我是認真的XD，
過來人的經驗，180度要先解出來，90度才是下一個階段的問題。
直接就硬爆 90度 大魔王連怎麼死的都不知道
來先解 180度 吧，直接看圖! (觀察只有兩個東西在互換)
重要觀念：i, j 是「變化量 (delta)」，不要用「座標」的概念下去想。
寫 for 迴圈的時候，就會知道這問題出在哪了! (可以見文章最下面錯誤的部分)
- 示意圖：(我們可以發現，這題只有兩個東西在互換)
觀察 x軸, y軸的變化
180度 比較簡單，「x軸」上的變化只會影響在「x軸」，
等等 90度 就沒有這麼簡單了!!!
- 整理一下變換公式：
先有這樣的觀念，我們再來推 90度的答案!
個人手繪解法筆記 (解法重點) – 方法一 (比較正常思考一點XDD)
再強調一次重要觀念：i, j 是「變化量 (delta)」，不要用「座標」的概念下去想。
寫 for 迴圈的時候，就會知道這問題出在哪了! (可以見文章最下面錯誤的部分)
每次的互換，只同時牽扯到四個東西
- 示意圖：(看得出來每次互換只扯到四個東西吧?)
我們將每個座標對應的關係，都「仔細地」寫出來!
- 示意圖：(仔細觀察 i,j 變化量出現的位置，牽扯到 x軸, y軸 值上面的移動。)
列成循環算式，並更正方向錯誤的座標。
如果一個「i,j 變化量」的方向錯誤，
我們可以視為「加上(N-1)後，減去變化量的值」，
(可以想想，N-1是最大邊界，不能再更多了，只能再扣掉變化量。)
- 示意圖：(整理一下就能夠得到我們最終的循環公式囉!)
另外一個大魔王? 什麼時候才是終止條件? (你以為能無腦全部掃過嗎XDD，那就是轉四次回原狀惹)
為什麼不能夠無腦全部掃過?
這就是另外一個大魔王惹，真的不能無腦全部掃過
因為全部掃過 = 轉四次 = 變回原狀，根本沒解到題目XDDD
那要怎麼找到只需要掃一次的東西呢?
什麼時候才是終止條件? (其實也沒那麼難啦XDD)
因為是四角轉換，我們從最簡單的 2*2 來看，是不是就很簡單了呢?
也就是說，放大來看後，我們一樣只需要去抓一個角即可。
- 示意圖：(四角互換)
先來處理比較容易的 「N = 偶數」邊
偶數沒什麼問題，就是稍微算一下範圍確認 for 要到多少即可。
記得 range 的範圍，與實際範圍的不同。
注意: +1, -1 對答案都會有影響XDD 請小心。
再來處理比較難搞的 「N = 奇數」邊
奇數就比較麻煩一點點，我們先上一下色，
我們發現 y軸上 的分析，需要比 x軸 少一格，
不然就會有重複運算的問題。
稍微注意這點也就沒什麼好怕的了。
我們奇偶數不分開處理，再更方便一點
我們仔細分析我們剛剛得到的範圍，(當然你要 N = 奇偶數 分開處理一定可以的XD)
幾乎都出現了 in range (N/2)，只有在奇數的時候多出現一個 in range ((N/2)+1)
那這個「1」可以怎麼來呢? 就是只有「奇數」才會來嘛!
所以 「N%2 = 1」 (就會得到我們的奇數囉!!)
我們將範圍公式都改寫成：「in range (N/2 + N%2)」，這樣就非常漂亮了!
注意：只有「x軸」 需要這個範圍
不要太開心連「y軸」一起用下去了XDD，偶數就會錯惹!!!
(現在你知道這題 +1, -1 的問題真的有夠煩的吧!)
個人範例程式碼
真的別小看這只有八行的程式碼…，實際上寫出來花的時間根本遠遠超過這八行
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
N = len(matrix) # one side
for i in range(N//2 + N%2):
for j in range(N//2):
tmp = matrix[i][j] # save temporarily
matrix[i][j] = matrix[-j+(N-1)][i] # 1
matrix[-j+(N-1)][i] = matrix[-i+(N-1)][-j+(N-1)] # 2
matrix[-i+(N-1)][-j+(N-1)] = matrix[j][-i+(N-1)] # 3
matrix[j][-i+(N-1)] = tmp # 4
個人手繪解法筆記 (解法重點) – 方法二 (炫炮解法)
直接看圖吧! 這題我們利用 「轉90度 = 轉置 + 左右翻轉」的概念
(嗯… 有夠快的…，我們剛剛在幹嘛)
仔細分析題目的能力還是很重要的!!! (不一定是解題，工作上更是常需要!)
- 示意圖: (轉90度 = 轉置 + 左右翻轉)
轉置細節：也是不能無聊全部掃過
即使是轉置矩陣，我們也沒辦法無腦掃過XDD，
我們只能掃「一個對角線內的全部值」，
我們可以運用「j = i + 1」來達到我們想要的效果!
左右反轉細節：思考座標點，跟想像的不太一樣
這邊我踩了一個雷，就是我想像中的座標概念，
與實際上的座標概念是不同的。
主要原因是：list[list] 會先讀取到第一個是「該行」矩陣，也就是「y軸」
請務必想清楚這一點，不然就會錯惹QQ (好複雜XDDD)
個人範例程式碼
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
N = len(matrix) # one side
# transpose
for i in range(N):
for j in range(i+1, N):
tmp = matrix[i][j]
matrix[i][j] = matrix[j][i]
matrix[j][i] = tmp
# print(f"{matrix}") #dubug
# right and left reverse
for i in range(N):
for j in range(N//2):
tmp = matrix[i][j]
matrix[i][j] = matrix[i][-j+(N-1)]
matrix[i][-j+(N-1)] = tmp
觀念錯誤筆記
觀念錯誤的部分：i, j 是「變化量 (delta)」，不要用「座標」的概念下去想。
寫 for 迴圈的時候，就會知道這問題出在哪了!
來先解 180度 吧，直接看圖!
從圖中我們大概知道，「x軸上的移動，會影響的只會在x軸」
(也許聰明的你已經想到了，90度的影響會跑到y軸去!!!會更複雜!)
所以我們由上圖整理一下我們的x,y軸變化
我們將數值整理一下，
可以發現x軸上 i + offset(變化量)的時候，
對應的 180度 x軸上後的變化量 為 i+(N-1)-offset(變化量)
也就是說
i + offset -> i+(N-1)-offset
同理可以推得
j + offset -> j+(N-1)-offset
先有這樣的觀念，我們再來推 90度的答案!
每次的互換，只同時牽扯到四個東西
- 示意圖：(看得出來每次互換只扯到四個東西吧?)
將它換成 offset
- 示意圖：(換成 k = offset 之後的圖)
慢慢來，我們把他慢慢的都寫出來
- 示意圖：(一個個把算式寫出來就對了! 就只有這四行關鍵算式!!!)
Reference
https://ithelp.ithome.com.tw/articles/10237207
https://leetcode.com/problems/rotate-image/solution/
https://leetcode.com/problems/rotate-image/discuss/18888/1-line-in-Python
[…] […]