目錄

2952. 需要添加的硬幣的最小數(shù)量

題目描述：

實(shí)現(xiàn)代碼與解析：

貪心

原理思路：

---

2952. 需要添加的硬幣的最小數(shù)量

題目描述：

????????給你一個(gè)下標(biāo)從?0?開始的整數(shù)數(shù)組?coins，表示可用的硬幣的面值，以及一個(gè)整數(shù)?target?。

如果存在某個(gè)?coins?的子序列總和為?x，那么整數(shù)?x?就是一個(gè)?可取得的金額?。

返回需要添加到數(shù)組中的?任意面值?硬幣的?最小數(shù)量?，使范圍?[1, target]?內(nèi)的每個(gè)整數(shù)都屬于?可取得的金額?。

數(shù)組的?子序列?是通過(guò)刪除原始數(shù)組的一些（可能不刪除）元素而形成的新的?非空?數(shù)組，刪除過(guò)程不會(huì)改變剩余元素的相對(duì)位置。

示例 1：

輸入：coins = [1,4,10], target = 19
輸出：2
解釋：需要添加面值為 2 和 8 的硬幣各一枚，得到硬幣數(shù)組 [1,2,4,8,10] 。
可以證明從 1 到 19 的所有整數(shù)都可由數(shù)組中的硬幣組合得到，且需要添加到數(shù)組中的硬幣數(shù)目最小為 2 。

示例 2：

輸入：coins = [1,4,10,5,7,19], target = 19
輸出：1
解釋：只需要添加一枚面值為 2 的硬幣，得到硬幣數(shù)組 [1,2,4,5,7,10,19] 。
可以證明從 1 到 19 的所有整數(shù)都可由數(shù)組中的硬幣組合得到，且需要添加到數(shù)組中的硬幣數(shù)目最小為 1 。

示例 3：

輸入：coins = [1,1,1], target = 20
輸出：3
解釋：
需要添加面值為 4 、8 和 16 的硬幣各一枚，得到硬幣數(shù)組 [1,1,1,4,8,16] 。 
可以證明從 1 到 20 的所有整數(shù)都可由數(shù)組中的硬幣組合得到，且需要添加到數(shù)組中的硬幣數(shù)目最小為 3 。

提示：

• 1 <= target <= 105
• 1 <= coins.length <= 105
• 1 <= coins[i] <= target

實(shí)現(xiàn)代碼與解析：

貪心

class Solution {public int minimumAddedCoins(int[] coins, int target) {Arrays.sort(coins);int n = coins.length;int s = 1;int i = 0;int res = 0;while (s <= target) {if (i < n && coins[i] <= s) {s += coins[i++];} else {s *= 2;res++;}}return res;}
}

原理思路：

????????假設(shè)當(dāng)前需要構(gòu)造的金額為 s，且我們已經(jīng)構(gòu)造出了 [0,...,s?1]內(nèi)的所有金額。若此時(shí)有一個(gè)新的硬幣 x，我們把它加入到數(shù)組中，可以構(gòu)造出 [x,s+x?1]內(nèi)的所有金額。

????????如果 x≤s，可以將上面兩個(gè)區(qū)間合并，得到 [0,s+x?1]內(nèi)的所有金額。
????????如果 x>s，就需要添加一個(gè)面值為 s?的硬幣，這樣可以構(gòu)造出 [0,2s?1]內(nèi)的所有金額。

????????所以，將數(shù)組 coins按照升序排序，小到大遍歷數(shù)組中的硬幣。對(duì)于每個(gè)硬幣 x，進(jìn)行和s的比對(duì)。直到大于等于target