#疯狂游戏# 提前批研发岗笔试AK代码

两道编程题一道问答题

编程题1：

给定无限量的[1,4,5]硬币和目标值

求最少硬币数，并输出此时使用的各项硬币数量，若硬币数相同，优先输出面额大的组合

如输入目标值21

输出 0, 4, 1 而不是 1, 0, 4 (即优先选择4、4、4、4、5，而不是5、5、5、5、1)

public class Main {
    static List<List<Integer>> res = new LinkedList<>();
    static LinkedList<Integer> track = new LinkedList<>();
    static int curSum = 0;
    static int minCount = Integer.MAX_VALUE;

    public static void main(String[] args) {
        //优先选择面额大的，提高回溯剪枝命中率
        int[] coins = new int[]{5, 4, 1};
        
        Scanner sc = new Scanner(System.in);
        int target = sc.nextInt();
        
        backTrack(coins, target, 0);
        
        Collections.sort(res, (a, b)->{
            StringBuilder A = new StringBuilder();
            StringBuilder B = new StringBuilder();
            for (Integer num : a) {
                A.append(num);
            }
            for (Integer num : b) {
                B.append(num);
            }

            return A.toString().compareTo(B.toString());
        });
        
        List<Integer> list = res.get(res.size() - 1);
        int one = 0, four = 0, five = 0;
        for (Integer o : list) {
            if(o == 1) one++;
            if (o == 4) four++;
            if (o == 5) five++;
        }

        System.out.println(one + "," + four + "," + five);
    }

    private static void backTrack(int[] coins, int target, int start) {

        if(curSum == target && track.size() <= minCount){
            if(track.size() < minCount){
                res.clear();
            }

            minCount = Math.min(minCount, track.size());

            LinkedList<Integer> temp = new LinkedList(track);
            Collections.sort(temp, (a, b)->{
                return a - b;
            });

            res.add(temp);
            return;
        }

        for (int i = start; i < 3; i++) {
            if(curSum + coins[i] > target) continue;
            if(track.size() > minCount) break;

            curSum += coins[i];
            track.add(coins[i]);
            
            //元素可复选
            backTrack(coins, target, i);

            track.removeLast();
            curSum -= coins[i];
        }
    }
}

编程题2：

给定若干钞票和目标金额，求所有能凑出目标金额的不重复组合

优先输出钞票数量少的组合，若钞票数量相同，则优先输出面额小的组合，如优先输出1,4而不是2,3

如输入：1,2,3,4,5;5
输出：5;1,4;2,3

public class Main {
    static List<List<Integer>> res = new LinkedList<>();
    static LinkedList<Integer> track = new LinkedList<>();
    static int curSum = 0;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        String[] split = s.split("[,;]");
        int n = split.length;

        Integer[] money = new Integer[n - 1];
        int target = Integer.parseInt(split[n - 1]);

        for (int i = 0; i < n - 1; i++) {
            money[i] = Integer.parseInt(split[i]);
        }
        Arrays.sort(money, (a, b)->{
            return b - a;
        });

        backTrack(money, target, 0);

        Collections.sort(res, (a, b)->{
            if (a.size() == b.size()){
                StringBuilder A = new StringBuilder();
                StringBuilder B = new StringBuilder();
                for (Integer num : a) {
                    A.append(num);
                }
                for (Integer num : b) {
                    B.append(num);
                }

                return A.toString().compareTo(B.toString());

            }else return a.size() - b.size();
        });

        StringBuilder sb = new StringBuilder();
        for (List<Integer> re : res) {
            for (Integer num : re) {
                sb.append(num).append(",");
            }
            sb.deleteCharAt(sb.length() - 1);
            sb.append(";");
        }
        sb.deleteCharAt(sb.length() - 1);

        System.out.println(sb.toString());
    }

    private static void backTrack(Integer[] money, int target, int start) {

        if(curSum == target){
            LinkedList<Integer> temp = new LinkedList<>(track);
            Collections.sort(temp, (a, b)->{
                return a - b;
            });
            res.add(temp);
            return;
        }

        for (int i = start; i < money.length; i++) {
            //避免重复答案
            if(i > start && money[i] == money[i - 1]) continue;

            if(money[i] + curSum > target) continue;

            curSum += money[i];
            track.add(money[i]);

            backTrack(money, target, i + 1);

            track.removeLast();
            curSum -= money[i];
        }
    }
}

#疯狂游戏##秋招#