题目描述：

LeetCode 330. Patching 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.

Example 2:
nums = [1, 5, 10], n = 20
Return 2.
The two patches can be [2, 4].

Example 3:
nums = [1, 2, 2], n = 5
Return 0.

题目大意：

给定一个有序正整数数组nums以及一个整数n，向数组中添加/补充一些元素，使其“部分元素和”可以组成范围[1, n]内的所有数字。返回最少需要添加的元素个数。

测试用例如题目描述。

解题思路：

贪心算法（Greedy Algorithm）

参阅解法：https://leetcode.com/discuss/82822/solution-explanation

假设数组nums的“部分元素和”可以表示范围[1, total)内的所有数字，

那么向nums中添加元素add可以将表示范围扩充至[1, total + add)，其中add ≤ total，当且仅当add = total时取到范围上界[1, 2 * total)

若nums数组为空，则构造[1, n]的nums为[1, 2, 4, 8, ..., k]，k为小于等于n的2的幂的最大值。

若nums数组非空，则扩展时利用nums中的已有元素，详见代码。

Python代码：

class Solution(object):
    def minPatches(self, nums, n):
        """
        :type nums: List[int]
        :type n: int
        :rtype: int
        """
        idx, total, ans = 0, 1, 0
        size = len(nums)
        while total <= n:
            if idx < size and nums[idx] <= total:
                total += nums[idx]
                idx += 1
            else:
                total <<= 1
                ans += 1
        return ans

 

本文链接：http://bookshadow.com/weblog/2016/01/27/leetcode-patching-array/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码