有多少种硬币组合,更优解法
November 02, 2018
写在前面的自我检讨 v2
上周我发布了一篇博文有多少种硬币组合——找出独特子数组之和,是关于有多少种硬币组合的算法题的解法。虽然算法本身能够给出一个正确答案,可是仔细想来,我却没办法给出一个简单直接的解释为什么这样跑可以奏效。好的算法应该是能够以一种通俗易懂的方法教给别人的,如果连做出这道算法题的人都无法解释清楚,那即便这个算法能够跑起来,也不能算好吧。
就这个问题,一位高人给出了一个更好的解决方式,通俗易懂。听完之后,我真是不得不服功力之高深呐~
问题和复制粘贴的分析
如果你有一个硬币数组和一个代表其数量的数组,如何得到一共有多少种不同组合所得的和?
比如:硬币数组[10, 50, 100]
,和代表其数量的数组[1, 2, 1]
就表示这里一共有三种硬币,1 枚 10 分,2 枚 50 分和 1 枚 100 分硬币。那么其可能的排列组合则包括
- 10 = 10
- 50 = 50
- 100 = 100
- 10 + 50 = 60
- 10 + 100 = 110
- 50 + 50 = 100
- 50 + 100 = 150
- 10 + 50 + 50 = 110
- 10 + 50 + 100 = 160
- 50 + 50 + 100 = 200
- 10 + 50 + 50 + 100 = 210
则,不重复的值则包括加黑的部分,一共是 9 个。
接下来是正经分析
第一步:将所有硬币组成一个数组
首先,上一篇博文里的第一步和第二步是正确的,我们确实需要将所有硬币组合起来,组成一个新的数组coinList
,其中包含了所有的硬币。则这部分的代码还是继续使用。
代码如下:
/**
* Count number of
* @param {Array<Number>} coins array contains coins with different values
* @param {Array<Number>} counts array contains corresponding counts of different coins
* @returns {Number} The count of distinct sums
*/
function countDistinctSum(coins, counts) {
if (coins.length !== counts.length) {
return -1;
}
const results = {};
const coinList = [];
for (let i = 0; i < coins.length; i++) {
for (let j = 0; j < counts[i]; j++) {
coinList.push(coins[i]);
}
}
// where the beauty of algorithm shows
return Object.keys(results).length - 1; // Remove the empty 0 coin element
}
第二步:了解所有的组合是如何计算得到的
我们一步一步来看,所有的组合是如何的出来的。假如,现在我们只有一个硬币,1 分。则可能性只有 1 种,那就是[1]
。
现在我们增加一个硬币,2 分。则可能性则变成了[1, 2, 1+2]
,3 种。
如果我们再加一个硬币,3 分呢?则可能性又变成了[1, 2, 3, 1+2, 1+3,2+3,1+2+3]
,7 种。
仔细看,当硬币的数量一个一个地增加,可能的组合数量也相应地有规律地再增加。什么规律???好像看不是很清楚。那么我们换一种方法来表示呢?
如果将硬币表示为 A, B, C。
一枚硬币:A
一枚硬币的时候,是:
A
两枚硬币:A、B
两枚硬币的时候呢?那我们直接在之前的 A 后面加上一枚新的 B
A + B
除此之外,之前的 A 也应该在里面
A + B
A
再加上新增加的 B,则变成了:
A + B
A
B
三枚硬币:A、B、C
这时候加第三枚了,我们在之前的这三种情况下都加上 C,则变成了
A + B + C
A + C
B + C
而之前的那三种组合是还存在的,所以整个数组变成了
A + B + C
A + C
B + C
A + B
A
B
最后加上新增加的 C,最终得到了
A + B + C
A + C
B + C
A + B
A
B
C
这下是否更清楚了?每当一个新的硬币被加进数组之中时,组合的数量始终是之前的两倍多一个。比如:
- 1 枚硬币时,组合数量是
1
- 2 枚硬币时,组合数量是
1 * 2 + 1 = 3
- 3 枚硬币时,组合数量是
3 * 2 + 1 = 7
- 4 枚硬币时,组合数量是
7 * 2 + 1 = 15
…
以此类推
第三步:只储存非重复的值
在计算过程中,难免会遇到许多重复的值。比如两枚硬币都是 10 分的时候,计算出来的组合是[10, 10, 20]
。但其实我们不需要两个 10,而只需要[10, 20]
就可以了。这个时候我们需要用到Set
这种数据结构来储存数据。因为set
里面的元素都是非重复的。
比如,一组硬币[10, 50, 50]
。处理第一枚硬币的时候,Set
里有[10]
。
处理第二枚硬币时,对这个Set
里的所有元素提取出来并且加上新的硬币值,10 + 50
得到了60
,并添加得到的和与新添加的这枚硬币值进入进入Set
里,得到了[10, 50, 60]
.
处理第三枚硬币时,还是继续提取出这个Set
里的所有元素,并且加上新的硬币值。于是:
10 + 50 = 60
50 + 50 = 100
60 + 50 = 110
将这三个新的和加入Set
,去掉重复值之后得到了[10, 50, 60, 100, 110]
。然后再把第三枚硬币本身的值,50,也添加进去。但因为 50 已经存在了,则Set
还是[10, 50, 60, 100, 110]
。
一直重复循环到最后,我们将得到所有非重复的和。问题至此也被解决了~
大功告成
完整代码
/*
* Count number of
* @param {Array<Number>} coins array contains coins with different values
* @param {Array<Number>} counts array contains corresponding counts of different coins
* @returns {Number} The count of distinct sums
*/
function countDistinctSum(coins, counts) {
if (coins.length !== counts.length) {
return -1;
}
const coinList = [];
for (let i = 0; i < coins.length; i++) {
for (let j = 0; j < counts[i]; j++) {
coinList.push(coins[i]);
}
}
// Create a new set
const results = new Set();
for (let i = 0; i < coinList.length; i++) {
// tempSum is used to store the temporary sum of every element in the set and new coin value
const tempSum = [];
for (let it = results.values(), val = null; (val = it.next().value); ) {
tempSum.push(val + coinList[i]);
}
// add every sum in tempSum to the set and the set will do automatic duplication removal.
tempSum.forEach(n => {
results.add(n);
});
// add the new coin value into the set
results.add(coinList[i]);
}
return results.size;
}
测试:
const a = [10, 50, 100];
const b = [1, 2, 1];
console.log("Result:", countDistinctSum(a, b)); // Result: 9