330. Patching Array
又是一道greedy的题目
class Solution(object):
def minPatches(self, nums, n):
"""
:type nums: List[int]
:type n: int
:rtype: int
"""
patch = 0
i = 0
miss = 1
while miss <= n: #* invariant: [1,miss) is covered */
if i >= len(nums) or miss < nums[i]:
miss += miss # patch miss, now we reach miss-1 (already covered) + miss + 1 (next miss)=2*miss
patch += 1
else:
miss += nums[i] # miss >= nums[i], [1,miss) + nums[i] covers miss and move forward
i += 1
return patch
