When the lord closes a door, somewhere he opens a window.
当主关上了一扇门,就会在别处打开一扇窗。 给定一个已排序的正整数数组nums,和一个正整数n。从[1, n]区间内选取任意个数字补充到nums中,使得[1,n]区间内的任何数字都可以用 nums中某几个数字的和来表示。请输出满足上述要求的最少需要补充的数字个数。 示例 1: 输入: nums=[1,3],n=6 输出:1 解释: 根据nums里现有的组合[1],[3],[1,3],可以得出1,3,4。 现在如果我们将 2 添加到 nums 中, 组合变为: [1], [2], [3], [1,3], [2,3], [1,2,3]。 其和可以表示数字1,2,3,4,5,6,能够覆盖[1,6]区间里所有的数。 所以我们最少需要添加一个数字。
示例 2: 输入:nums=[1,5,10],n=20 输出:2 解释:我们需要添加[2,4]。
示例 3: 这题让从数组中找出任意数字都可以组成n,题中说了,数组是排序的。 假设数组中前k个数字能组成的数字范围是[1,total],当我们添加数组中第k+1个数字nums[k](数组的下标是从0开始的)的时候,范围就变成了[1,total]U[nums[k],nums[k]]U[1+nums[k],total+nums[k]],这是个并集,可以合并成[1,total]U[nums[k],total+nums[k]],我们仔细观察一下 1,如果左边的total<nums[k]-1,那么他们中间肯定会有空缺,不能构成完整的[1,total+nums[k]]。 举个例子 [1,5]U[7,10],因为5<7-1,所以是没法构成[1,10]的 这个时候我们需要添加一个数字total+1。先构成一个更大的范围[1,total*2+1]。 这里为什么是添加total+1而不是添加total,我举个例子,比如可以构成的数字范围是[1,5],如果需要添加一个构成更大范围的,我们应该选择6而不是选择5。 2,如果左边的total>=nums[k]-1,那么就可以构成完整的[1,total+nums[k]],就不需要在添加数字了。 来看下代码 1public int minPatches(int[] nums, int n) { 2 //累加的总和 3 long total = 0; 4 //需要补充的数字个数 5 int count = 0; 6 //访问的数组下标索引 7 int index = 0; 8 while (total < n) { 9 if (index < nums.length && nums[index] <= total + 1) { 10 //如果数组能组成的数字范围是[1,total],那么加上nums[index] 11 //就变成了[1,total]U[nums[index],total+nums[index]] 12 //结果就是[1,total+nums[index]] 13 total += nums[index++]; 14 } else { 15 //添加一个新数字,并且count加1 16 total = total + (total + 1); 17 count++; 18 } 19 } 20 return count; 21}
上面组成数字的范围是闭区间,我们还可以改成开区间[1,total) ,原理都一样,稍作修改即可,代码如下 1public int minPatches(int[] nums, int n) { 2 //累加的总和 3 long total = 1; 4 //需要补充的数字个数 5 int count = 0; 6 //访问的数组下标索引 7 int index = 0; 8 while (total <= n) { 9 if (index < nums.length && nums[index] <= total) { 10 //如果数组能组成的数字范围是[1,total),那么加上nums[index] 11 //就变成了[1,total)U[nums[index],total+nums[index]) 12 //结果就是[1,total+nums[index]) 13 total += nums[index++]; 14 } else { 15 //添加一个新数字,并且count加1 16 total <<= 1; 17 count++; 18 } 19 } 20 return count; 21}
|