2017-08-22

FreeCodeCamp 高级算法题 - 计算找零

计算找零 (Exact Change)

题目链接

问题解释

这个 function 接收三个参数，price 为购买总价，cash 为付款金额，cid 为收银机中可用的零钱。返回值为应找回的零钱列表
需要注意的是，cid 中，每个子数组的第一个元素代表面值，第二个元素代表这个面值的总额。比如 ["TEN", 30.00] 就表示十元纸币共有 30 元，即三张
如果 price 为 19.50，cash 为 20.00，cid 为 [["PENNY", 1.01], ["NICKEL", 2.05], ["DIME", 3.10], ["QUARTER", 4.25], ["ONE", 90.00], ["FIVE", 55.00], ["TEN", 20.00], ["TWENTY", 60.00], ["ONE HUNDRED", 100.00]]，则返回值应为 [["QUARTER", 0.50]]
注意，这道题的基本解法虽然可以通过 FCC 的测试，但明显是有漏洞的

解题思路

可能有些朋友不知道美元的硬币面值，"PENNY" 代表一分，"NICKEL" 代表五分，"DIME" 代表一角，"QUARTER" 代表二十五分 (两毛五)
首先，计算出找零金额不难，直接用 cash 减去 price 就可以了
根据 cid，我们可以很明确地知道零钱的总额。如果这个总额小于应找金额则应返回 "Insufficient Funds"，如果这个总额等于应找金额则应返回 "Closed"。这两个条件我们可以在一开始判断，如果符合即可直接返回，不需要进行任何其他的计算
可以回想一下罗马数字转换器那道题。在那道题中，我们的思路就是先写一个可用字母代表的数字组成的数组，然后从数组中最大的数开始与给定的数字比较，只要是小于等于原数字，就减去匹配到的数字，得到的结果继续进行匹配。尽管还涉及一些特殊情况，但整体思路是这样
这道题同理，我们先生成一个零钱面值数组，然后对应找金额进行迭代就可以了
比如说，应找金额为 23.5 元
- 显然我们是不需要 100 元的。我们需要先凑出来二十。如果我们有 20 元，就应该直接给一张。如果没有，那就应该继续找，看有没有两张十块。以此类推。这一步完成后再去凑剩下的三块五
- 对于三块五，我们要先凑三块钱出来。显然我们是不需要 5 元的。只需要看看有没有三张 1 元。如果没有，就要继续找，看看硬币的 Quarter 够不够，以此类推
- 最后再凑五角，显然我们应该从 Quarter 开始试，两个 Quarter 就可以。如果没有，就看看有没有五个 Dime，以此类推
显然，如果计算到中间的步骤，比如五角这一步。就算前面都可以满足，但这时候发现任何一个面值都没法付清五角，那就表示我们没法付清找零，因此就应该直接跳出，返回 "Insufficient Funds"

注意事项 - 关于浮点数

在绝大部分计算机语言中，小数都是允许使用的，JavaScript 也不例外。只是限于 IEEE 754 标准，很多语言处理浮点数会出现问题。比如 JavaScript 中很经典的 0.1 + 0.2 === 0.3 返回 false。这个不是 JavaScript 语言本身的问题，而是浮点数需要以二进制形式存储。
内部的原理，大致上是这样。比如 0.1，首先它等于 1/10，但 10 并不是一个二进制数。对于 1/10，我们需要用二进制数来无限接近它，1/8 显然不可能，因为它已经比 1/10 大了。那我们可以表示为：
1
0.1 = 1/10 = 1/16 + (1/10 - 1/16)
计算 1/10 - 1/16，我们得到 0.0375。进而可以表示为：
1
0.0375 = 1/32 + (0.0375 - 1/32)
然后继续运算。这样就可以得到一个无限趋近于 0.1 的表示方式。这也就是计算精度丢失的根本来源
这是我们无法避免的，换语言也不能避免。常用的处理方式有两种
1. 把需要计算的数字转换成整数，也就是乘以 10 的 n 次方。计算后再除回来。这样做相对保险
2. 将计算结果保留到一定精度，然后与保留前的值求差。显然，如果计算结果 “正确”，那这个差应该是 0。然后，将这个差值与一个很小的数字比较，如果差值小于这个很小的数字，那就表示我们可以直接使用保留后的结果
第一种方式很好理解。比如我们要计算 0.1 + 0.2，那我们就先把他们都乘以 10 来计算 1 + 2，得到 3，结果再除以 10 就可以得到 0.3
对于第二种方式，可能有些人会问，那我们怎么知道这个 “很小的数字” 是多少？理论上来说这取决于实际的精度要求。但事实上，JavaScript 已经为我们内置了这个很小的数，叫 Number.EPSILON。请移步到这里查看：文档
虽然这个是 ES6 中才有的，但这个数本身就是一个常数，我们自己定义就没问题了。而且 MDN 页面上也给出了 Polyfill 的方案
有兴趣的朋友可以试试实现以上两种思路，其实代码都非常简单

那么，之所以提到这件事儿，是因为在这道题目中，我们需要处理小数。由于这道题的场景是计算交易金额/找零，那么我们可以认为，小数点后最多只可能有两位

因此，我们就都把所有的过程，按照单位为 分 去处理就可以了。比如，一元我们用 100 表示，”Quarter” 我们就用 25 表示。这样会在很大的程度上简化代码和计算

只是别忘了，输出的结果还是要以 元 为单位，那么我们在生成最终结果的时候，或者生成的过程中转换一下就好了

基本解法 (警告：虽然可以通过 FCC 测试，但解法本身存在漏洞)

思路提示

按照上面的思路，我们再来考虑一些实现中的细节问题。上面已经说了，建议在这道题中，把所有涉及到钱的计算都乘以 100 来处理
我们需要先构建关于面值和名称的参考数组。与罗马数字转换器类似，在那道题中我们构建了一个用于存储每个罗马字符代表的阿拉伯数字的 numArr，以及一个用于存储所有罗马字符的 strArr。这两个数组可以通过索引来建立联系。对于这道题，同理，我们可以建立一个面值名称的数组，和每一个面值代表的钱数的数组，同样用索引来建立联系。就像这样：

1
2
3

// 注意，这里给每种面值都乘了 100
var denomination = [1, 5, 10, 25, 100, 500, 1000, 2000, 10000];
var denominationName = ['PENNY', 'NICKEL', 'DIME', 'QUARTER', 'ONE', 'TEN', 'TWENTY', 'ONE HUNDRED'];

可能有些朋友会问，既然需要建立一一对应的关系，为什么不像这样，使用对象呢？

var denominationObj = {
    PENNY: 1,
    NICKEL: 5,
    DIME: 10,
    QUARTER: 25,
    // ....
}

由于对象本身是无序的 (至少，我们不应该认为它是有序的)，我们在用 for...in 遍历对象的时候也就无法保证实际遍历的顺序。这样说虽然不够确切，因为默认会按照定义时候的顺序来遍历。但不同浏览器内核对 for...in 的实现也不尽相同，因此我们无法保证顺序一定是我们最开始定义的，详情请参考底下的链接。所以，不建议使用
对于这道题来说，由于我们希望的是从最大的 10000 也就是一百元开始尝试，然后尝试二十元，十元，五元，以此类推。因此，这里我还是建议使用两个数组去定义
遍历的过程大概是这样。假如，目前需要找零 43.30 元：
- 可以不用试一百元了
- 二十元这里要分情况讨论了：
  - 如果我们能找到两张二十元，就可以添加到结果数组，并在应找零钱中减去 40。也就是用 3.30 继续做后面的步骤
  - 如果我们有一张二十元，也可以添加到结果数组，并在应找零钱中减去 20。也就是用 23.30 继续做后面的步骤
  - 如果我们没有二十元，那就继续用 43.30 继续做后面的步骤
- 十元这里讨论如下：
  - 如果上一步找到了两张二十元，那这一步就不用试十元了
  - 如果上一步只有一张二十元，那我们要看能不能找到两张十元
  - 如果上一步没有二十元，那我们就要看能不能找到四张十元
- 以此类推……
不难得出一个结论：如果某个面值合适，并且数量大于 0，那我们就把合适的数量添加到结果数组，并在应找零钱中减去当前的 面值 * 数量，用于下次计算
这就是一开始说的，这道题的核心思路就是基于一个数字的迭代。在罗马数字转换器中，我们基于传入的阿拉伯数字迭代。那么在这道题中，其实就是在迭代我们根据传入的实际参数计算出来的应找零钱
如果看到这里你还是没想清楚代码该如何写，建议你从头再看一遍思路分析，或者想想罗马数字那道题的思路。看起来内容好像很多，但我觉得这个思路还是比较容易理解的

参考链接

代码

function checkCashRegister(price, cash, cid) {
    // 计算应找金额
    var change = cash * 100 - price * 100;
    // 面值数组
    var denoNum = [1, 5, 10, 25, 100, 500, 1000, 2000, 10000];
    // 面值名称数组，遍历的过程中添加
    var denoStr = [];
    // 零钱柜中可用找零总额
    var total = 0;
    // 零钱柜中面值名称与可用额度的 map
    var counterMap = {};
    // 结果数组
    var output = [];

    // 遍历 cid，更新上面定义的数组，对象
    for (var i = 0; i < cid.length; i++) {
        var temp = cid[i][1] * 100;
        denoStr.push(cid[i][0]);
        counterMap[cid[i][0]] = Math.round(temp);
        total += Math.round(temp);
    }

    // 边界条件
    if (change > total) {
        return 'Insufficient Funds';
    }
    if (change === total) {
        return 'Closed';
    }

    for (var i = denoNum.length - 1; i >= 0; i--) {
        // 找出需要试的金额，条件为比 change 小
        // 注意这里是从右开始遍历
        if (denoNum[i] <= change) {
            // 计算当前面值需要的总额
            var currentTotal = change - change % denoNum[i];

            if (counterMap[denoStr[i]] < currentTotal && counterMap[denoStr[i]] > 0) {
                // 处理柜台中当前面值的总额不为 0，但不够的情况
                output.push([denoStr[i], counterMap[denoStr[i]] / 100]);
                change -= counterMap[denoStr[i]];
            } else if (counterMap[denoStr[i]] >= currentTotal) {
                // 处理柜台中当前面值的总额够用的情况
                output.push([denoStr[i], currentTotal / 100]);
                change -= currentTotal;
            }
        }
        // 只要 change 为 0，就可以返回结果数组了
        if (change === 0) {
            return output;
        }
    }
    // 执行到这里表示无法凑出应找金额
    return "Insufficient Funds";
}

解释

计算应找金额，一定要先把两个数都乘以 100，否则可能需要在求差之后 Math.round 一下
然后定义一些后续会用到的变量。denoNum 直接通过 literal 形式定义，代表所有的面值。与之对应的是 denoStr，代表面值的名称。这两个数组通过 index 关联 (顺便说一句，”面值” 这个词英文叫 denomination，这里缩写为 deno)
遍历 cid 的过程中其实完成了三件事。将 cid 中每个子数组的第一个元素添加到 denoStr，生成面值名称与可用额度的对应关系 counterMap，以及计算出零钱柜中可用的总额 total
第二个遍历 denoNum 可能看起来会很复杂。我们来分析一下，注意这个遍历从右边开始：
- 如果当前 denoNum[i] 比 change 大，那我们就可以跳过这个 denoNum[i]，寻找下一个值。举例来说，为了凑 30 的找零，我们不可能需要一百元
- currentTotal 是一个临时变量。它的意义是，对于 change，假如我们要用 denoNum[i] 来凑，那么需要 currentTotal 这么多的钱。比如，当 change = 70，denoNum[i] = 20 时，currentTotal 就是 60，意思是三张二十元。这里写成 Math.floor(change / denoNum[i]) * denoNum[i] 也是一个效果
- 然后我们需要比较 currentTotal 与零钱柜中当前面值的可用金额，即 counterMap[denoStr[i]]
  - 如果可用金额比 currentTotal 大，那我们可以直接用 currentTotal / 100 作为输出，面值当然就是 denoStr[i]。因此把这两个值，合并成数组，push 到结果数组中
  - 如果可用金额比 currentTotal 小，就要进一步讨论可用金额是否为 0
    - 如果为 0，那我们就不该添加到结果数组，继续下一次判断就可以了
    - 如果不为 0，那我们就应该用当前的可用金额作为输出，即 counterMap[denoStr[i]] / 100
- 只要在 output 中添加了找零金额，那我们就应该把这个添加的金额从 change 中减掉，然后继续下一次循环
- 只要 change 为 0 了，那就表示我们已经完成了找零的计算，可以返回 output 了
- 如果遍历结束，change 依然不为 0，那我们就可以认为是 "Insufficient Funds" 的情况

漏洞与优化

上面的这个思路实现起来不难，理解起来也相对容易。尽管可以通过测试，但漏洞也是很明显的
问题主要出在循环结束判断 "Insufficient Funds" 那里，我们先来回想一下计算过程。计算找零的时候，总会先匹配可用的最大值。比如对于 0.30 元，会首先尝试 Quarter，这是有道理的，因为我们总不希望找给顾客三十个一分硬币
换个角度想想，如果我们需要找零 0.30 元，而我们手里有三个 Dime (一角) 和一个 Quarter (两毛五)。那么按照这个思路，会先匹配一个 Quarter，然后继续往下找 Nickel (五分)。如果我们手里没有五分，那么就会返回 "Insufficient Funds"，这样其实是不确切的。显然，我们也可以匹配三个 Dime
可能会有朋友说，那我们从最小开始匹配不就行了？也不尽然，如果遇到 0.40 元，而我们有一个 Nickel (五分)，三个 Dime (一角) 和一个 Quarter (两毛五)，就算不出来了
因此我们需要一种 “尝试” 机制。意思是，当一条路走不通的时候，我们要回到可能出错的点，然后换一条路继续尝试。这样的处理，在算法中成为回溯 (backtrack)
另一点，我能想到的优化就是能否算出 “最优解”。比如，我们需要找零 0.30 元，手里有五个 Penny (一分)，三个 Dime (一角) 和一个 Quarter (两毛五)。按照现在的算法，我们会得到一个 Quarter 与五个 Penny 的结果。事实上，三个 Dime 才是我们想要的结果。在现实生活中，我们也会给出三个 Dime，而不是前者
处理这个问题也不会很简单，尽管按照上面提到的回溯法也是可以解决的，但回溯法本身时间复杂度就比较高。从算法 (面试) 角度来说，这应该会是一个动态规划 (Dynamic Programming，简称 DP) 思路的应用场景
限于篇幅，就不在这篇中过多展开了，学有余力的朋友们可以去了解一下。我打算先更新完高级算法题所有题目的思路和解法，如果有空，再回来更新这道题目的优化思路和解法

本文标题:FreeCodeCamp 高级算法题 - 计算找零

文章作者:S1ngS1ng

发布时间:2017年08月22日 - 23时50分

最后更新:2017年09月01日 - 23时19分

原始链接:S1ngS1ng.github.io/blog/fcc/advanced-exact-change/

许可协议: "署名-非商用-相同方式共享 3.0" 转载请保留原文链接及作者。