class Solution {
public:
int minimumAddedCoins(vector<int>& coins, int target) {
}
};
100153. 需要添加的硬币的最小数量
给你一个下标从 0 开始的整数数组 coins，表示可用的硬币的面值，以及一个整数 target 。
如果存在某个 coins 的子序列总和为 x，那么整数 x 就是一个 可取得的金额 。
返回需要添加到数组中的 任意面值 硬币的 最小数量 ，使范围 [1, target] 内的每个整数都属于 可取得的金额 。
数组的 子序列 是通过删除原始数组的一些（可能不删除）元素而形成的新的 非空 数组，删除过程不会改变剩余元素的相对位置。
示例 1：
输入：coins = [1,4,10], target = 19 输出：2 解释：需要添加面值为 2 和 8 的硬币各一枚，得到硬币数组 [1,2,4,8,10] 。 可以证明从 1 到 19 的所有整数都可由数组中的硬币组合得到，且需要添加到数组中的硬币数目最小为 2 。
示例 2：
输入：coins = [1,4,10,5,7,19], target = 19 输出：1 解释：只需要添加一枚面值为 2 的硬币，得到硬币数组 [1,2,4,5,7,10,19] 。 可以证明从 1 到 19 的所有整数都可由数组中的硬币组合得到，且需要添加到数组中的硬币数目最小为 1 。
示例 3：
输入：coins = [1,1,1], target = 20 输出：3 解释： 需要添加面值为 4 、8 和 16 的硬币各一枚，得到硬币数组 [1,1,1,4,8,16] 。 可以证明从 1 到 20 的所有整数都可由数组中的硬币组合得到，且需要添加到数组中的硬币数目最小为 3 。
提示：
1 <= target <= 1051 <= coins.length <= 1051 <= coins[i] <= target原站题解
javascript 解法, 执行用时: 179 ms, 内存消耗: 61.6 MB, 提交时间: 2024-03-30 23:45:24
/**
* @param {number[]} coins
* @param {number} target
* @return {number}
*/
var minimumAddedCoins = function(coins, target) {
coins.sort((a, b) => a - b);
let ans = 0, s = 1, i = 0;
while (s <= target) {
if (i < coins.length && coins[i] <= s) {
s += coins[i++];
} else {
s *= 2; // 必须添加 s
ans++;
}
}
return ans;
};
rust 解法, 执行用时: 20 ms, 内存消耗: 3 MB, 提交时间: 2024-03-30 23:44:58
impl Solution {
pub fn minimum_added_coins(mut coins: Vec<i32>, target: i32) -> i32 {
coins.sort_unstable();
let mut ans = 0;
let mut s = 1;
let mut i = 0;
while s <= target {
if i < coins.len() && coins[i] <= s {
s += coins[i];
i += 1;
} else {
s *= 2; // 必须添加 s
ans += 1;
}
}
ans
}
}
golang 解法, 执行用时: 104 ms, 内存消耗: 8.7 MB, 提交时间: 2023-12-03 22:50:36
// 分类讨论
func minimumAddedCoins(coins []int, target int) (ans int) {
slices.Sort(coins)
s, i := 1, 0
for s <= target {
if i < len(coins) && coins[i] <= s {
s += coins[i]
i++
} else {
s *= 2 // 必须添加 s
ans++
}
}
return
}
cpp 解法, 执行用时: 156 ms, 内存消耗: 75.1 MB, 提交时间: 2023-12-03 22:50:51
class Solution {
public:
int minimumAddedCoins(vector<int> &coins, int target) {
sort(coins.begin(), coins.end());
int ans = 0, s = 1, i = 0;
while (s <= target) {
if (i < coins.size() && coins[i] <= s) {
s += coins[i];
i++;
} else {
s *= 2; // 必须添加 s
ans++;
}
}
return ans;
}
};
java 解法, 执行用时: 23 ms, 内存消耗: 58.1 MB, 提交时间: 2023-12-03 22:51:04
class Solution {
public int minimumAddedCoins(int[] coins, int target) {
Arrays.sort(coins);
int ans = 0, s = 1, i = 0;
while (s <= target) {
if (i < coins.length && coins[i] <= s) {
s += coins[i];
i++;
} else {
s *= 2; // 必须添加 s
ans++;
}
}
return ans;
}
}
python3 解法, 执行用时: 128 ms, 内存消耗: 26.9 MB, 提交时间: 2023-12-03 22:51:20
class Solution:
def minimumAddedCoins(self, coins: List[int], target: int) -> int:
coins.sort()
ans, s, i = 0, 1, 0
while s <= target:
if i < len(coins) and coins[i] <= s:
s += coins[i]
i += 1
else:
s *= 2 # 必须添加 s
ans += 1
return ans