Greedy (8) - HackMD

# Greedy (8) > 紀錄 NeetCode-150 與 LeetCode 的解題想法、刷題過程與錯誤，以 Python 或 C++ 兩種語言為主 > > 其他 NeetCode-150 或 LeetCode 的主題請見 [Here](https://hackmd.io/-ovTFlzLRWaSgzDGhbSwsA)  Greedy 的題目重點在於透過適合的 greedy rule 將問題分解，找到每個 subproblem 的局部最佳解後，再從每一次的局部最佳解構成最後的解集合。 ## 1. Maximum Subarray **Medium** > Given an array of integers `nums`, find the subarray with the largest sum and return the sum. > > A **subarray** is a contiguous non-empty sequence of elements within an array. ### Example 1: ```java Input: nums = [2,-3,4,-2,2,1,-1,4] Output: 8 ``` Explanation: The subarray [4,-2,2,1,-1,4] has the largest sum 8. ### Example 2: ```java Input: nums = [-1] Output: -1 ``` ### Constraints * `1 <= nums.length <= 1000` * `-1000 <= nums[i] <= 1000` ### Recommended complexity * Time complexity: $O(n)$ * Space complexity: $O(1)$ ### Solution **Greedy rule:** 對於 index = i 的元素，分析要不要將他加入至目前的 subArray 之中使它對目前的最大和(local optimal)有貢獻。迭代輸入陣列 nums 並維護一個當前最大和 surrSum 以及全局最大和 maxSum，每個元素考慮以下狀況: * 加上 nums[i] 後總和 >= nums[i] * 表示 nums[i] 對 currSum 有貢獻 * 可加入 subarray 之中 * 加上 nums[i] 後總和 < nums[i] * 表示不需要前面的 subarray，因為前面的元素會拖垮後面的表現 * 更新 currSum 與 maxSum * 並從 nums[i] 開始做為第一個元素，往後找新的 subarray ```python= class Solution: def maxSubArray(self, nums: List[int]) -> int: maxSum = nums[0] currSum = 0 for n in nums: if currSum + n < n: currSum = 0 currSum += n maxSum = max(currSum, maxSum) return maxSum ``` ## 2. Jump Game **Medium** > You are given an integer array `nums` where each element `nums[i]` indicates your maximum jump length at that position. > > Return `true` if you can reach the last index starting from index `0`, or `false` otherwise. ### Example 1: ```java Input: nums = [1,2,0,1,0] Output: true ``` Explanation: First jump from index 0 to 1, then from index 1 to 3, and lastly from index 3 to 4. ### Example 2: ```java Input: nums = [1,2,1,0,1] Output: false ``` ### Constraints * `1 <= nums.length <= 1000` * `0 <= nums[i] <= 1000` ### Recommended complexity * Time complexity: $O(n)$ * Space complexity: $O(1)$ ### Solution **Greedy rule:** 找到每個能抵達局部終點的局部最佳解 (1) 能不能抵達終點最快的看法是從終點往回逆推，如果回推的某個點能夠抵達目前的終點，表示此點是一個局部最佳解 (2) 此時將終點更新為這個局部最佳解的點，並繼續逆推找下一個最佳解 (3) 直到找到起點為止，表示能夠從起點透過上述的每個局部最佳解走到終點 ```python= class Solution: def canJump(self, nums: List[int]) -> bool: n = len(nums) dst = n - 1 for i in range(n - 2, -1, -1): if nums[i] + i >= dst: dst = i return True if dst == 0 else False ``` ## 3. Jump Game ll **Medium** > You are given an array of integers `nums`, where `nums[i]` represents the maximum length of a jump towards the right from index `i`. For example, if you are at `nums[i]`, you can jump to any index `i + j` where: > > * `j <= nums[i]` > * `i + j < nums.length` > > You are initially positioned at `nums[0]`. > > Return the minimum number of jumps to reach the last position in the array (index `nums.length - 1`). You may assume there is always a valid answer. ### Example 1: ```java Input: nums = [2,4,1,1,1,1] Output: 2 ``` Explanation: Jump from index 0 to index 1, then jump from index 1 to the last index. ### Example 2: ```java Input: nums = [2,1,2,1,0] Output: 2 ``` ### Constraints * `1 <= nums.length <= 1000` * `0 <= nums[i] <= 100` ### Recommended complexity * Time complexity: $O(n)$ * Space complexity: $O(1)$ ### Solution **Greedy rule:** 每次尋找能夠走最遠距離的點作為局部最佳解 * 維護兩個指標 `leftPtr` 與 `rightPtr`，這兩個指標間的點表示目前可以抵達的點 * 初始化，兩個指標都從 index = 0 的起點開始 * 透過迭代可以抵達的點尋找最遠距離 * 迭代完並找到最遠距離後，更新下一段的指標 * leftPtr = rightPtr + 1 * rightPtr = 距離最遠的點 * 當右指標(最遠點)超過終點位置，表示抵達最後終點每次在找最遠距離時，每更新一次指標就表示選擇一個點前進 $\Rightarrow$ 步數 + 1 ```python= class Solution: def jump(self, nums: List[int]) -> int: leftPtr, rightPtr = 0, 0 res = 0 while rightPtr < len(nums) - 1: # go through the reachable index farIdx = rightPtr for i in range(leftPtr, rightPtr + 1): farIdx = max(farIdx, i + nums[i]) # update left and right pointer leftPtr = rightPtr + 1 rightPtr = farIdx res += 1 return res ``` ## 4. Gas Station **Medium** > There are `n` gas stations along a circular route. You are given two integer arrays `gas` and `cost` where: > > `gas[i]` is the amount of gas at the `ith` station. > `cost[i]` is the amount of gas needed to travel from the `ith` station to the `(i + 1)th` station. (The last station is connected to the first station) > > You have a car that can store an unlimited amount of gas, but you begin the journey with an empty tank at one of the gas stations. > > Return the starting gas station's index such that you can travel around the circuit once in the clockwise direction. If it's impossible, then return `-1`. > > It's guaranteed that at most one solution exists. ### Example 1: ```java Input: gas = [1,2,3,4], cost = [2,2,4,1] Output: 3 ``` Explanation: Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4 Travel to station 0. Your tank = 4 - 1 + 1 = 3 Travel to station 1. Your tank = 3 - 2 + 2 = 3 Travel to station 2. Your tank = 3 - 2 + 3 = 4 Travel to station 3. Your tank = 2 - 4 + 4 = 2 ### Example 2: ```java Input: gas = [1,2,3], cost = [2,3,2] Output: -1 ``` Explanation: You can't start at station 0 or 1, since there isn't enough gas to travel to the next station. If you start at station 2, you can move to station 0, and then station 1. At station 1 your tank = 0 + 3 - 2 + 1 - 2 = 0. You're stuck at station 1, so you can't travel around the circuit. ### Constraints * `1 <= gas.length == cost.length <= 1000` * `0 <= gas[i], cost[i] <= 1000` ### Recommended complexity * Time complexity: $O(n)$ * n is the size of input array * Space complexity: $O(1)$ ### Solution **Greedy rule:** 選定起點後開始走，如果在某個中間站點的油量 < 0 表示該點不能做為起點當發現某個點不能做為起點，意味著從這個起點開始到油量 < 0 的點，瓦斯補給(`gas`)的總和 < 消耗成本(`cost`)的總和，因此中間路途的點都不能作為起點。Step-by-step 如下: * 設總油量 `total = 0`，起點為 index = 0 * 以單一站點來看，離開每個站點後所剩的油量為 `remains = gas[i] - cost[i]`(先補給再消耗) * 若 `total + remains < 0` 表示油量不夠 * 以下一個點 index = `i + 1` 作為新的起點 * 更新總油量 `total = 0` ```python= class Solution: def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int: if sum(gas) < sum(cost): return -1 totalGas = 0 n = len(gas) startIdx = 0 for i in range(n): remains = gas[i] - cost[i] totalGas += remains if totalGas < 0: totalGas = 0 startIdx = i + 1 return startIdx ``` ## 5. Hamd of Straights **Medium** > You are given an integer array `hand` where `hand[i]` is the value written on the `ith` card and an integer `groupSize`. > > You want to rearrange the cards into groups so that each group is of size `groupSize`, and card values are consecutively increasing by `1`. > > Return `true` if it's possible to rearrange the cards in this way, otherwise, return `false`. ### Example 1: ```java Input: hand = [1,2,4,2,3,5,3,4], groupSize = 4 Output: true ``` Explanation: The cards can be rearranged as `[1,2,3,4]` and `[2,3,4,5]`. ### Example 2: ```java Input: hand = [1,2,3,3,4,5,6,7], groupSize = 4 Output: false ``` Explanation: The closest we can get is `[1,2,3,4]` and `[3,5,6,7]`, but the cards in the second group are not consecutive. ### Constraints: * `1 <= hand.length <= 1000` * `0 <= hand[i] <= 1000` * `1 <= groupSize <= hand.length` ### Recommended complexity * Time complexity: $O(n \cdot \log n)$ * Spce complexity: $O(n)$ ### Solution **Greedy rule:** 每次從最小的數字開始形成一個 group (局部最佳解) * 每個數字可能提供給多個 group 使用，所以要先計算/紀錄每個數字出現的頻率 * 將給定的 array 排序，從最小的數字開始建立 group * 選定最小的數字(假設為 n)後，因為 group 內的數字是每次遞增 1，所以直接把 n, n+1, n+2, n+3 這四個數字的頻率 - 1 表示用這四個數字形成一個 group * 如果某數字不存在或頻率不夠(=0)，表示不能建立這組 group > [!Tip] > * 選定最小數字作為每個 group 的起點，後面 groupSize - 1 個數字直接以迭代遞增的方式找出來然後把頻率/次數 - 1 即可，不用真的創建 group 放入數字 > * 完成一個 group 後(local optimal)再完成下一個 group，這樣的目的是符合 greedy 的概念 ```python= class Solution: def isNStraightHand(self, hand: List[int], groupSize: int) -> bool: if len(hand) % groupSize: return False count = {} for i in hand: count[i] = 1 + count.get(i, 0) hand.sort() for i in hand: if count[i] != 0: for j in range(i, i + groupSize): if (j in count) and (count[j] > 0): count[j] -= 1 else: return False return True ``` ## 6. Merge Triplets to Form Target **Medium** > You are given a 2D array of integers `triplets`, where `triplets[i] = [ai, bi, ci]` represents the `ith` triplet. You are also given an array of integers `target = [x, y, z]` which is the triplet we want to obtain. > > To obtain `target`, you may apply the following operation on `triplets` zero or more times: > > Choose two different triplets `triplets[i]` and `triplets[j]` and update `triplets[j]` to become `[max(ai, aj), max(bi, bj), max(ci, cj)]`. > > * E.g. if `triplets[i] = [1, 3, 1]` and `triplets[j] = [2, 1, 2]`, `triplets[j]` will be updated to `[max(1, 2), max(3, 1), max(1, 2)] = [2, 3, 2]`. > > Return `true` if it is possible to obtain `target` as an **element of** `triplets`, or `false` otherwise. ### Example 1: ```java Input: triplets = [[1,2,3],[7,1,1]], target = [7,2,3] Output: true ``` Explanation: Choose the first and second triplets, update the second triplet to be [max(1, 7), max(2, 1), max(3, 1)] = [7, 2, 3]. ### Example 2: ```java Input: triplets = [[2,5,6],[1,4,4],[5,7,5]], target = [5,4,6] Output: false ``` ### Constraints: * `1 <= triplets.length <= 1000` * `1 <= triplets.length <= 1000` ### Recommended complexity * Time complexity: $O(n)$ * n is the size of the input array * Space complexity: $O(1)$ ### Solution **Greedy rule:** 刪除不合理的組別，每次挑選可以符合 target[i] 的位置(local optimal) (1) 刪除不合理只要某個組別(`tri`)中的三個數字有一個(`tri[i]`)大於對應的 target 值(`target[i]`)，表示該組不可能對 target 有貢獻。 (2) 挑選剩餘組別剩餘組別的值必定 <= 對應的 target 值，只有剩餘組別中有一個數字 = 對應的 target 值，則該組必定可以透過交換保留它並湊出最後的 target。 ```python= class Solution: def mergeTriplets(self, triplets: List[List[int]], target: List[int]) -> bool: candidate = set() for tri in triplets: if tri[0] > target[0] or tri[1] > target[1] or tri[2] > target[2]: continue for idx, value in enumerate(tri): if value == target[idx]: candidate.add(idx) return len(candidate) == 3 ``` ## 7. Partition Labels **Medium** > You are given a string `s` consisting of lowercase english letters. > > We want to split the string into as many substrings as possible, while ensuring that each letter appears in at most one substring. > > Return a list of integers representing the size of these substrings in the order they appear in the string. ### Example 1: ```java Input: s = "xyxxyzbzbbisl" Output: [5, 5, 1, 1, 1] ``` Explanation: The string can be split into `["xyxxy", "zbzbb", "i", "s", "l"]`. ### Example 2: ```java Input: s = "abcabc" Output: [6] ``` ### Constraints * `1 <= s.length <= 100` ### Recommended complexity * Time complexity: $O(n)$ * n is the length og the string `s` * Space complexity: $O(m)$ * m is the number of unique characters in the string `s` ### Solution (1) 原本的想法 **Greedy rule:** 每次完成一個字母做為局部最佳解 * 根據題意所說，每個字母只能出現在最多一個 substring 中，所以需要計算每個字母剩餘的出現次數/頻率 * 以 two pointer 做搜索，左指標指向目前正在處理的字元，右指標歷遍 substring 字串 * 右指標歷遍字串的過程中，每碰到一個字元就將它的出現次數 - 1，直到左指標指向的字元的頻率 = 0 時表示該字元處理完 * 左指標 + 1 處理下一個字元 * 直到左指標 = 右指標，表示找到 substring 的分界點，再計算 sustring 的長度 ```python= class Solution: def partitionLabels(self, s: str) -> List[int]: count = {} for ch in s: count[ch] = 1 + count.get(ch, 0) LP, RP = 0, 0 start = 0 res = [] while LP < len(s): ch = s[LP] while count[ch] != 0: count[s[RP]] -= 1 RP += 1 LP += 1 if LP == RP: res.append(RP - start) start = RP return res ``` (2) Improvement **Greedy rule:** 每次完成一個字母做為局部最佳解 * 要完成一個字母最快的方式就是直接找到它出現的最後位置，就是該字母需要對應的 substring 長度 * 從頭開始歷遍字串 `s` * 尋找每個字母最後出現的位置並取最大值 * 當最大位置 = 目前正在處理的位置，表示找到 substring 的分界點 * 再計算 substring 長度 ```python= class Solution: def partitionLabels(self, s: str) -> List[int]: lastIndex = {} for idx, ch in enumerate(s): lastIndex[ch] = idx res = [] size = 0 end = 0 for idx, ch in enumerate(s): size += 1 end = max(end, lastIndex[ch]) if idx == end: res.append(size) size = 0 return res ``` ## 8. Valid Parenthesis String **Medium** > You are given a string `s` which contains only three types of characters: `'('`, `')'` and `'*'`. > > Return `true` if `s` is **valid**, otherwise return `false`. > > A string is valid if it follows all of the following rules: > > * Every left parenthesis `'('` must have a corresponding right parenthesis `')'`. > * Every right parenthesis `')'` must have a corresponding left parenthesis `'('`. > * Left parenthesis `'('` must go before the corresponding right parenthesis `')'`. > * A `'*'` could be treated as a right parenthesis `')'` character or a left parenthesis `'('` character, or as an empty string `""`. ### Example 1: ```java Input: s = "((**)" Output: true ``` Explanation: One of the `'*'` could be a `')'` and the other could be an empty string. ### Example 2: ```java Input: s = "(((*)" Output: false ``` Explanation: The string is not valid because there is an extra `'('` at the beginning, regardless of the extra `'*'`. ### Constraints * `1 <= s.length <= 100` ### Recommended complexity * Time complexity: as good or better than $O(n)$ * Space complexity: as good or better than $O(n)$ ### Soluton **Greedy rule**: 維護一個可能的左括的出現次數的範圍每一個 ( 都需要一個 ) 配對才能組成一組括號，因此當發現一個 ( 時左括號的出現次數 + 1，反之出現 ) 時左括號出現次數 - 1。又因為 `*` 符號可以作為 ( 與 ) 使用，所以遇到 `*` 時可以同時 + 1 或 - 1。因此最後計算出的結果 ( 出現次數應該是一個範圍，具有最大值 leftMax(未匹配的 `(` 的最大數量) 與最小值 leftMin(未匹配的 `(` 的最小數量)。只有 leftMin = 0 的狀況才是合理的，因為每組括號都可以正確閉合。 * 當 leftMax < 0 表示 ) 太多，無法形成合理的括號對 * 當 leftMin < 0 表示出現了多餘的 )，無法形成合理的括號對 ```python= class Solution: def checkValidString(self, s: str) -> bool: leftMin, leftMax = 0, 0 for ch in s: if ch == ')': leftMin, leftMax = leftMin - 1, leftMax - 1 elif ch == '(': leftMin, leftMax = leftMin + 1, leftMax + 1 else: # when * appear leftMin, leftMax = leftMin - 1, leftMax + 1 if leftMax < 0: return False if leftMin < 0: leftMin = 0 return leftMin == 0 ```