当前位置：网站首页>力扣330 按要求补齐数组（贪心）

力扣330 按要求补齐数组（贪心）

2022-08-05 11:07:00 【这代码有点上头】

 

 这道题主要用到了贪心的思想

设想一个情景，我用一堆数能够表示  [1,x-1]的范围的数

那么我将[1,x-1]范围内的数添加一个进来就能够表示x了

但是上面的并不是最优的，再想想，我们不如添加x吧

因为添加x之后，我能够表示数的范围增大了，增大至[1,2x-1]

而你将[1,x-1]范围内的数添加进来达不到这个效果

所以我们秉承这个思想

我们去遍历nums数组，如果该下标的数<=x 那么我们直接扩大x，表示可表示的范围增大了

如果该下标的数超过了x，我们应该怎么办呢？

没错就是将x加入数组，x->2*x

表示我们可表示的范围增加值2x-1

直到2x>这个数

这样才能保证我中间的数都能连续得被表示

代码附上：

int minPatches(vector<int>& nums, int n) {
        int res=0;
        long long x=1;
        int index=0;
        int len=nums.size();
        while(x<=n){
            if(index<len&&nums[index]<=x){
                x+=nums[index];
                index++;
            }
            else{
                x<<=1;
                res++;
            }
        }
        return res;

    }

原网站

版权声明
本文为[这代码有点上头]所创，转载请带上原文链接，感谢
https://blog.csdn.net/weixin_47993432/article/details/126157775

边栏推荐

猜你喜欢

随机推荐