資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++程式：計算需要新增多少個數才能構成從1到k的所有數字
假設我們有一個名為nums的數字列表和另一個值k。我們必須找到需要插入nums中的最小數字數量，以便我們可以使用nums中的某些子集構成[1, k]中的任何數字。
因此，如果輸入類似於nums = [3, 5]，k = 6，則輸出將為2，因為我們必須插入1, 2，這樣我們可以構成：1 = [1]，2 = [2]，3 = [3]，4 = [1, 3]，5 = [5]，6 = [1, 5]。
為了解決這個問題，我們將遵循以下步驟：
- 對陣列nums進行排序
- sum := 0, next := 1, ret := 0
- 對於nums中的所有i
- 當next < i時
- 如果sum >= k，則
- 退出迴圈
- sum := sum + next
- next := sum + 1
- (將ret增加1)
- 如果sum >= k，則
- 如果sum >= k，則
- 退出迴圈
- sum := sum + i
- next := sum + 1
- 當next < i時
- 當next <= k時
- sum := sum + next
- next := sum + 1
- (將ret增加1)
- 返回ret
讓我們看看下面的實現以更好地理解：
示例
#include
using namespace std;
class Solution {
public:
int solve(vector& nums, int k) {
sort(nums.begin(), nums.end());
int sum = 0;
int next = 1;
int ret = 0;
for (int i : nums) {
while (next < i) {
if (sum >= k) break;
sum += next;
next = sum + 1;
ret++;
}
if (sum >= k) break;
sum += i;
next = sum + 1;
}
while (next <= k) {
sum += next;
next = sum + 1;
ret++;
}
return ret;
}
};
int solve(vector& nums, int k) {
return (new Solution())->solve(nums, k);
}
int main(){
vector v = {3, 5};
int k = 6;
cout << solve(v, k);
}輸入
[3, 5], 6
輸出
2
更新於：2020年12月2日
61 次瀏覽
廣告