➣ Reading Time: 15 minutes

題目出處

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

 ⭐Python leetcode 相關文章整理⭐:  
⭐Leetcode 解題紀錄⭐:難度Tag
⭐面試最經典 Top 75 題⭐:
1.【Leetcode】python - [1] Two Sum 兩數之和 個人手繪解法筆記 (只講解法重點, 內含範例程式碼)#Easy#Array #HashTable
3.【Leetcode】python - [3] Longest Substring Without Repeating Characters 個人手繪解法筆記 (只講解法重點, 內含範例程式碼) #Medium#HashTable #TwoPointers #String #SlidingWindow
5.【Leetcode】python - [5] Longest Palindromic Substring 個人手繪解法筆記 (只講解法重點, 內含範例程式碼) #Medium#String #DP
11.【Leetcode】python - [11] Container With Most Water 個人手繪解法筆記 (只講解法重點, 內含範例程式碼) #Medium#Array #TwoPointers
15.【Leetcode】python - [15] 3Sum 三數之和 個人手繪解法筆記 (只講解法重點, 內含範例程式碼) #Medium#Array #TwoPointers
48.【Leetcode】python - [48] Rotate Image 旋轉矩陣 個人手繪解法筆記與解題思考建議 (只講解法重點, 內含範例程式碼)#Medium (但我覺得很難)#Array
104.【Leetcode】python - [104] Maximum Depth of Binary Tree 個人手繪解法筆記 (只講解法重點, 內含範例程式碼) #Easy#Tree #DFS #Recursion
⭐Leetcode 小技巧⭐:
1.【Python】python 測試程式 – 利用 doctest 測試 python testcase 的優雅寫法,適用於 leetcode (doctest in function,搭配 function 的用法)
2.【Leetcode】python – 利用 doctest 測試 leetcode python testcase 的優雅寫法 (doctest in class,搭配 class 的用法)