FCC参阅笔记之有趣的算法（下）

墨蓝 2022-07-14 05:47 152阅读 0赞

## 收银程序 checkCashRegister() ##

**描述：**设计一个收银程序 checkCashRegister() ，其把购买价格(price)作为第一个参数 , 付款金额 (cash)作为第二个参数, 和收银机中零钱 (cid) 作为第三个参数.

cid 是一个二维数组，存着当前可用的找零.

当收银机中的钱不够找零时返回字符串 “Insufficient Funds”. 如果正好则返回字符串 “Closed”.

否则, 返回应找回的零钱列表,且由大到小存在二维数组中.

**解题程序：**

function checkCashRegister(price, cash, cid) { 
      var balance = cash - price;
      var change = [];
      var unit = [100.00, 20.00, 10.00, 5.00, 1.00, 0.25, 0.10, 0.05, 0.01];//金额某面值的单位
      //将给出的零钱数组参数先反转，然后映射其单位
      var tempCid = cid.reverse().map(function(w,j){ 
        w.push(unit[j]);
        return w;
      });
      tempCid.forEach(function(v,i,arr){ 
        if (v[1] > 0 && balance >= v[2]) {
          if (balance >= v[1]) {
            change.push([v[0], v[1]]);
            //js减法的bug，可能会减出循环数值，在这里使用toFixed()方法处理，然后将其转为数值类型。
            //balance为当前需要找的零钱数
            balance = (balance - v[1]).toFixed(2)  - 0;  
            //当前金额单位的剩余数值
            v[1] = 0;
          } else {
          //找出当前金额单位可以找零的数值
            var tempMoney = parseInt(balance / v[2]) * v[2];
            change.push([v[0], tempMoney]);
            balance = (balance - tempMoney).toFixed(2) - 0;
            v[1] -= tempMoney;
          }  
        }
      });
      if (balance === 0) {
      //通过判断零钱数组成员的第二个值是否为零判断是否零钱数恰好为该找零的数值。
        if (tempCid.every(function(v){ return !v[1];})) {
          return 'Closed';  
        }
        //返回该找零的零钱数组
        return change;
      } else if (balance > 0) {
        return 'Insufficient Funds';
      } else {
        throw new Error('未知的错误');
      }
    }

**Note：**该题目为FCC的高级编程训练题的某一个，题目并不很难，只是要对边界条件、找零过程有一个清晰的思路。

**FCC参考链接：** 点击[这里][Link 1]

## Inventory Update ##

**描述：** 依照一个存着新进货物的二维数组，更新存着现有库存(在 arr1 中)的二维数组. 如果货物已存在则更新数量 . 如果没有对应货物则把其加入到数组中，更新最新的数量. 返回当前的库存数组，且按货物名称的字母顺序排列.

**解题程序：**

function updateInventory(arr1, arr2) { 
       var arr1key = arr1.map(function(v){ 
         return v[1];
       });
      arr2.forEach(function(v){ 
        if (arr1key.indexOf(v[1]) === -1) {
          arr1.push(v);
        } else {
          arr1[arr1key.indexOf(v[1])][0] += v[0];
        }
      });
      return arr1.sort(function(a,b){ 
        return a[1].charCodeAt(0) - b[1].charCodeAt(0);
      });
    }

**Note：**该题目也比较简单，在这里写出来，只是因为实现的思路挺好的，我们可以把第一个数组成员的第一个元素单独拎出来存储起来，然后遍历第二个数组，判断第二个数组的当前成员的第一个属性是否在我们存储的属性数组中，然后使用`indexOf()` 方法找到他的位置，则这个位置也是该成员在第一个数组中的位置。这样方便了赋值操作。

**FCC参考链接：** 点击[这里][Link 2]

## No repeats please ##

**描述：** 把一个字符串中的字符重新排列生成新的字符串(注：进行给定字符串的**全排列**)，返回新生成的字符串里没有连续重复字符的字符串个数.连续重复只以单个字符为准。例如, aab 应该返回 2 因为它总共有6中排列 (aab, aab, aba, aba, baa, baa), 但是只有两个 (aba and aba)没有连续重复的字符 (在本例中是 a).

**解题程序：**

function permAlone(str) { 
        var strArr = str.split('');//将给定字符串分割成数组
        //如果给定的字符串是一个重复的元素，例:aaa，则直接返回0
        if (strArr.every(function(v){ return v === strArr[0];})) {
            return 0;
        }
        var resultArr = [];
        var tempArr = [];
        var len = str.length;
        //得到给定字符串的全排列，使用递归实现。
        (function rec(arr){ 
            //对字符串的最后一个元素的处理
            if (arr.length === 1) {
                var resultStrArr = tempArr.concat(arr);
                //在这里判断该次的排列结果其元素是否有重复。
                var bool = resultStrArr.some(function(v, i, arr) { 
                    return v === arr[i + 1];
                });
                //如果不重复(例如：aba)，将其压入存入最终结果的数组resultArr
                if (!bool) {
                    resultArr.push(resultStrArr.join(''));
                }
                //抛出倒数第二个数组元素，方便下次循环时结果的存放
                tempArr.pop();
            } else {
                //对给定递归数组的一个深拷贝
                var arr2 = arr.slice(0);
                var len2 = arr2.length;
                for (var i = 0;i <= len2; i++) {
                    if (i < len2) {
                        //push该次循环的元素
                        tempArr.push(arr2[i]);
                        //深拷贝一个新的循环数组
                        var arr3 = arr2.slice(0);
                        //将已使用的元素从arr3中删除
                        arr3.splice(i, 1);
                        //将处理后的arr3传入rec函数，进行更深层次的递归操作
                        rec(arr3);
                    //如果该次数组已结束循环，则对其存放该次排列结果的数组进行pop操作。
                    } else {
                        tempArr.pop();
                    }
                }
            }
        })(strArr);
        //返回存入最终结果的数组的长度。
        return resultArr.length;
    }

**Note：** 感觉这道题应该是FCC高级算法编程题中最难的一个了，在网络上搜索了全排列的实现算法，对其思路不怎么理的很清楚，然而自己还是慢慢解出了这道题，感觉挺好的。这道题的难点在于对给定元素的全排列，首先要有递归实现的思路，其次在每次得到排列结果后需要对存放结果的数组进行`pop`操作，以存放下一次的循环的元素。

**FCC参考链接：** 点击[这里][Link 3]

[Link 1]: https://www.freecodecamp.cn/challenges/exact-change#
[Link 2]: https://www.freecodecamp.cn/challenges/inventory-update#
[Link 3]: https://www.freecodecamp.cn/challenges/no-repeats-please#

发表评论取消回复

表情：

评论列表（有 0 条评论，152人围观）

还没有评论，来说两句吧...

相关阅读

相关有趣的算法（七） ——快速排序改进算法

有趣的算法（七） ——快速排序改进算法目录有趣的算法（七） ——快速排序改进算法 -------------------- 本文章向大家介绍有趣的算法（七） —

你的名字/ 2024年02月22日 02:10/ 0 赞/ 49 阅读

相关 Linux/UNIX下的有趣命令

原贴:http://blog.chinaunix.net/u/20483/showart.php?id=1830554 Linux/UNIX下的有趣命令 <tabl

淩亂°似流年/ 2022年08月12日 00:08/ 0 赞/ 168 阅读

相关 FCC参阅笔记之编程知识点（上）

好玩的代码片段 1. 返回一个在min(包括min)和max(包括max)之间的随机数。 Math.floor(Math.random() (max - m

男娘i/ 2022年07月16日 03:45/ 0 赞/ 154 阅读

相关 FCC参阅笔记之有趣的算法（下）

收银程序 checkCashRegister() 描述：设计一个收银程序 checkCashRegister() ，其把购买价格(price)作为第一个参数 , 付款金额

墨蓝/ 2022年07月14日 05:47/ 0 赞/ 153 阅读

相关 FCC参阅笔记之有趣的算法（上）

有趣的算法如果给定的字符串是回文，返回`true`，反之，返回`false`。 function palindrome(str) { st

Myth丶恋晨/ 2022年07月13日 23:39/ 0 赞/ 143 阅读

相关 linux下有趣的commands

接触了这么多年的Linux，今日才知道原来linux居然也有如此funny的一面啊！！！下面就简单的介绍几条Linux下非常funny的commands。有些命令cento

浅浅的花香味﹌/ 2022年05月13日 04:06/ 0 赞/ 210 阅读

相关（有趣）获取下一天的日期

网上摘的代码，感觉有点意思，据说第二天被开除了~ / 获取下一天的日期 @return / public st

谁践踏了优雅/ 2022年04月22日 14:08/ 0 赞/ 250 阅读

相关 PHP 经典有趣的算法

原文：https://blog.csdn.net/a519395243/article/details/77942913 1、一群猴子排成一圈，按1，2，…，n依次编号。然

喜欢ヅ旅行/ 2021年12月12日 10:31/ 0 赞/ 235 阅读

相关几道有趣的算法题

　　题目：给定一个数字，得出这个数字的连续正整数之和，如给出15，得出1+2+3+4+5=4+5+6=7+8 1 public

约定不等于承诺〃/ 2021年12月05日 03:53/ 0 赞/ 274 阅读

相关有趣的数字环的算法实现

看到这么个数字环，感觉很有趣，于是就想着用算法实现此数字环。首先附图看效果，看是什么样的数字环 ![20130811092021906][]![2013081109203

爱被打了一巴掌/ 2021年11月04日 09:44/ 0 赞/ 286 阅读