分類

展開全部 | 收合全部

分類

展開全部 | 收合全部

【Leetcode】python – [48] Rotate Image 個人解法筆記 (updated: 2022/5/29)

題目出處

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

⭐ Leetcode 解題紀錄 ⭐題型資料結構Python SolutionC++ SolutionNote
⭐BFS 相關題型 ⭐
104Maximum Depth of Binary TreeBFS (分層)Python
94Binary Tree Inorder TraversalBFS (分層)TreePython 內含 處理 Tree 樹問題的重點
102Binary Tree Level Order TraversalBFS (分層)TreePython
103Binary Tree Zigzag Level Order TraversalBFS (分層)TreePython
107Binary Tree Level Order Traversal IIBFS (分層)TreePython
133Clone GraphBFS (分層)GraphPython Graph 的基本操作 #重要題型
127Word LadderBFS (分層), DFSGraphPython
[Lint] 127Topological SortingBFS (拓撲)Python
內有 indegree, outdegree 介紹 #重要題型
207Course ScheduleBFS (拓樸)GraphPython
210Course Schedule IIBFS (拓樸)GraphPython
[Lint] 892Alien DictionaryBFS (拓樸)GraphPython
[Lint] 431Connected Component in Undirected GraphBFS (連通塊)GraphPython 內含 BFS 模板 #重要題型
1091Shortest Path in Binary MatrixBFS (最短路徑)MatrixPython
⭐ Binary Serach 相關題型 ⭐
33Search in Rotated Sorted ArrayBinary SerachArrayPython #重要題型
34Find First and Last Position of Element in Sorted ArrayBinary SerachPython
50Pow(x, n) Binary SerachPython
153Find Minimum in Rotated Sorted Array Binary SerachArrayPython
162Find Peak ElementBinary SerachPython
278First Bad VersionBinary SerachPython
658Find K Closest ElementsBinary SerachPython
704Binary SearchBinary SerachPython
852Peak Index in a Mountain ArrayBinary SerachPython
[Lint] 14First Position of TargetBinary SerachPython
[Lint] 140Fast PowerBinary SerachPython
[Lint] 447Search in a Big Sorted ArrayBinary SerachArrayPython
[Lint] 458Last Position of TargetBinary SerachPython
191Number of 1 BitsBit ManipulationPython
⭐ Data Stream 相關題型 ⭐
[Lint] 642Moving Average from Data StreamData StreamQueuePython
⭐ Design 相關題型 ⭐
155Min StackDesignPython
[Lint] 659Encode and Decode StringsDesignPython
232Implement Queue using StacksDesignQueue, StackPython
⭐ DFS 相關題型 ⭐
98Validate Binary Search TreeDFSPython
2265Count Nodes Equal to Average of SubtreeDFSPython
292nd Weekly Contest
2261K Divisible Elements SubarraysDFSPython
內含 python substring 常見作法 / 291st LeetCode Weekly Contest
22Generate ParenthesesDFSPython
79Word SearchDFSMatrixPython
126Word Ladder IIDFSPython
212Word Search IIDFSTreePython
290Word PatternDFSPython
[Lint] 829Word Pattern IIDFSPython
31Next PermutationDFS (排列)Python
46PermutationsDFS (排列)Python
#重要題型
47Permutations IIDFS (排列)Python
#重要題型
51N-QueensDFS (排列)Python
52N-Queens IIDFS (排列)Python
[Lint] 862Next Closest TimeDFS (排列)Python
內有 set 判斷是否 subset 的用法
10Regular Expression MatchingDFS (組合)Python
77CombinationsDFS (組合)Python
#重要題型
39Combination SumDFS (組合)Python
40Combination Sum IIDFS (組合)Python
216Combination Sum IIIDFS (組合)Python
377Combination Sum IVDFS (組合)Python
44Wildcard MatchingDFS (組合)Python
78SubsetsDFS (組合)Python
#重要題型
90Subsets IIDFS (組合)Python
#重要題型
131Palindrome PartitioningDFS (組合)Python
139Word BreakDFS (組合)Python
140Word Break IIDFS (組合)Python
[Lint] 90k Sum IIDFS (組合)Python
[Lint] 680Split StringDFS (組合)Python
173Binary Search Tree IteratorDFS (BST)BSTPython
#重要題型
230Kth Smallest Element in a BSTDFS (BST)BSTPython
[Lint] 448Inorder Successor in BSTDFS (BST)BSTPython
[Lint] 900Closest Binary Search Tree ValueDFS (BST)BSTPython
[Lint] 901Closest Binary Search Tree Value IIDFS (BST)BSTPython
#綜合難題
208Implement Trie (Prefix Tree)DFS (Graph)TreePython
17Letter Combinations of a Phone NumberDFS (Graph)GraphPython
332Reconstruct ItineraryDFS (Graph)GraphPython
#重要題型
110Balanced Binary TreeDFS (Tree)TreePython
226Invert Binary TreeDFS (Tree)TreePython
572Subtree of Another TreeDFS (Tree)TreePython
105Construct Binary Tree from Preorder and Inorder TraversalDFS (Tree)TreePython
112Path SumDFS (Tree)Python
113Path Sum IIDFS (Tree)TreePython
235Lowest Common Ancestor of a Binary Search TreeDFS (Tree)TreePython
236Lowest Common Ancestor of a Binary TreeDFS (Tree)TreePython
#重要題型
257Binary Tree PathsDFS (Tree)TreePython
[Lint] 474Lowest Common Ancestor IIDFS (Tree)TreePython
[Lint] 578Lowest Common Ancestor IIIDFS (Tree)TreePython
[Lint] 596Minimum SubtreeDFS (Tree)TreePython
543Diameter of Binary TreeDFS (Tree)Python
144Binary Tree Preorder TraversalDFS (Tree)TreePython
內含 處理 Tree 樹問題的重點
145Binary Tree Postorder TraversalDFS (Tree)TreePython
114Flatten Binary Tree to Linked ListDFS (Tree)TreePython
⭐ Dynamic Programming 相關題型 ⭐
338Counting BitsDPPython
309Best Time to Buy and Sell Stock with CooldownDPPython
2266Count Number of TextsDPPython
292nd Weekly Contest
2262Total Appeal of A StringDPPython
291st Weekly Contest
91Decode Ways DPPython C++
70Climbing Stairs DPPython C++
221Maximal SquareDPPython
53Maximum SubarrayDP (一維)ArrayPython C++ 內含 C++ vector max 用法整理
91Decode WaysDP (一維)Python
55Jump GameDP (一維)Python
#重要題型
45Jump Game IIDP (一維)Python
#重要題型
198House RobberDP (一維)Python
213House Robber IIDP (一維)Python
509Fibonacci NumberDP (一維)Python
122Best Time to Buy and Sell Stock IIDP (一維)Python
300Longest Increasing SubsequenceDP (一維接龍, LIS)Python
#重要題型
62Unique PathsDP (二維)Python C++
63Unique Paths IIDP (二維)Python C++
152Maximum Product SubarrayDP (二維)Python
#重要題型
118Pascal’s TriangleDP (二維)Python
內含 python sum of two list (list add 相加方法整理)
322Coin ChangeDP (背包問題)Python
內含 DP 背包問題模板 #重要題型
518Coin Change 2DP (背包問題)Python
#重要題型
[Lint] 92BackpackDP (背包問題)Python
[Lint] 125Backpack IIDP (背包問題)Python
[Lint] 440Backpack IIIDP (背包問題)Python
[Lint] 562Backpack IVDP (背包問題)Python
[Lint] 563Backpack VDP (背包問題)Python
[Lint] 798Backpack VIIDP (背包問題)Python
[Lint] 799Backpack VIIIDP (背包問題)Python
[Lint] 800Backpack IXDP (背包問題)Python
[Lint] 801Backpack XDP (背包問題)Python
1143Longest Common SubsequenceDP (LCS)Python
494Target SumDP (Memoization)Python
2267Check if There Is a Valid Parentheses String PathDP (Memoization)Python
內含:Memoization 記憶化搜索筆記 / 292nd Weekly Contest
⭐ Hash 相關題型 ⭐
13Roman to IntegerHashPython
73Set Matrix Zeroes HashPython C++ 內含 python while-else 用法說明
692Top K Frequent WordsHashPython
內含 python 自定義排序 key function 的使用方法
846Hand of StraightsHashPython
347Top K Frequent ElementsHashPython
205Isomorphic StringsHashPython
268Missing NumberHashPython
242Valid AnagramHashPython
763Partition LabelsHashIntervalPython
383Ransom NoteHashPython
387 First Unique Character in a String HashPython
2186Minimum Number of Steps to Make Two Strings Anagram IIHashPython
282nd Weekly Contest
[Lint] 793Intersection of ArraysHashPython
146LRU CacheHashPython
387First Unique Character in a StringHashPython
[Lint] 920Meeting RoomsHashIntervalPython
#重要題型
[Lint] 920Meeting RoomsHashIntervalPython
#重要題型
[Lint] 919Meeting Rooms IIHashIntervalPython
#重要題型
[Lint] 919Meeting Rooms IIHashIntervalPython
#重要題型
349 Intersection of Two ArraysHashPython
217Contains DuplicateHashArrayPython
C++ 內含 C++ set, unordered_set 用法整理
137Single Number IIHashPython
350Intersection of Two Arrays IIHashPython
2248Intersection of Multiple ArraysHashPython
290th Weekly Contest
49Group AnagramsHash (Anagrams)Python
217Contains DuplicateHash (Duplicate)Python
128Longest Consecutive SequenceHash (LCS)Python
136Single NumberHash, Bit ManipulationPython
⭐ Heap 相關題型 ⭐
264Ugly Number IIHeapPython
⭐ Stack 相關題型 ⭐
739Daily TemperaturesStackPython
496Next Greater Element IStackPython
503Next Greater Element IIStackPython
20Valid ParenthesesStack (Parentheses)Python
內含用 python List 組出 Stack, Queue 的方法整理
⭐ Two pointers 相關題型 ⭐
11Container With Most WaterTwo pointersPython
42Trapping Rain WaterTwo pointersPython
74Search a 2D Matrix Two pointersMatrixPython
141Linked List CycleTwo pointersLinked ListPython
142Linked List Cycle IITwo pointersLinked ListPython
內含 python while-else 用法介紹
283Move ZeroesTwo pointersPython
876Middle of the Linked ListTwo pointersPython
2260Minimum Consecutive Cards to Pick UpTwo pointers (快慢)Python
291st Weekly Contest
21Merge Two Sorted ListsTwo pointers (Merge)Linked ListPython
內含 python Linked List 基本操作 (for 新手教學)
88Merge Sorted Array Two pointers (Merge)Python C++ 內含 python while-else 用法說明
1Two SumTwo pointers (NSum)ArrayPython C++ 內有 Python list comprehesion / dict comprehesion 整理 / C++ map find 方法補充 (dict find)
153Sum Two pointers (NSum)ArrayPython
163Sum ClosestTwo pointers (NSum)Python
167Two Sum II – Input Array Is SortedTwo pointers (NSum)Python
[Lint] 382Triangle CountTwo pointers (NSum)Python
[Lint] 533Two Sum – Closest to TargetTwo pointers (NSum)Python
[Lint] 587Two Sum – Unique PairsTwo pointers (NSum)Python
5Longest Palindromic Substring Two pointers (Palindrome)Python C++ 內含 C++ string.substr() 用法筆記
9Palindrome NumberTwo pointers (Palindrome)Python
125Valid PalindromeTwo pointers (Palindrome)StringPython內含 python isalpha(), isalnum() 的整理
680Valid Palindrome IITwo pointers (Palindrome)Python
409Longest Palindrome
Two pointers (Palindrome)Python
647Palindromic SubstringsTwo pointers (Palindrome)Python
234Palindrome Linked ListTwo pointers (Palindrome)Linked ListPython
內含 reverse LinkedList 方法
75Sort ColorsTwo pointers (partition)Python
#重要題型
[Lint] 5Kth Largest ElementTwo pointers (partition)Python
#重要題型
[Lint] 31Partition ArrayTwo pointers (partition)Python
#重要題型
[Lint] 143Sort Colors IITwo pointers (partition)Python
#重要題型
[Lint] 461Kth Smallest Numbers in Unsorted ArrayTwo pointers (partition)Python
#重要題型
3Longest Substring Without Repeating CharactersTwo pointers (Sliding Window)Python
76 Minimum Window SubstringTwo pointers (Sliding Window)Python
239Sliding Window MaximumTwo pointers (Sliding Window)Python
⭐ 其他題型 / 待分類 ⭐
2Add Two NumbersLinked ListPython
7Reverse IntegerPython
19Remove Nth Node From End of ListLinked ListPython
36Valid SudokuPython
48Rotate ImageMatrixPython
621Task SchedulerPython
202Happy NumberPython
238Product of Array Except SelfPython
222Count Complete Tree NodesTreePython
674Longest Continuous Increasing SubsequencePython
435Non-overlapping IntervalsIntervalPython
88Merge Sorted ArrayPython
內含 python while-else 用法說明
2264Largest 3-Same-Digit Number in StringPython
292nd Weekly Contest
56Merge IntervalsIntervalPython
內含:python sorted key 搭配 lambda 的用法範例
57Insert IntervalIntervalPython
61Rotate ListLinked ListPython
2259Remove Digit From Number to Maximize ResultPython
291st Weekly Contest
53Maximum SubarrayPython
54Spiral MatrixPython
228Summary RangesPython
263Ugly NumberPython
203Remove Linked List ElementsLinked ListPython
內含 Linked List remove 操作 part 2 (for 新手教學)
206Reverse Linked ListLinked ListPython
內含 Linked List reverse 反轉操作 part 3 (for 新手教學)
189Rotate ArrayArrayPython
2185Counting Words With a Given PrefixStringPython
282nd Weekly Contest
134Gas StationPython
121Best Time to Buy and Sell StockPython
83Remove Duplicates from Sorted ListLinked ListPython
566Reshape the MatrixMatrixPython
內含 python array 初始化, index 操作與控制範例
2243Calculate Digit Sum of a StringPython
289th Weekly Contest
2244Minimum Rounds to Complete All TasksPython
289th Weekly Contest
2249Count Lattice Points Inside a CirclePython
290th Weekly Contest
⭐【喜歡我的文章嗎? 歡迎幫我按讚~ 讓基金會請創作者喝一杯咖啡!
如果喜歡我的文章,請幫我在下方【按五下Like】 (Google, Facebook 免註冊),會由 「LikeCoin」 贊助作者鼓勵繼續創作,讀者們「只需幫忙按讚,完全不用出錢」哦!

likecoin-steps
Howard Weng
Howard Weng

我是 Howard Weng,很多人叫我嗡嗡。這個網站放了我的各種筆記。希望這些筆記也能順便幫助到有需要的人們!如果文章有幫助到你的話,歡迎幫我點讚哦!
另外,因為定位是「個人的隨手筆記」,有些文章內容「⚠️可能我理解有誤⚠️」或「?只寫到一半?」,如果有發現這樣的情況,歡迎在該文章的最下面留言提醒我!我會儘快修正或補上!感謝大家的建議與幫忙,讓網站能變得更好?

文章: 883

1 則留言

★留個言吧!內容有誤或想要補充也歡迎與我討論!