题解-需要添加的硬币的最小数量-最大化在缺口处补硬币的作用

, , , 评论

Problem: 100153. 需要添加的硬币的最小数量

思路

  • 这题和LeetCode-1798. 你能构造出连续值的最大数目很像,很经典的想法
  • 是子序列所以先排序
  • 先考虑我们手里的硬币能构造出来多少
  • 假设我们手里的硬币足够我们构造出来[0,x),接下来我们又拿到了一个硬币,数值为y,
    • 如果我们把y放进之前的所有序列之中,会发现我们能够构造[y,x+y)
    • 再加上刚才的区间,我们手里的硬币加y之后能构造的数的范围为
    • 如果y<=x则我们能够构造的数就能达到[0,x+y)
    • 如果y>x则会有一段空缺
  • 为了填补这段空缺,我们应该往里面放另一块硬币,假设为z,根据上面的推论,我们很容易得到z会生成的片段为[z,x+z),而且z的取值范围应该为[y-x,x],为了让填补有效,且最大化填补的内容,应该让z=x,因为这样能最大化填补的空缺
    • 取最大更有可能单次填补完空缺
  • 而我们遇到的问题只是将y换成了target,所有遇到的大于当前x的也认为是y即可

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def minimumAddedCoins(self, coins: List[int], target: int) -> int:
        coins.sort()
        res=0
        canMake=0 #能生成的范围是[0,canMake]
        i=0
        while i<(len(coins)):
            val=coins[i]
            if val<=canMake+1:
                canMake+=val
                i+=1
            else:
                res+=1 #这里补的硬币就是canMake+1
                canMake+=canMake+1
        while canMake<target:
            res+=1
            canMake+=canMake+1
        return res

Noirking's Pawn

个人简介。