題目出處143 · Sort Colors II
難度medium
個人範例程式碼from typing import (
List,
)
class Solution:
"""
@param colors: A list of integer
@param k: An integer
@return: nothing
"""
def sort_colors2(self, colors: List[int], k: int):
# write your code here
# sort 1~k
self.partition(colors, 1, k, 0, len(colors)-1)
return
def partition(self, colors, color_from, color_to, start, end):
# end
if color_from == color_to or start == end:
return
left, right = start, end
pivot = (color_from + color_to) // 2
# define
while(left <= right):
while(left <= right and colors[left] <= pivot): # if same, left part
left += 1
while(left <= right and colors[right] > pivot):
right -= 1
if(left <= right):
colors[left], colors[right] = colors[right], colors[left] # careful infinite loop: left, right still can move
else: # split
# print(colors, start, right, left, end)
self.partition(colors, color_from, pivot, start, right)
self.partition(colors, pivot+1, color_to, left, end)
算法說明此題是考 partition 的綜合題。
這題會經常錯在遞迴判斷式與邊界條件,導致無法 AC。
遞迴判斷式 遞迴的定義# define
while(left <= right):
while(left <= right and colors[left] <= pivot): # if same, left part
left += 1
while(left <= right and colors[right] > pivot):
right -= 1
if(left <= right):
colors[left], colors[right] = colors[right], colors[left] # careful infinite loop: left, right still can move
遞迴的拆解這邊要處理的是邊界問題,往前我們還需要多注意 while(left <= right),
這會導致我們是「交錯」才結束,
結束時的狀態為 「start < right < left < end 」,由於與 pivot 相等的在兩側都有可能出現,
拆解的搜尋條件為
self.partition(colors, color_from, pivot, start, right)
self.partition(colors, pivot+1, color_to, left, end)
遞迴的中止如果「color_from color_to」 or 「start end」,return
「color_from color_to」:已經同顏色,不必再分 「start end」:同位置,不必再分 這題沒有特別說要怎麼處理特殊的 input,預設的 input 都給正確的。
Boundary conditions上方已經說明完囉
另解 – 更換中止條件from typing import (
List,
)
class Solution:
"""
@param colors: A list of integer
@param k: An integer
@return: nothing
"""
def sort_colors2(self, colors: List[int], k: int):
# write your code here
# sort 1~k
self.partition(colors, 1, k, 0, len(colors)-1)
return
def partition(self, colors, color_from, color_to, start, end):
# end
if color_from == color_to:
return
left, right = start, end
pivot = (color_from + color_to) // 2
# define
while(left <= right):
while(left <= right and colors[left] <= pivot): # if same, left part
left += 1
while(left <= right and colors[right] > pivot):
right -= 1
if(left <= right):
colors[left], colors[right] = colors[right], colors[left] # careful infinite loop: left, right still can move
else: # split
# print(colors, start, right, left, end)
if start < right: # still need sorting
self.partition(colors, color_from, pivot, start, right)
if left < end: # still need sorting
self.partition(colors, pivot+1, color_to, left, end)
更換部分# end
if color_from == color_to:
return
限制範圍才持續往下做 partition (其實也等同於 start end) if start < right: # still need sorting
self.partition(colors, color_from, pivot, start, right)
if left < end: # still need sorting
self.partition(colors, pivot+1, color_to, left, end)
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 」 贊助作者鼓勵繼續創作,讀者們「只需幫忙按讚,完全不用出錢 」哦!