太和网站开发招聘,新闻20条摘抄大全,北京电脑培训网站,想建个网站LeetCode-2952. 需要添加的硬币的最小数量【贪心 数组 排序】 题目描述#xff1a;解题思路一#xff1a;看提示主要是用贪心和排序。那我们肯定是首先对coins排序。然后依次遍历coins[i]#xff0c;获取当前可以获取金额范围#xff0c;和判断是否加入新硬币。判断规则如下… LeetCode-2952. 需要添加的硬币的最小数量【贪心 数组 排序】 题目描述解题思路一看提示主要是用贪心和排序。那我们肯定是首先对coins排序。然后依次遍历coins[i]获取当前可以获取金额范围和判断是否加入新硬币。判断规则如下解题思路二0解题思路三0 题目描述
给你一个下标从 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 105 1 coins.length 105 1 coins[i] target
解题思路一看提示主要是用贪心和排序。那我们肯定是首先对coins排序。然后依次遍历coins[i]获取当前可以获取金额范围和判断是否加入新硬币。判断规则如下
为方便描述把 0 也算作可以得到的数。
假设现在得到了区间 [0,s−1] 中的所有整数如果此时遍历到整数 xcoins[i]那么把 [0,s−1] 中的每个整数都增加 x我们就得到了区间 [x,sx−1] 中的所有整数。
此时有两个区间 [0,s−1] [x,sx−1] 那么可以分为两种情况
x s那我们可以直接得到一个新区间[0, sx-1] 中的所有整数。x s注意这里我们贪心的直接将面值为s的硬币加入coins中加一个比 s 还小的数字就没法得到更大的数不够贪直接得到区间[0,s−1] [s,2s−1]可以直接合并得到一个新区间[0, 2s−1] 中的所有整数。然后继续遍历cions[i]
class Solution:def minimumAddedCoins(self, coins: List[int], target: int) - int:coins.sort()result, s, i, 0, 1, 0while s target:if i len(coins) and coins[i] s:s coins[i]i 1else:s * 2result 1return result时间复杂度O(nlogn)排序 空间复杂度O(n)
解题思路二0 时间复杂度O(n) 空间复杂度O(n)
解题思路三0 时间复杂度O(n) 空间复杂度O(n)
