经验分享：带你快速通过字节算法面试

字节跳动面试题： 找零

描述 某国的货币系统包含面值 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)。 源代码

public class Solution {
    /**
     * @param amount: The amount you should pay.
     * @return: Return the minimum number of coins for change.
     */
    public int giveChange(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++) {
            int value = (int)VALUES.get(i);
            number += change / value;
            change %= value;
        }
        
        return number;
    }
}