C++ 中的数组修补
c++server side programmingprogramming
假设我们有一个数组 nums 和一个数字。我们可以向数组中添加元素，使得 [1, n] 范围内(包含 [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 时，执行 −
如果 i < nums 的大小，且 nums[i] <= req，则
req = req + nums[i]
将 i 加 1
否则
req = req + req
将 ret 加 1
return 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}
输出
1
