教育类的网站案例,屏蔽 wordpress 插件,福州网站提升排名,成都网站开发公司哪家好LeetCode
需要添加的硬币的最小数量
题目链接#xff1a;2952. 需要添加的硬币的最小数量 - 力扣#xff08;LeetCode#xff09;
题目描述
给你一个下标从 0 开始的整数数组 coins#xff0c;表示可用的硬币的面值#xff0c;以及一个整数 target 。
如果存在某个 c…LeetCode
需要添加的硬币的最小数量
题目链接2952. 需要添加的硬币的最小数量 - 力扣LeetCode
题目描述
给你一个下标从 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
思路 大佬题解 2952. 需要添加的硬币的最小数量 - 力扣LeetCode 代码
C
class Solution {
public:int minimumAddedCoins(vectorint coins, int target) {ranges::sort(coins);int ans 0;int s 1;int i 0;while(s target){if(i coins.size() coins[i] s){s coins[i];} else{s * 2;ans;}}return ans;}
};Java
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];} else{s * 2;ans;}}return ans;}
}
