LintCode 1503

找零

题目描述
某国的货币系统包含面值 1 元、4 元、16 元、64 元共 4 种硬币，以及面值 1024 元的纸币。
你现在使用 1024 元的纸币购买了一件价值为 N,0<N<=1024 元的商品，请问最少会收到多少个硬币作为找零。

扫码免费做题
↓↓↓

样例 1
样例输入1:amount = 1014样例输出1:4找零 2 个 4 元硬币，和 2 个 1 元硬币。
样例 2
样例输入2:amount = 1004样例输出2:2找零 1 个 16 元硬币，1 个 4 元硬币。
解题思路
我们可以算出要找的钱为1024−amount1024−amount，由于所有的硬币的面值两两成倍数关系，所以一定尽量每次优先用最大的面值去找零，如果最大的面值大于剩下的金额数，再用第二大的面值。利用贪心思想，从大到小进行计算。
代码思路
1. 令常量 VALUES=[64,16,4,1]VALUES=[64,16,4,1]。
2. 从大到小遍历，将 numbernumber 加上 change/valuechange/value，代表需要多少个面值 valuevalue 的硬币，changemodvaluechangemodvalue 代表用这种面值后剩下多少金额。
复杂度分析

时间复杂度：

· 只需常量次数的计算，时间复杂度为O(1)。

空间复杂度：

· 需要常量空间进行计算，空间复杂度为O(1)。
源代码
publicclassSolution {/** * @param amount: The amount you should pay. * @return: Return the minimum number of coins for change. */publicintgiveChange(int amount) { final List<Integer> VALUES = new ArrayList<Integer>(); VALUES.add(64); VALUES.add(16); VALUES.add(4); VALUES.add(1);int change = 1024 - amount;int number = 0;for (int i = 0; i < 4; i++) {intvalue = (int)VALUES.get(i); number += change / value; change %= value; }return number; }}
查看完整代码，向左滑动
点击【阅读原文】，查看领扣原题。
继续阅读
阅读原文
关键词
硬币
面值
常量
2个