《貪婪策略》專題 · ttttt

# 《貪婪策略》專題 # 貪婪策略貪婪策略是一種常見的算法思想，具體是指，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，他所做出的是在某種意義上的局部最優解。貪心算法不是對所有問題都能得到整體最優解，關鍵是貪心策略的選擇，選擇的貪心策略必須具備無后效性，即某個狀態以前的過程不會影響以后的狀態，只與當前狀態有關，這點和動態規劃一樣。貪婪策略和動態規劃類似，大多數情況也都是用來處理`極值問題`。 LeetCode 上對于貪婪策略有 73 道題目。我們將其分成幾個類型來講解，截止目前我們暫時只提供`覆蓋`問題，其他的可以期待我的新書或者之后的題解文章。 ## 覆蓋我們挑選三道來講解，這三道題除了使用貪婪法，你也可以嘗試動態規劃來解決。 - [45. 跳躍游戲 II](https://leetcode-cn.com/problems/jump-game-ii/)，困難 - [1024. 視頻拼接](https://leetcode-cn.com/problems/video-stitching/)，中等 - [1326. 灌溉花園的最少水龍頭數目](https://leetcode-cn.com/problems/minimum-number-of-taps-to-open-to-water-a-garden/)，困難覆蓋問題的一大特征，我們可以將其抽象為`給定數軸上的一個大區間 I 和 n 個小區間 i[0], i[1], ..., i[n - 1]，問最少選擇多少個小區間，使得這些小區間的并集可以覆蓋整個大區間。` 我們來看下這三道題吧。 ### 45. 跳躍游戲 II #### 題目描述給定一個非負整數數組，你最初位于數組的第一個位置。數組中的每個元素代表你在該位置可以跳躍的最大長度。你的目標是使用最少的跳躍次數到達數組的最后一個位置。示例: 輸入: \[2,3,1,1,4\] 輸出: 2 解釋: 跳到最后一個位置的最小跳躍數是 2。從下標為 0 跳到下標為 1 的位置，跳 1 步，然后跳 3 步到達數組的最后一個位置。說明: 假設你總是可以到達數組的最后一個位置。 #### 思路貪婪策略，即我們每次在可跳范圍內選擇可以使得跳的更遠的位置，由于題目保證了`你總是可以到達數組的最后一個位置`,因此這種算法是完備的。如下圖，開始的位置是 2，可跳的范圍是橙色的。然后因為 3 可以跳的更遠，所以跳到 3 的位置。 ![](https://img.kancloud.cn/fd/79/fd79a3ebf61891d2aea6d45d026fe316_342x141.jpg) 如下圖，然后現在的位置就是 3 了，能跳的范圍是橙色的，然后因為 4 可以跳的更遠，所以下次跳到 4 的位置。 ![](https://img.kancloud.cn/fd/54/fd5445523c7e68c6d6fa7fd494d5f8bf_433x117.jpg) 寫代碼的話，我們用 end 表示當前能跳的邊界，對于上邊第一個圖的橙色 1，第二個圖中就是橙色的 4，遍歷數組的時候，到了邊界，我們就重新更新新的邊界。 > 圖來自 <https://leetcode-cn.com/u/windliang/> #### 代碼代碼支持：Python3 Python3 Code: ``` <pre class="calibre18">``` class Solution: def jump(self, nums: List[int]) -> int: n, cnt, furthest, end = len(nums), 0, 0, 0 for i in range(n - 1): furthest = max(furthest, nums[i] + i) if i == end: cnt += 1 end = furthest return cnt ``` ``` **復雜度分析** - 時間復雜度：O(N)O(N)O(N)。 - 空間復雜度：O(1)O(1)O(1)。 ### 1024. 視頻拼接 #### 題目描述你將會獲得一系列視頻片段，這些片段來自于一項持續時長為 T 秒的體育賽事。這些片段可能有所重疊，也可能長度不一。視頻片段 clips\[i\] 都用區間進行表示：開始于 clips\[i\]\[0\] 并于 clips\[i\]\[1\] 結束。我們甚至可以對這些片段自由地再剪輯，例如片段 \[0, 7\] 可以剪切成 \[0, 1\] + \[1, 3\] + \[3, 7\] 三部分。我們需要將這些片段進行再剪輯，并將剪輯后的內容拼接成覆蓋整個運動過程的片段（\[0, T\]）。返回所需片段的最小數目，如果無法完成該任務，則返回 -1 。示例 1：輸入：clips = \[\[0,2\],\[4,6\],\[8,10\],\[1,9\],\[1,5\],\[5,9\]\], T = 10 輸出：3 解釋：我們選中 \[0,2\], \[8,10\], \[1,9\] 這三個片段。然后，按下面的方案重制比賽片段：將 \[1,9\] 再剪輯為 \[1,2\] + \[2,8\] + \[8,9\] 。現在我們手上有 \[0,2\] + \[2,8\] + \[8,10\]，而這些涵蓋了整場比賽 \[0, 10\]。示例 2：輸入：clips = \[\[0,1\],\[1,2\]\], T = 5 輸出：-1 解釋：我們無法只用 \[0,1\] 和 \[0,2\] 覆蓋 \[0,5\] 的整個過程。示例 3：輸入：clips = \[\[0,1\],\[6,8\],\[0,2\],\[5,6\],\[0,4\],\[0,3\],\[6,7\],\[1,3\],\[4,7\],\[1,4\],\[2,5\],\[2,6\],\[3,4\],\[4,5\],\[5,7\],\[6,9\]\], T = 9 輸出：3 解釋：我們選取片段 \[0,4\], \[4,7\] 和 \[6,9\] 。示例 4：輸入：clips = \[\[0,4\],\[2,8\]\], T = 5 輸出：2 解釋：注意，你可能錄制超過比賽結束時間的視頻。提示： 1 <= clips.length <= 100 0 <= clips\[i\]\[0\], clips\[i\]\[1\] <= 100 0 <= T <= 100 #### 思路貪婪策略，我們選擇滿足條件的最大值。和上面的不同，這次我們需要手動進行一次排序，實際上貪婪策略經常伴隨著排序，我們按照 clip\[0\]從小到大進行排序。 ![](https://img.kancloud.cn/df/6d/df6d1df4572b11ef8e3dc56b4c7e7ec4_1240x648.jpg) 如圖： - 1 不可以，因此存在斷層 - 2 可以 - 3 不行，因為不到 T 我們當前的 clip 開始結束時間分別為 s，e。上一段 clip 的結束時間是 t1，上上一段 clip 結束時間是 t2。那么這種情況下 t1 實際上是不需要的，因為 t2 完全可以覆蓋它： ![](https://img.kancloud.cn/49/30/4930abbc40430843dfe7853d441115b7_870x172.jpg) 那什么樣 t1 才是需要的呢？如圖： ![](https://img.kancloud.cn/0e/c8/0ec8e71d759302ae14be352de84148a2_804x208.jpg) 用代碼來說的話就是`s > t2 and t2 <= t1` #### 代碼代碼支持：Python3 Python3 Code: ``` <pre class="calibre18">``` class Solution: def videoStitching(self, clips: List[List[int]], T: int) -> int: # t1 表示選取的上一個clip的結束時間 # t2 表示選取的上上一個clip的結束時間 t2, t1, cnt = -1, 0, 0 clips.sort(key=lambda a: a[0]) for s, e in clips: # s > t1 已經確定不可以了， t1 >= T 已經可以了 if s > t1 or t1 >= T: break if s > t2 and t2 <= t1: cnt += 1 t2 = t1 t1 = max(t1,e) return cnt if t1 >= T else - 1 ``` ``` **復雜度分析** - 時間復雜度：由于使用了排序（假設是基于比較的排序），因此時間復雜度為 O(NlogN)O(NlogN)O(NlogN)。 - 空間復雜度：O(1)O(1)O(1)。 ### 1326. 灌溉花園的最少水龍頭數目 #### 題目描述在 x 軸上有一個一維的花園。花園長度為 n，從點 0 開始，到點 n 結束。花園里總共有 n + 1 個水龍頭，分別位于 \[0, 1, ..., n\] 。給你一個整數 n 和一個長度為 n + 1 的整數數組 ranges ，其中 ranges\[i\] （下標從 0 開始）表示：如果打開點 i 處的水龍頭，可以灌溉的區域為 \[i - ranges\[i\], i + ranges\[i\]\] 。請你返回可以灌溉整個花園的最少水龍頭數目。如果花園始終存在無法灌溉到的地方，請你返回 -1 。示例 1： ![](https://img.kancloud.cn/63/96/639673d30232ba886aefb05e59d8d999_418x213.jpg) 輸入：n = 5, ranges = \[3,4,1,1,0,0\] 輸出：1 解釋：點 0 處的水龍頭可以灌溉區間 \[-3,3\] 點 1 處的水龍頭可以灌溉區間 \[-3,5\] 點 2 處的水龍頭可以灌溉區間 \[1,3\] 點 3 處的水龍頭可以灌溉區間 \[2,4\] 點 4 處的水龍頭可以灌溉區間 \[4,4\] 點 5 處的水龍頭可以灌溉區間 \[5,5\] 只需要打開點 1 處的水龍頭即可灌溉整個花園 \[0,5\] 。示例 2：輸入：n = 3, ranges = \[0,0,0,0\] 輸出：-1 解釋：即使打開所有水龍頭，你也無法灌溉整個花園。示例 3：輸入：n = 7, ranges = \[1,2,1,0,2,1,0,1\] 輸出：3 示例 4：輸入：n = 8, ranges = \[4,0,0,0,0,0,0,0,4\] 輸出：2 示例 5：輸入：n = 8, ranges = \[4,0,0,0,4,0,0,0,4\] 輸出：1 提示： 1 <= n <= 10^4 ranges.length == n + 1 0 <= ranges\[i\] <= 100 #### 思路貪心策略，我們盡量找到能夠覆蓋最遠（右邊）位置的水龍頭，并記錄它最右覆蓋的土地。 - 我們使用 furthest\[i\] 來記錄經過每一個水龍頭 i 能夠覆蓋的最右側土地。 - 一共有 n+1 個水龍頭，我們遍歷 n + 1 次。 - 對于每次我們計算水龍頭的左右邊界，\[i - ranges\[i\], i + ranges\[i\]\] - 我們更新左右邊界范圍內的水龍頭的 furthest - 最后從土地 0 開始，一直到土地 n ，記錄水龍頭數目 #### 代碼代碼支持：Python3 Python3 Code: ``` <pre class="calibre18">``` class Solution: def minTaps(self, n: int, ranges: List[int]) -> int: furthest, cnt, cur = [0] * n, 0, 0 for i in range(n + 1): l = max(0, i - ranges[i]) r = min(n, i + ranges[i]) for j in range(l, r): furthest[j] = max(furthest[j], r) while cur < n: if furthest[cur] == 0: return -1 cur = furthest[cur] cnt += 1 return cnt ``` ``` **復雜度分析** - 時間復雜度：時間復雜度取決 l 和 r，也就是說取決于 ranges 數組的值，假設 ranges 的平均大小為 Size 的話，那么時間復雜度為 O(N?Size)O(N \* Size)O(N?Size)。 - 空間復雜度：我們使用了 furthest 數組，因此空間復雜度為 O(N)O(N)O(N)。