每日一题(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;
    }
};