題目出處

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