本文主要是介绍Leetcode 2952. Minimum Number of Coins to be Added，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
- Leetcode 2952. Minimum Number of Coins to be Added
- 1. 解题思路
- 2. 代码实现
- 题目链接：2952. Minimum Number of Coins to be Added
1. 解题思路
这一题思路上就是一个贪婪算法的思路，偏数学性多一点。
首先，我们将面值有序排列，然后依次考察每
一个面值 x x x，假设此时可以遍历到的最大值为 k k k：
- 如果 x ≤ k + 1 x \leq k+1 x≤k+1，那么我们可以直接加入这个面值，此时我们可以遍历到的最大值更新为 k + x k+x k+x；
- 如果 x > k + 1 x > k+1 x>k+1，那么中间一定会出现缺口，此时我们需要不断地迭代增加面值为 k + 1 k+1 k+1的币值，直到新的 k k k值满足 x ≤ k + 1 x \leq k+1 x≤k+1，此时又回到了第一种情况当中。
最后，当所有面值的硬币都是用完成后，我们要做的就是重复上述步骤2中的过程，直至 k k k值超过目标值。
2. 代码实现
给出python代码实现如下：
class Solution:def minimumAddedCoins(self, coins: List[int], target: int) -> int:coins = sorted(coins)bound = 0ans = 0for coin in coins:while coin > bound+1:ans += 1bound = bound * 2 + 1bound += coinwhile bound < target:ans += 1bound = bound * 2 + 1return ans
提交代码评测得到：耗时623ms，占用内存30.3MB。
这篇关于Leetcode 2952. Minimum Number of Coins to be Added的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
