硬幣找零
該問題的思路來于https://www.ideserve.co.in/learn/coin-change-problem-number-of-ways-to-make-change
假設(shè)需給顧客找零n元，目前有硬幣c,d,e,f，每個(gè)硬幣假設(shè)有無限多,要求判斷有多少種找零方法狐粱。
該問題的解題思路是遍歷判斷，例如n=50，c=20诸衔，d=10着绷，e=5，f=1時(shí)储矩，解題思路如下
該問題的難點(diǎn)在于遞歸感耙，因?yàn)樵谂袛噙^程中會(huì)出現(xiàn)重復(fù)判斷的情況，例如下圖所示持隧。在數(shù)字較少時(shí)不明顯即硼，但如果數(shù)字較多時(shí)這種重復(fù)的情況會(huì)嚴(yán)重影響時(shí)間，因此在做判斷時(shí)需要對(duì)重復(fù)數(shù)據(jù)進(jìn)行判斷屡拨。
解決問題代碼如下：
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
*/
? ? //給定數(shù)字n只酥，從集合c中取任意數(shù)據(jù)(同一數(shù)據(jù)可取任意次)相加后等于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);
? ? }
}
