LeetCode - 330. Patching Array
Hard
要寫出不 Memory Limit Exceeded 和 Time Limit Exceeded 真的要很 Greedy
本題解法參考了 bhanu_bhakta 大佬的解法
這位老哥實在是太神了,我原本的解法是用 maxHeap
來解這題,
但老哥的解法簡短到讓我看了不得不為之一驚,所以我把看了他的解法後的逐步解題思路和程式寫在下面,
最後再感嘆一次,實在太神了..
題目
Given a sorted integer array nums
and an integer n
, add/patch elements to the array such that any number in the range [1, n]
inclusive can be formed by the sum of some elements in the array.
Return the minimum number of patches required.
Example 1:
Input: nums = [1,3]
, n = 6
Output: 1
Explanation:
Combinations of nums are [1]
, [3]
, [1,3]
, which form possible sums of: 1
, 3
, 4
.
Now if we add/patch 2
to nums, the combinations are: [1]
, [2]
, [3]
, [1,3]
, [2,3]
, [1,2,3]
.
Possible sums are 1
, 2
, 3
, 4
, 5
, 6
, which now covers the range [1, 6]
.
So we only need 1
patch.
Example 2:
Input: nums = [1,5,10]
, n = 20
Output: 2
Explanation: The two patches can be [2, 4]
.
Example 3:
Input: nums = [1,2,2]
, n = 5
Output: 0
Constraints:
1 <= nums.length <= 1000
1 <= nums[i] <=
nums is sorted in ascending order.
1 <= n <=
- 1
解題思路
farPtr: 目前可以加總到的最遠距離是到 num[i] + sumPtr
確認 farPtr 他自己可以加總到的最遠距離 farPtr + (farPtr - 1)
再 + 1
是否已存在於 nums
節至某格 nums[i]
為止,這個 num
小於 farPtr
,代表它已經可以被加總出來,所以 farPtr
再加上這個 num
,讓加總到的最遠距離可以變得更遠
反之,如果 nums[i]
比 farPtr
大,代表目前的 farPtr
還沒到達可以組出他的距離,則更新 farPtr + (farPtr - 1) 再 + 1
程式邏輯詳細解釋
以 Case 2: nums = [1, 5, 10]
, n = 20
為例
1. farPtr = 1, i = 0
nums[0] = 1 <= farPtr
farPtr += nums[0]
: farPtr = 1 + 1 = 2
i += 1
目前總共可以用來組合的數字有 [1]
現在可以證明到 farPtr = 2 - 1
的 1
為止,存在 [1]
可以組合出 1
,現在把 farPtr
更新到未知是否可以的 2
2. farPtr = 2, i = 1
nums[1] = 5 > farPtr
farPtr += farPtr
: farPtr = 2 + 2 = 4
ans += 1
(因為 patches 2
)
因為 5
無法被組出來,所以要加入 “2
“
目前總共可以用來組合的數字有 [1, 2]
3. farPtr = 4, i = 1
nums[1] = 5 > farPtr
farPtr += farPtr
: farPtr = 4 + 4 = 8
ans += 1
(因為 patches 4
)
因為 5
還是無法被組出來,所以要加入 “4
“
目前總共可以用來組合的數字有 [1, 2, 4]
4. farPtr = 8, i = 1
nums[1] = 5 <= farPtr
farPtr += nums[1]
: farPtr = 8 + 5 = 13
i += 1
目前總共可以用來組合的數字有 [1, 2, 4, 5]
現在可以證明到 farPtr = 13 - 1
的 12
為止,存在 [1]
, [2]
, [1, 2]
, [4]
, [5]
, [1, 2, 3]
, [1, 2, 4]
, [1, 2, 5]
, [4, 5]
, [1, 4, 5]
, [2, 4, 5]
, [1, 2, 4, 5]
可以組合出 1 ~ 12
,現在把 farPtr
更新到未知是否可以的 13
5. farPtr = 13, i = 2
nums[2] = 10 <= farPtr
farPtr += nums[2]
: farPtr = 13 + 10 = 23
i += 1
目前總共可以用來組合的數字有 [1, 2, 4, 5, 10]
現在可以證明到 farPtr = 23 - 1
的 22
為止,存在 [1]
, [2]
, [1, 2]
, [4]
, [5]
, [1, 2, 3]
, [1, 2, 4]
, [1, 2, 5]
, [4, 5]
, [10]
, [1, 10]
, [2, 10]
, [1, 2, 10]
, [4, 10]
, [5, 10]
, [1, 5, 10]
, [2, 5, 10]
, [1, 2, 5, 10]
, [4, 5, 10]
, [1, 4, 5, 10]
, [2, 4, 5, 10]
, [1, 4, 5, 10]
可以組合出 1 ~ 22
,現在把 farPtr
更新到未知是否可以的 23
而其中,也可以發現我們現已可以解出 n (n = 20)
6. farPtr = 23 > n (n = 20)
break
Solution Code
1 | class Solution(object): |