516,贪心算法解按要求补齐数组

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:

输入:nums=[1,2,2],n=5

输出:0

 

贪心算法解决

这题让从数组中找出任意数字都可以组成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}
上一篇:阿里云对象存储OSS————跨域资源共享(CORS)(m3u8 无法加载m3u8:跨域访问被拒绝)


下一篇:leetcode——第516题——最长回文子序列