資料結構
網路
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 次瀏覽
廣告