数据结构
网络
关系数据库管理系统 (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 次浏览
广告