数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会科学
服装研究
法律研究C++ 数组修补
假设我们有一个数组 nums 和一个数字。我们可以向该数组中添加元素，以使范围 [1, n]（两者都包括在内）内的任何数字都可以由该数组中某些元素的和形成。我们必须找到所需的最小修补数量。因此，当数组像 [1,4]，给出的数字为 n = 7 时，输出将为 1，因为最初 nums 为 [1]，[4] 和 [1,4] = 5，如果我们将 2 添加到数组中，那么 nums 将为 [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
返回 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
2020 年 5 月 27 日更新
295 次浏览
广告