LC330. 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.
求能够利用nums里的元素构成[1, n]的所有数字，至少加入多少新元素。没什么思路看了史蒂芬大神的解法。
public class Solution {
public int minPatches(int[] nums, int n) {
// miss may exceed int_max
// nums can form [1, miss)
long miss = 1;
int res = 0, i = 0;
while(miss <= n){
if(i < nums.length && nums[i] <= miss){
miss += nums[i++];
}else{
miss += miss;
res++;
}
} // while
return res;
}
}
假设miss为第一个不能到达的数。首先假设miss = 1，如果nums[i] <= miss，更新miss = miss + nums[i]即可。 如果nums[i] > miss, 利用小于miss的所有数字，这时候需要加入miss这个值，更新miss = 2*miss, 直到达到n。