用C ++修补数组

2024-05-14 06:30:06 411

假设我们有一个数组nums和一个数字。我们可以在数组中添加元素，以便可以由数组中某些元素的总和形成[1，n]范围内的任何数字（包括两端）。我们必须找到所需补丁的最小数量。因此，当数组类似于[1,4]且给定数字为n=7时，输出将为1，因为最初的数字为[1]，[4]和[1,4]=5，如果我们将2变成数组，则数字将为[1]，[2]，[4]，[1,2]，[1,4]，[2,4]，[1,2,4]，因此总和值分别为1、2、4、3、5、6、7。

为了解决这个问题，我们将遵循以下步骤-

req：=1，i：=0，ret：=0

当req<=n时，执行-

需求=需求+需求

增加ret1

req=req+数字[i]

使我增加1

如果i<nums和nums[i]<=req的大小，则，

除此以外

返回ret

示例

让我们看下面的实现以更好地理解-

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int minPatches(vector<int>& nums, int n) {
      long long int req = 1;
      int i = 0;
      int ret = 0;
      while(req <= n){
         if(i < nums.size() && nums[i] <= req){
            req += nums[i];
            i++;
         } else {
            req += req;
            ret++;
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,4};
   cout << (ob.minPatches(v, 7));
}

输入值

{1,4}

输出结果

用C ++修补数组

示例

输入值

热门推荐

随机推荐