找零
# 📃 题目描述
题目链接:找零_牛客题霸_牛客网 (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;
}
# 💥 复杂度分析
- 空间复杂度:
- 时间复杂度:
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10