程序计算在C ++中应追加多少个数字以创建从1到k的所有数字
假设我们有一个称为nums的数字列表,另一个值为k。我们必须找到需要插入到num中的最小数量的数字,以便我们可以使用num中的某些子集从[1,k]中得出任何数字。
因此,如果输入类似于nums=[3,5],k=6,则输出将为2,因为我们必须插入1、2,所以我们可以使:1=[1],2=[2],3=[3],4=[1、3],5=[5],6=[1、5]。
为了解决这个问题,我们将遵循以下步骤-
对数组数字进行排序
sum:=0,下一个:=1,ret:=0
对于我所有的数字
从循环中出来
如果总和>=k,则:
总和:=总和+下一个
下一个:=sum+1
(增加ret1)
从循环中出来
而下一个<i,请执行:
如果总和>=k,则:
和:=和+i
下一个:=sum+1
而下一个<=k,请执行以下操作:
总和:=总和+下一个
下一个:=sum+1
(增加ret1)
返回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