Patch Array
题目描述
Given a sorted positive integer array nums and an integer n, add/patch elements to the array such that any number in 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: nums = [1, 3], n = 6 Return 1.
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.
解题方法
我们可以先写几个例子找出规律
- [1]能够表示[1, 2), 加入2
- [1, 2]能够表示[1,4)， 加入4
- [1, 2, 4]能够表示[1, 8), 加入8
- [1, 2, 4 , 8]能够表示[1, 16) 。。。。。
是不断地2倍的成长，如果当前能表示到[0, n)， 即使array中有大于n的数，也是无法表示n的，所以我们需要加入n, 然后再继续判断后面的数是否对于range有影响。
因为array已经是sorted的了，所以我们从前往后loop，将一开始能够达到的range设为[0, miss), miss = 1对于nums[i]:
- nums[i] <= miss, 那么nums[i]对于当前range有影响，range可以扩展为[0, miss+nums[i])
- nums[i] > miss, nums[i]对于当前range无影响，我们需要加入miss, 然后range可以扩展为[0, miss +miss)
当miss > n时，就可以退出Loop了。
这一题有点像jump game ii，可以归类总结。
Solution
class Solution(object):
def minPatches(self, nums, n):
"""
:type nums: List[int]
:type n: int
:rtype: int
"""
miss = 1
i = 0
patch_add = 0
length = len(nums)
while miss <= n:
if i < length and nums[i] <= miss:
miss += nums[i]
i += 1
else:
miss += miss
patch_add += 1
return patch_add