无意中看到一道平安科技2017年的面试题（根据消费者手上的钱计算使用可能的付款方式），想到几年前写过一篇博客《换零钱算法分析及代码示例》，似乎可以借鉴一下思路。先根据用户手中钱币种类计算出所有可能的换零钱方式，再根据用户持有的钱币数量判断这种付款方式是否有效。

一、面试题截图

二、解题思路

换零钱的思路是采用递归分解的思想，将某金额的钱币换成指定种类零钱的方式等价于换成必包含第一种钱币的零钱方式和必不包含第一种零钱方式的并集。详细的推导过程参看《换零钱算法分析及代码示例》，这里不详解。贴出源码：

1、钱币种类枚举定义

 1 package com.elon;
 2 
 3 /**
 4  * 钱币种类枚举定义。
 5  * 
 6  * @author elon
 7  * @version 2018年3月9日
 8  */
 9 public enum EnumMoneyType {
10     ONE_YUAN("a1", 1),
11     
12     FIVE_YUAN("a2", 5),
13     
14     TEEN_YUAN("a3", 10),
15     
16     TWENTY_YUAN("a4", 20),
17     
18     FIFTY_YUAN("a5", 50),
19     
20     HUNDRED_YUAN("a6", 100);
21     
22     /**
23      * 币值类型
24      */
25     private String type;
26     
27     /**
28      * 币值
29      */
30     private int value;
31     
32     public String getType() {
33         return type;
34     }
35 
36     public int getValue() {
37         return value;
38     }
39 
40     private EnumMoneyType(String type, int value) {
41         this.type = type;
42         this.value = value;
43     }
44 
45     public static int getValueByType(String type)
46     {
47         EnumMoneyType[] values = EnumMoneyType.values();
48         for (EnumMoneyType v : values) {
49             if (v.type.equals(type)) {
50                 return v.value;
51             }
52         }
53         
54         return 0;
55     }
56     
57     public static String getTypeByValue(int value) {
58         EnumMoneyType[] values = EnumMoneyType.values();
59         for (EnumMoneyType v : values) {
60             if (v.value == value) {
61                 return v.type;
62             }
63         }
64         
65         return "";
66     }
67 }

2、递归树子节点类型定义

 1 package com.elon;
 2 
 3 /**
 4  * 子节点类型。
 5  * 
 6  * @author elon
 7  * @version 2018年3月7日
 8  */
 9 public enum EnumChildType {
10     LEFT,    //左节点
11     RIGHT;  //右节点
12 }

3、从控制台录入条件，解析条件

 1 package com.elon;
 2 
 3 import java.io.BufferedReader;
 4 import java.io.IOException;
 5 import java.io.InputStreamReader;
 6 import java.util.ArrayList;
 7 import java.util.HashMap;
 8 import java.util.List;
 9 import java.util.Map;
10 import java.util.Map.Entry;
11 
12 public class StartService {
13     public static void main(String[] args) {
14         
15         //从控制台读入输入的n=11,a1=0,a2=0,a3=5,a4=6,a5=3,a6=2
16         BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
17         
18         try {
19             String str = reader.readLine();
20             String[] splitResults = str.split(",");
21             
22             //提取转换为Key/Value结构方便查询
23             Map<String, Integer> keyValueMap = new HashMap<>();
24             for (String pair : splitResults) {
25                 String[] pairValues = pair.split("=");
26                 keyValueMap.put(pairValues[0].trim(), Integer.parseInt(pairValues[1].trim()));
27             }
28             
29             int total = keyValueMap.get("n");
30             
31             Map<Integer, Integer> moneyMap = new HashMap<>();
32             moneyMap.put(EnumMoneyType.ONE_YUAN.getValue(), keyValueMap.get(EnumMoneyType.ONE_YUAN.getType()));
33             moneyMap.put(EnumMoneyType.FIVE_YUAN.getValue(), keyValueMap.get(EnumMoneyType.FIVE_YUAN.getType()));
34             moneyMap.put(EnumMoneyType.TEEN_YUAN.getValue(), keyValueMap.get(EnumMoneyType.TEEN_YUAN.getType()));
35             moneyMap.put(EnumMoneyType.TWENTY_YUAN.getValue(), keyValueMap.get(EnumMoneyType.TWENTY_YUAN.getType()));
36             moneyMap.put(EnumMoneyType.FIFTY_YUAN.getValue(), keyValueMap.get(EnumMoneyType.FIFTY_YUAN.getType()));
37             moneyMap.put(EnumMoneyType.HUNDRED_YUAN.getValue(), keyValueMap.get(EnumMoneyType.HUNDRED_YUAN.getType()));
38             
39             List<Map<Integer, Integer>> resultList = new PaymentCalc().calcPaymentMethod(total, moneyMap);
40             
41             List<Map<String, Integer>> resultShowList = new ArrayList<>();
42             for (Map<Integer, Integer> result : resultList) {
43                 Map<String, Integer> resultShowMap = new HashMap<>();
44                 for (Entry<Integer, Integer> entry : result.entrySet()) {
45                     resultShowMap.put(EnumMoneyType.getTypeByValue(entry.getKey()), entry.getValue());
46                 }
47                 
48                 resultShowList.add(resultShowMap);
49             }
50             
51             System.out.println(resultShowList);
52             
53         } catch (IOException e) {
54             e.printStackTrace();
55         }
56         
57     }
58 }

4、计算及打印可能的付款组合方式

  1 package com.elon;
  2 
  3 import java.util.ArrayList;
  4 import java.util.Collections;
  5 import java.util.HashMap;
  6 import java.util.List;
  7 import java.util.Map;
  8 import java.util.Map.Entry;
  9 import java.util.Stack;
 10 
 11 /**
 12  * 计算支付方式。
 13  * 
 14  * @author elon
 15  * @version 2018年3月5日
 16  */
 17 public class PaymentCalc {
 18     
 19     /**
 20      * 计算支持的付款方式。
 21      * 
 22      * @param totalMoney 总付款金额.
 23      * @param moneyMap 持有的钱币信息 .Map<币值分类, 数量>
 24      * @return 付款方式。List<Map<币值分类, 数量>>
 25      */
 26     public List<Map<Integer, Integer>> calcPaymentMethod(int totalMoney, Map<Integer, Integer> moneyMap){
 27         
 28         List<List<Integer>> payList = new ArrayList<List<Integer>>();
 29         List<Integer> currencyTypeList = new ArrayList<>();
 30         currencyTypeList.addAll(moneyMap.keySet());
 31         Collections.sort(currencyTypeList);
 32         
 33         payList = calcPayMethodByCurrency(totalMoney, currencyTypeList);
 34         return judgePayNum(payList, moneyMap);
 35     }
 36     
 37     /**
 38      * 根据币种计算所有可能的支付方式。
 39      * 
 40      * @param totalMoney 总金额
 41      * @param currencyList 币种列表
 42      * @return 支持的支付方式
 43      */
 44     private List<List<Integer>> calcPayMethodByCurrency(int totalMoney, List<Integer> currencyList){
 45         
 46         List<List<Integer>> payList = new ArrayList<List<Integer>>();
 47         
 48         //计算右子树
 49         Stack<Integer> payMethod = new Stack<>();
 50         payList.addAll(calcChildPayMethod(totalMoney - currencyList.get(0) , currencyList, payMethod, 
 51                 EnumChildType.RIGHT));
 52         
 53         //计算左子树
 54         List<Integer> leftCurrencyTypeList = new ArrayList<>();
 55         leftCurrencyTypeList.addAll(currencyList);
 56         leftCurrencyTypeList.remove(0);
 57         payList.addAll(calcChildPayMethod(totalMoney, leftCurrencyTypeList, new Stack<Integer>(), 
 58                 EnumChildType.LEFT));
 59         
 60         return payList;
 61     }
 62 
 63     /**
 64      * 递归计算子树节点。这个函数中没一步操作,入栈、出栈，判断处理的顺序都很重。
 65      * 
 66      * @param totalMoney 总金额
 67      * @param currencyList 币种数量列表
 68      * @param payMethod 支付方式列表
 69      * @param lOrR 当前处理的是左子树还是右子树
 70      * @return 支付方式列表
 71      */
 72     private List<List<Integer>> calcChildPayMethod(int totalMoney, List<Integer> currencyList,
 73             Stack<Integer> payMethod, EnumChildType lOrR) {
 74 
 75         List<List<Integer>> payList = new ArrayList<List<Integer>>();
 76 
 77         if (lOrR == EnumChildType.RIGHT && !currencyList.isEmpty()) {
 78             payMethod.push(currencyList.get(0));
 79         }
 80 
 81         if (totalMoney == 0) {
 82             List<Integer> payCopy = new ArrayList<>();
 83             payCopy.addAll(payMethod);
 84             payList.add(payCopy);
 85             return payList;
 86         }
 87 
 88         if (totalMoney < 0 || currencyList.isEmpty()) {
 89             return payList;
 90         }
 91 
 92         List<Integer> moneyTypeListLeft = new ArrayList<>();
 93         moneyTypeListLeft.addAll(currencyList);
 94         moneyTypeListLeft.remove(0);
 95         
 96         //递归处理右子树
 97         payList.addAll(calcChildPayMethod(totalMoney - currencyList.get(0), currencyList, payMethod, 
 98                 EnumChildType.RIGHT));
 99 
100         //由于上一步是最后处理右子树，且currencyList不为空，有入栈操作。执行完后需要 先出栈在处理左子树。
101         payMethod.pop();
102 
103         //递归处理左子树
104         payList.addAll(calcChildPayMethod(totalMoney, moneyTypeListLeft, payMethod, EnumChildType.LEFT));
105 
106         return payList;
107     }
108     
109     /**
110      * 根据手上持有的货币判断实际能支持哪些付费方式。
111      * 
112      * @param payList
113      *            按币种计算所有可能的付费方式
114      * @param moneyMap
115      *            持久的货币信息
116      * @return 实际支持的支付方式
117      */
118     private List<Map<Integer, Integer>> judgePayNum(List<List<Integer>> payList, Map<Integer, Integer> moneyMap) {
119 
120         List<Map<Integer, Integer>> fitPayMap = new ArrayList<>();
121         List<Map<Integer, Integer>> allPayMap = new ArrayList<>();
122 
123         for (List<Integer> pay : payList) {
124 
125             Map<Integer, Integer> onePayMap = new HashMap<>();
126             for (int money : pay) {
127                 if (!onePayMap.containsKey(money)) {
128                     onePayMap.put(money, 0);
129                 }
130 
131                 onePayMap.put(money, onePayMap.get(money) + 1);
132             }
133 
134             allPayMap.add(onePayMap);
135         }
136 
137         for (Map<Integer, Integer> payMap : allPayMap) {
138             for (Entry<Integer, Integer> entry : payMap.entrySet()) {
139                 if (!moneyMap.containsKey(entry.getKey()) || moneyMap.get(entry.getKey()) < entry.getValue()) {
140                     continue;
141                 }
142             }
143 
144             fitPayMap.add(payMap);
145         }
146 
147         return fitPayMap;
148     }
149 }

JAVA学习网

分类