硬币找零
该问题的思路来于https://www.ideserve.co.in/learn/coin-change-problem-number-of-ways-to-make-change
假设需给顾客找零n元，目前有硬币c,d,e,f，每个硬币假设有无限多,要求判断有多少种找零方法。
该问题的解题思路是遍历判断，例如n=50，c=20，d=10，e=5，f=1时，解题思路如下
该问题的难点在于递归，因为在判断过程中会出现重复判断的情况，例如下图所示。在数字较少时不明显，但如果数字较多时这种重复的情况会严重影响时间，因此在做判断时需要对重复数据进行判断。
解决问题代码如下：
class Result {
static class AmountDenom {
int amount;
long denom;
public AmountDenom(int amount, long denom) {
this.amount = amount;
this.denom = denom;
}
// we need to override hashCode and equals method for user defined objects when these objects are used as keys
@Override
public int hashCode() {
// since this code uses jdk 7
return Objects.hash(this.amount, this.denom);
}
@Override
public boolean equals(Object obj) {
if (objinstanceof AmountDenom) {
AmountDenom keyObj = (AmountDenom) obj;
return (keyObj.amount ==this.amount && keyObj.denom ==this.denom);
}else {
return false;
}
}
}
/*
* Complete the 'getWays' function below.
*
* The function is expected to return a LONG_INTEGER.
* The function accepts following parameters:
* 1. INTEGER n
* 2. LONG_INTEGER_ARRAY c
*/
//给定数字n，从集合c中取任意数据(同一数据可取任意次)相加后等于n，判断有多少种相加方法
public static long getWays(int n, List c) {
// Write your code here
if (n >250) {
return 0;
}
if (null == c || c.isEmpty() || c.size() >50) {
return 0;
}
if (c.stream().anyMatch(i -> i >50)) {
return 0;
}
Map map =new HashMap<>();
List list = c.stream()
.sorted(Comparator.reverseOrder())
.distinct()
.collect(toList());
System.out.println(n);
System.out.println(list);
return getCoinWays(n, list, map);
}
private static long getCoinWays(int n, List list, Map map) {
if (1 == list.size()) {
int cnt =0 == n % list.get(0) ?1 :0;
map.put(new AmountDenom(n, list.get(0)), (long) cnt);
return cnt;
}
long ways =0;
int numberOfCoins =0, modifiedAmount;
long denom = list.get(0);
while (numberOfCoins * denom <= n) {
modifiedAmount = (int) (n - (numberOfCoins * denom));
if (null != map.get(new AmountDenom(modifiedAmount, list.get(1)))) {
ways = ways+ map.get(new AmountDenom(modifiedAmount, list.get(1)));
}else {
ways =ways +getCoinWays(modifiedAmount, list.subList(1, list.size()), map);
}
numberOfCoins++;
}
map.put(new AmountDenom(n, denom), ways);
return ways;
}
}
public class Solution {
public static void main(String[] args)throws IOException {
Result.AmountDenom a1 =new Result.AmountDenom(2, 1);
Result.AmountDenom a2 =new Result.AmountDenom(2, 1);
System.out.println(a1.equals(a2));
int n =179;
List c = Arrays.asList(24L, 6L, 48L, 27L, 36L, 22L, 35L, 15L, 41L, 1L, 26L, 25L, 4L, 8L, 14L, 20L, 9L, 38L, 34L, 40L, 45L, 17L, 33L, 19L, 5L, 43L, 2L);
long ways = Result.getWays(n, c);
System.out.println(ways);
}
}
