网站开发怎么收费,游戏系统网站开发说明书,南京的网站建设公司,磁器口网站建设这道题如果整体去思考#xff0c;情况会比较复杂。因此我们考虑使用贪心算法。
1 我们可以假定一个X#xff0c;认为[1,X-1]区间的金额都可以取到#xff0c;不断去扩张X直到大于target。#xff08;这里为什么要用[1,X-1]而不是[1,X],总的来说是方便#xff0c;潜在思想…
这道题如果整体去思考情况会比较复杂。因此我们考虑使用贪心算法。
1 我们可以假定一个X认为[1,X-1]区间的金额都可以取到不断去扩张X直到大于target。这里为什么要用[1,X-1]而不是[1,X],总的来说是方便潜在思想是1,2,4,8....n这样下去最后能够构成的数的区间是是[1,2^(n1)-1],和这里如出一辙X就像一个桥梁成为了一个边界
2 我们会先将原coins数组进行从小到大排序接着逐个去判断与X的大小关系如果小于等于那么那么[1,X]会扩展为[1,Xcoins[index]]index为当前数索引那么此时可以构成的数为[1,Xcoins[index]-1]从这里可以感受到X桥梁的作用;如果是大于那么就需要添加一个X那么[1,X]会扩展为[1,2X]index为当前数索引那么此时可以构成的数为[1,2X-1]。就这样直到循环结束。
可以看看官方的讲解 class Solution {
public:int minimumAddedCoins(vectorint coins, int target) {sort(coins.begin(),coins.end());int lengthcoins.size();int index0;int res0;int x1;while(xtarget){if(indexlength coins[index]x){xcoins[index];index;}else{x1;res;}}return res;}
};
