每日一题(leetcode2952):添加硬币最小数量 初识贪心算法

这道题如果整体去思考，情况会比较复杂。因此我们考虑使用贪心算法。

1 我们可以假定一个X，认为[1,X-1]区间的金额都可以取到，不断去扩张X直到大于target。（这里为什么要用[1,X-1]而不是[1,X],总的来说是方便，潜在思想是1,2,4,8，....n这样下去最后能够构成的数的区间是是[1,2^(n+1)-1]）,和这里如出一辙，X就像一个桥梁，成为了一个边界）

2 我们会先将原coins数组进行从小到大排序，接着逐个去判断与X的大小关系，如果小于等于，那么那么[1,X]会扩展为[1,X+coins[index]]（index为当前数索引），那么此时可以构成的数为[1,X+coins[index]-1]（从这里可以感受到X桥梁的作用）;如果是大于，那么就需要添加一个X，那么[1,X]会扩展为[1,2X]（index为当前数索引），那么此时可以构成的数为[1,2X-1]。就这样，直到循环结束。

可以看看官方的讲解：

class Solution {
public:int minimumAddedCoins(vector<int>& coins, int target) {sort(coins.begin(),coins.end());int length=coins.size();int index=0;int res=0;int x=1;while(x<=target){if(index<length && coins[index]<=x){x+=coins[index];index++;}else{x<<=1;res++;}}return res;}
};