題目出處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 的範圍)。
題目預設是沒有,這裡我多處理了一個 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度 = 轉置 + 左右翻轉」的概念
(嗯… 有夠快的…,我們剛剛在幹嘛)
仔細分析題目的能力還是很重要的!!! (不一定是解題,工作上更是常需要!)
轉置細節:也是不能無聊全部掃過即使是轉置矩陣,我們也沒辦法無腦掃過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
慢慢來,我們把他慢慢的都寫出來示意圖:(一個個把算式寫出來就對了! 就只有這四行關鍵算式!!!)
Reference⭐ 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 」 贊助作者鼓勵繼續創作,讀者們「只需幫忙按讚,完全不用出錢 」哦!
[…] […]