題目出處

48. Rotate Image

難度

Medium (但我覺得其實很難想XDD)

題目分類

Array

特別注意題目說的「inplace」

特別注意題目說的「inplace」，基本上就是希望不要用到額外儲存空間，
可以當作不能「製造出新的矩陣」，只能單純的「矩陣內位置互換」

• 換成程式碼的意思就是：「一個個index去換值」，不要對整個矩陣操作

先講點題外話(喂

這題基本上就是真正實作「圖片的旋轉」了！
(不能靠 OpenCV 或 Numpy 幫助的那種XDD)

學起來這題後，我有體會到 OpenCV 中旋轉圖片的函數實作有多偉大與困難XDD
真心更尊敬 OpenCV 的開發者惹 (人家本來就超強XDD)

個人範例程式碼 – 2022/5/29 二刷

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        m, n = len(matrix), len(matrix[0])

        if m != n:
            return 

        # transpose
        for i in range(m):
            for j in range(i+1, n):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j] 

        # reverse
        for i in range(m):
            matrix[i].reverse()

算法說明

利用「旋轉 90 度 = 先轉置，再單行反轉的概念 」，我們可以推得

分析範圍，我們只能做一個三角，尋找三角的方式

我們可以透過 i+1 來控制三角形的範圍 (也就是 m 的範圍)。

input handling

題目預設是沒有，這裡我多處理了一個 m != n 的特殊情況 (題目也不預期會發生)

Boundary conditions

用兩層 for loop 來控制範圍

個人範例程式碼 – 2021/4/3 一刷 (方法一)

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

真的別小看這只有八行的程式碼…，實際上寫出來花的時間根本遠遠超過這八行

解法說明

個人推薦可以先思考轉180度，再來考慮90度

我是認真的XD，
過來人的經驗，180度要先解出來，90度才是下一個階段的問題。

直接就硬爆 90度 大魔王連怎麼死的都不知道

來先解 180度 吧，直接看圖! (觀察只有兩個東西在互換)

重要觀念：i, j 是「變化量 (delta)」，不要用「座標」的概念下去想。
寫 for 迴圈的時候，就會知道這問題出在哪了! (可以見文章最下面錯誤的部分)

• 示意圖：(我們可以發現，這題只有兩個東西在互換)

觀察 x軸, y軸的變化

180度 比較簡單，「x軸」上的變化只會影響在「x軸」，
等等 90度 就沒有這麼簡單了!!!

• 整理一下變換公式：

先有這樣的觀念，我們再來推 90度的答案!

個人手繪解法筆記 – (方法一比較正常思考一點)

再強調一次重要觀念：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 的問題真的有夠煩的吧!)

個人範例程式碼 – 2021/4/3 一刷 (方法二，炫炮解法)

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

解法說明

直接看圖吧! 這題我們利用 「轉90度 = 轉置 + 左右翻轉」的概念
(嗯… 有夠快的…，我們剛剛在幹嘛)

仔細分析題目的能力還是很重要的!!! (不一定是解題，工作上更是常需要!)

• 示意圖: (轉90度 = 轉置 + 左右翻轉)

轉置細節：也是不能無聊全部掃過

即使是轉置矩陣，我們也沒辦法無腦掃過XDD，
我們只能掃「一個對角線內的全部值」，
我們可以運用「j = i + 1」來達到我們想要的效果!

左右反轉細節：思考座標點，跟想像的不太一樣

這邊我踩了一個雷，就是我想像中的座標概念，
與實際上的座標概念是不同的。
主要原因是：list[list] 會先讀取到第一個是「該行」矩陣，也就是「y軸」
請務必想清楚這一點，不然就會錯惹QQ (好複雜XDDD)

觀念錯誤筆記

觀念錯誤的部分：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

• 旋转图像 · Rotate Image
• 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

⭐ Leetcode 解題紀錄 ⭐		題型	資料結構	Python Solution	C++ Solution	Note
⭐BFS 相關題型 ⭐
104	Maximum Depth of Binary Tree	BFS (分層)		Python
94	Binary Tree Inorder Traversal	BFS (分層)	Tree	Python		內含 處理 Tree 樹問題的重點
102	Binary Tree Level Order Traversal	BFS (分層)	Tree	Python
103	Binary Tree Zigzag Level Order Traversal	BFS (分層)	Tree	Python
107	Binary Tree Level Order Traversal II	BFS (分層)	Tree	Python
133	Clone Graph	BFS (分層)	Graph	Python		Graph 的基本操作 #重要題型
127	Word Ladder	BFS (分層), DFS	Graph	Python
[Lint] 127	Topological Sorting	BFS (拓撲)		Python		內有 indegree, outdegree 介紹 #重要題型
207	Course Schedule	BFS (拓樸)	Graph	Python
210	Course Schedule II	BFS (拓樸)	Graph	Python
[Lint] 892	Alien Dictionary	BFS (拓樸)	Graph	Python
[Lint] 431	Connected Component in Undirected Graph	BFS (連通塊)	Graph	Python		內含 BFS 模板 #重要題型
1091	Shortest Path in Binary Matrix	BFS (最短路徑)	Matrix	Python
⭐ Binary Serach 相關題型 ⭐
33	Search in Rotated Sorted Array	Binary Serach	Array	Python		#重要題型
34	Find First and Last Position of Element in Sorted Array	Binary Serach		Python
50	Pow(x, n)	Binary Serach		Python
153	Find Minimum in Rotated Sorted Array	Binary Serach	Array	Python
162	Find Peak Element	Binary Serach		Python
278	First Bad Version	Binary Serach		Python
658	Find K Closest Elements	Binary Serach		Python
704	Binary Search	Binary Serach		Python
852	Peak Index in a Mountain Array	Binary Serach		Python
[Lint] 14	First Position of Target	Binary Serach		Python
[Lint] 140	Fast Power	Binary Serach		Python
[Lint] 447	Search in a Big Sorted Array	Binary Serach	Array	Python
[Lint] 458	Last Position of Target	Binary Serach		Python
191	Number of 1 Bits	Bit Manipulation		Python
⭐ Data Stream 相關題型 ⭐
[Lint] 642	Moving Average from Data Stream	Data Stream	Queue	Python
⭐ Design 相關題型 ⭐
155	Min Stack	Design		Python
[Lint] 659	Encode and Decode Strings	Design		Python
232	Implement Queue using Stacks	Design	Queue, Stack	Python
⭐ DFS 相關題型 ⭐
98	Validate Binary Search Tree	DFS		Python
2265	Count Nodes Equal to Average of Subtree	DFS		Python		292nd Weekly Contest
2261	K Divisible Elements Subarrays	DFS		Python		內含 python substring 常見作法 / 291st LeetCode Weekly Contest
22	Generate Parentheses	DFS		Python
79	Word Search	DFS	Matrix	Python
126	Word Ladder II	DFS		Python
212	Word Search II	DFS	Tree	Python
290	Word Pattern	DFS		Python
[Lint] 829	Word Pattern II	DFS		Python
31	Next Permutation	DFS (排列)		Python
46	Permutations	DFS (排列)		Python		#重要題型
47	Permutations II	DFS (排列)		Python		#重要題型
51	N-Queens	DFS (排列)		Python
52	N-Queens II	DFS (排列)		Python
[Lint] 862	Next Closest Time	DFS (排列)		Python		內有 set 判斷是否 subset 的用法
10	Regular Expression Matching	DFS (組合)		Python
77	Combinations	DFS (組合)		Python		#重要題型
39	Combination Sum	DFS (組合)		Python
40	Combination Sum II	DFS (組合)		Python
216	Combination Sum III	DFS (組合)		Python
377	Combination Sum IV	DFS (組合)		Python
44	Wildcard Matching	DFS (組合)		Python
78	Subsets	DFS (組合)		Python		#重要題型
90	Subsets II	DFS (組合)		Python		#重要題型
131	Palindrome Partitioning	DFS (組合)		Python
139	Word Break	DFS (組合)		Python
140	Word Break II	DFS (組合)		Python
[Lint] 90	k Sum II	DFS (組合)		Python
[Lint] 680	Split String	DFS (組合)		Python
173	Binary Search Tree Iterator	DFS (BST)	BST	Python		#重要題型
230	Kth Smallest Element in a BST	DFS (BST)	BST	Python
[Lint] 448	Inorder Successor in BST	DFS (BST)	BST	Python
[Lint] 900	Closest Binary Search Tree Value	DFS (BST)	BST	Python
[Lint] 901	Closest Binary Search Tree Value II	DFS (BST)	BST	Python		#綜合難題
208	Implement Trie (Prefix Tree)	DFS (Graph)	Tree	Python
17	Letter Combinations of a Phone Number	DFS (Graph)	Graph	Python
332	Reconstruct Itinerary	DFS (Graph)	Graph	Python		#重要題型
110	Balanced Binary Tree	DFS (Tree)	Tree	Python
226	Invert Binary Tree	DFS (Tree)	Tree	Python
572	Subtree of Another Tree	DFS (Tree)	Tree	Python
105	Construct Binary Tree from Preorder and Inorder Traversal	DFS (Tree)	Tree	Python
112	Path Sum	DFS (Tree)		Python
113	Path Sum II	DFS (Tree)	Tree	Python
235	Lowest Common Ancestor of a Binary Search Tree	DFS (Tree)	Tree	Python
236	Lowest Common Ancestor of a Binary Tree	DFS (Tree)	Tree	Python		#重要題型
257	Binary Tree Paths	DFS (Tree)	Tree	Python
[Lint] 474	Lowest Common Ancestor II	DFS (Tree)	Tree	Python
[Lint] 578	Lowest Common Ancestor III	DFS (Tree)	Tree	Python
[Lint] 596	Minimum Subtree	DFS (Tree)	Tree	Python
543	Diameter of Binary Tree	DFS (Tree)		Python
144	Binary Tree Preorder Traversal	DFS (Tree)	Tree	Python		內含 處理 Tree 樹問題的重點
145	Binary Tree Postorder Traversal	DFS (Tree)	Tree	Python
114	Flatten Binary Tree to Linked List	DFS (Tree)	Tree	Python
⭐ Dynamic Programming 相關題型 ⭐
338	Counting Bits	DP		Python
309	Best Time to Buy and Sell Stock with Cooldown	DP		Python
2266	Count Number of Texts	DP		Python		292nd Weekly Contest
2262	Total Appeal of A String	DP		Python		291st Weekly Contest
91	Decode Ways	DP		Python	C++
70	Climbing Stairs	DP		Python	C++
221	Maximal Square	DP		Python
53	Maximum Subarray	DP (一維)	Array	Python	C++	內含 C++ vector max 用法整理
91	Decode Ways	DP (一維)		Python
55	Jump Game	DP (一維)		Python		#重要題型
45	Jump Game II	DP (一維)		Python		#重要題型
198	House Robber	DP (一維)		Python
213	House Robber II	DP (一維)		Python
509	Fibonacci Number	DP (一維)		Python
122	Best Time to Buy and Sell Stock II	DP (一維)		Python
300	Longest Increasing Subsequence	DP (一維接龍, LIS)		Python		#重要題型
62	Unique Paths	DP (二維)		Python	C++
63	Unique Paths II	DP (二維)		Python	C++
152	Maximum Product Subarray	DP (二維)		Python		#重要題型
118	Pascal’s Triangle	DP (二維)		Python		內含 python sum of two list (list add 相加方法整理)
322	Coin Change	DP (背包問題)		Python		內含 DP 背包問題模板 #重要題型
518	Coin Change 2	DP (背包問題)		Python		#重要題型
[Lint] 92	Backpack	DP (背包問題)		Python
[Lint] 125	Backpack II	DP (背包問題)		Python
[Lint] 440	Backpack III	DP (背包問題)		Python
[Lint] 562	Backpack IV	DP (背包問題)		Python
[Lint] 563	Backpack V	DP (背包問題)		Python
[Lint] 798	Backpack VII	DP (背包問題)		Python
[Lint] 799	Backpack VIII	DP (背包問題)		Python
[Lint] 800	Backpack IX	DP (背包問題)		Python
[Lint] 801	Backpack X	DP (背包問題)		Python
1143	Longest Common Subsequence	DP (LCS)		Python
494	Target Sum	DP (Memoization)		Python
2267	Check if There Is a Valid Parentheses String Path	DP (Memoization)		Python		內含：Memoization 記憶化搜索筆記 / 292nd Weekly Contest
⭐ Hash 相關題型 ⭐
13	Roman to Integer	Hash		Python
73	Set Matrix Zeroes	Hash		Python	C++	內含 python while-else 用法說明
692	Top K Frequent Words	Hash		Python		內含 python 自定義排序 key function 的使用方法
846	Hand of Straights	Hash		Python
347	Top K Frequent Elements	Hash		Python
205	Isomorphic Strings	Hash		Python
268	Missing Number	Hash		Python
242	Valid Anagram	Hash		Python
763	Partition Labels	Hash	Interval	Python
383	Ransom Note	Hash		Python
387	First Unique Character in a String	Hash		Python
2186	Minimum Number of Steps to Make Two Strings Anagram II	Hash		Python		282nd Weekly Contest
[Lint] 793	Intersection of Arrays	Hash		Python
146	LRU Cache	Hash		Python
387	First Unique Character in a String	Hash		Python
[Lint] 920	Meeting Rooms	Hash	Interval	Python		#重要題型
[Lint] 920	Meeting Rooms	Hash	Interval	Python		#重要題型
[Lint] 919	Meeting Rooms II	Hash	Interval	Python		#重要題型
[Lint] 919	Meeting Rooms II	Hash	Interval	Python		#重要題型
349	Intersection of Two Arrays	Hash		Python
217	Contains Duplicate	Hash	Array	Python	C++	內含 C++ set, unordered_set 用法整理
137	Single Number II	Hash		Python
350	Intersection of Two Arrays II	Hash		Python
2248	Intersection of Multiple Arrays	Hash		Python		290th Weekly Contest
49	Group Anagrams	Hash (Anagrams)		Python
217	Contains Duplicate	Hash (Duplicate)		Python
128	Longest Consecutive Sequence	Hash (LCS)		Python
136	Single Number	Hash, Bit Manipulation		Python
⭐ Heap 相關題型 ⭐
264	Ugly Number II	Heap		Python
⭐ Stack 相關題型 ⭐
739	Daily Temperatures	Stack		Python
496	Next Greater Element I	Stack		Python
503	Next Greater Element II	Stack		Python
20	Valid Parentheses	Stack (Parentheses)		Python		內含用 python List 組出 Stack, Queue 的方法整理
⭐ Two pointers 相關題型 ⭐
11	Container With Most Water	Two pointers		Python
42	Trapping Rain Water	Two pointers		Python
74	Search a 2D Matrix	Two pointers	Matrix	Python
141	Linked List Cycle	Two pointers	Linked List	Python
142	Linked List Cycle II	Two pointers	Linked List	Python		內含 python while-else 用法介紹
283	Move Zeroes	Two pointers		Python
876	Middle of the Linked List	Two pointers		Python
2260	Minimum Consecutive Cards to Pick Up	Two pointers (快慢)		Python		291st Weekly Contest
21	Merge Two Sorted Lists	Two pointers (Merge)	Linked List	Python		內含 python Linked List 基本操作 (for 新手教學)
88	Merge Sorted Array	Two pointers (Merge)		Python	C++	內含 python while-else 用法說明
1	Two Sum	Two pointers (NSum)	Array	Python	C++	內有 Python list comprehesion / dict comprehesion 整理 / C++ map find 方法補充 (dict find)
15	3Sum	Two pointers (NSum)	Array	Python
16	3Sum Closest	Two pointers (NSum)		Python
167	Two Sum II – Input Array Is Sorted	Two pointers (NSum)		Python
[Lint] 382	Triangle Count	Two pointers (NSum)		Python
[Lint] 533	Two Sum – Closest to Target	Two pointers (NSum)		Python
[Lint] 587	Two Sum – Unique Pairs	Two pointers (NSum)		Python
5	Longest Palindromic Substring	Two pointers (Palindrome)		Python	C++	內含 C++ string.substr() 用法筆記
9	Palindrome Number	Two pointers (Palindrome)		Python
125	Valid Palindrome	Two pointers (Palindrome)	String	Python		內含 python isalpha(), isalnum() 的整理
680	Valid Palindrome II	Two pointers (Palindrome)		Python
409	Longest Palindrome	Two pointers (Palindrome)		Python
647	Palindromic Substrings	Two pointers (Palindrome)		Python
234	Palindrome Linked List	Two pointers (Palindrome)	Linked List	Python		內含 reverse LinkedList 方法
75	Sort Colors	Two pointers (partition)		Python		#重要題型
[Lint] 5	Kth Largest Element	Two pointers (partition)		Python		#重要題型
[Lint] 31	Partition Array	Two pointers (partition)		Python		#重要題型
[Lint] 143	Sort Colors II	Two pointers (partition)		Python		#重要題型
[Lint] 461	Kth Smallest Numbers in Unsorted Array	Two pointers (partition)		Python		#重要題型
3	Longest Substring Without Repeating Characters	Two pointers (Sliding Window)		Python
76	Minimum Window Substring	Two pointers (Sliding Window)		Python
239	Sliding Window Maximum	Two pointers (Sliding Window)		Python
⭐ 其他題型 / 待分類 ⭐
2	Add Two Numbers		Linked List	Python
7	Reverse Integer			Python
19	Remove Nth Node From End of List		Linked List	Python
36	Valid Sudoku			Python
48	Rotate Image		Matrix	Python
621	Task Scheduler			Python
202	Happy Number			Python
238	Product of Array Except Self			Python
222	Count Complete Tree Nodes		Tree	Python
674	Longest Continuous Increasing Subsequence			Python
435	Non-overlapping Intervals		Interval	Python
88	Merge Sorted Array			Python		內含 python while-else 用法說明
2264	Largest 3-Same-Digit Number in String			Python		292nd Weekly Contest
56	Merge Intervals		Interval	Python		內含：python sorted key 搭配 lambda 的用法範例
57	Insert Interval		Interval	Python
61	Rotate List		Linked List	Python
2259	Remove Digit From Number to Maximize Result			Python		291st Weekly Contest
53	Maximum Subarray			Python
54	Spiral Matrix			Python
228	Summary Ranges			Python
263	Ugly Number			Python
203	Remove Linked List Elements		Linked List	Python		內含 Linked List remove 操作 part 2 (for 新手教學)
206	Reverse Linked List		Linked List	Python		內含 Linked List reverse 反轉操作 part 3 (for 新手教學)
189	Rotate Array		Array	Python
2185	Counting Words With a Given Prefix		String	Python		282nd Weekly Contest
134	Gas Station			Python
121	Best Time to Buy and Sell Stock			Python
83	Remove Duplicates from Sorted List		Linked List	Python
566	Reshape the Matrix		Matrix	Python		內含 python array 初始化, index 操作與控制範例
2243	Calculate Digit Sum of a String			Python		289th Weekly Contest
2244	Minimum Rounds to Complete All Tasks			Python		289th Weekly Contest
2249	Count Lattice Points Inside a Circle			Python		290th Weekly Contest
⭐【喜歡我的文章嗎? 歡迎幫我按讚~ 讓基金會請創作者喝一杯咖啡! 】 如果喜歡我的文章，請幫我在下方【按五下Like】 (Google, Facebook 免註冊)，會由 「LikeCoin」 贊助作者鼓勵繼續創作，讀者們「只需幫忙按讚，完全不用出錢」哦!