📃 题目描述

题目链接：找零_牛客题霸_牛客网 (nowcoder.com) (opens new window)

Z国的货币系统包含面值 1 元、4元、16元、64元共计4种硬币，以及面值1024元的纸币。现在小Y使用1024元的纸币购买了一件价值为N (0 <= N <= 1024) 的商品，请问最少他会收到多少硬币？

输入描述:一行，包含一个数N。

输出描述:一行，包含一个数，表示最少收到的硬币数。

示例：

输入 200
输出 17
说明：花 200，需要找零824块，找12个64元硬币，3个16元硬币，2 个 4 元硬币即可

🔔 解题思路

用最少的硬币数拼凑出 1024 - N 元，典型的贪心算法，每次尽最大能力选择面值相对最大的硬币

import java.util.*;

public class Main {
    private static int PaperMoney = 1024;
    private static int[] coins = {64, 16, 4, 1};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        System.out.println(getMinCoinNums(PaperMoney - N));
    }

    private static int getMinCoinNums(int target) {
        // 总共硬币数
        int res = 0;
        for (int i = 0; i < coins.length; i ++) {
            while (target >= coins[i]) {
                res ++;
                target -= coins[i];
            }
        }
        return res;
    }
}

也可以这样写：

private static int func(int N) {
    int res = 0;
    while (N >= 64) {
        N -= 64;
        res ++;
    }
    while (N >= 16) {
        N -= 16;
        res ++;
    }
    while (N >= 4) {
        N -= 4;
        res ++;
    }

    // 1 元硬币
    return res + N;
}

💥 复杂度分析

• 空间复杂度：
• 时间复杂度：