网站链接: element-ui dtcms
当前位置: 首页 > 技术博文  > 技术博文

leetcode 330. 按要求补齐数组 【贪心构造】

2021/4/2 22:43:26 人评论

思路参考:https://leetcode-cn.com/problems/patching-array/solution/an-yao-qiu-bu-qi-shu-zu-tan-xin-suan-fa-b4bwr/ 当前集合可以覆盖[1,b],在当前集合上增加一个数字,使得这个区间可以覆盖到的数组最多,并且保证区间没有产生…

思路参考:https://leetcode-cn.com/problems/patching-array/solution/an-yao-qiu-bu-qi-shu-zu-tan-xin-suan-fa-b4bwr/

当前集合可以覆盖[1,b],在当前集合上增加一个数字,使得这个区间可以覆盖到的数组最多,并且保证区间没有产生空隙

#define debug(x) cout<<#x<<": "<<(x)<<endl;

using ll = long long;

class Solution {
public:
    int minPatches(vector<int>& a, int n) {
        ll r = 0;
        int ret = 0;
        int i = 0;
        while(r < n){
            if(i<a.size() && r+1 >= a[i]){
                r += a[i];
                i++;
            }
            else { //r+1 < a[i])
                ret ++;
                r += (r+1);
            } 
        }
        
        return ret;
    }
};

在这里插入图片描述

相关资讯

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?