问题描述:
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，问最少向数组中添加多少元素使得从nums[ ]中取若干元素的和能够覆盖[1, n]
解题思路:
我们可以试着从1到n检查每个数（记为current）是否满足。对于每一个current，先从输入数组nums中查看是否有满足条件的数（即是否nums[i] <= current，i表示nums数组中的数用到第几个，初始为0），若有则使用并进行i++、current += nums[i]（current至current + nums - 1可由current-nums[i]到current - 1分别加上nums[i]得到）操作；若无则添加新元素current并进行current = current * 2操作。
具体的，扫描数组nums，更新原则如下：
- 若nums[i] <= current , 则把nums[i]用掉（即 i++），同时current更新为current + nums[i];
- 若nums[i] > current，则添加新的元素current，同时current更新为current * 2.
但须注意：
current从1开始
current可能超过int型，需使用long型
示例代码:
class Solution {
public:
int minPatches(vector<int>& nums, int n) {
int len = nums.size();
if(len == 0){
return log2(n) + 1;
}
long current = 1;
int i = 0, count = 0;
while(current <= n){
if(i < len && nums[i] <= current){
current += nums[i];
i++;
}
else{
count++;
current *= 2;
}
}
return count;
}
};