1

对于 CodeWars 上的这个 Kata Level 6 问题，9 个测试中有8个通过了。奇怪的事情：CodeWars 不会告诉我哪个测试用例失败了。

这是我的代码。也许这里有人可以帮忙？太感谢了。

function tickets(peopleInLine) {
  var totalChange = 0;
  for (var i = 0; i < peopleInLine.length; i++) {
    if (peopleInLine[i] === 25) totalChange += 25;
    if (peopleInLine[i] > 25) {
      var change = peopleInLine[i] - 25;
      if (totalChange < change) return "NO";
      if (totalChange >= change) totalChange -= change;      
    }
  }
  return "YES";
}

这是问题：

新的“复仇者联盟”电影刚刚上映！电影院售票处有很多人排着长队。他们每个人都有一张 100、50 或 25 美元的钞票。“复仇者联盟”的门票价格为 25 美元。

Vasya 目前是一名文员。他想把一张票卖给这条线上的每个人。

如果 Vasya 最初没有钱并严格按照人们排队的顺序出售门票，Vasya 是否可以向每个人出售一张票并给他找零？

返回YES，如果 Vasya 可以向每个人出售一张票并给零钱。否则返回NO。

例子：

tickets([25, 25, 50]) // => YES 
tickets([25, 100]) // => NO. Vasya will not have enough money to give change to 100 dollars
4

2 回答 2

3

您需要计算您拥有的每张钞票：如果有人给您 100，您不能只用一张 100 的钞票给他 75。tickets([25,25,25, 100,100])应该返回"NO" 这是一个天真的解决方案，

function tickets(peopleInLine) {
  //var totalChange = 0; not needed
  var total25bill = 0;
  var total50bill = 0;
  var total100bill = 0;
  for (var i = 0; i < peopleInLine.length; i++) {
    //totalChange += peopleInLine[i]
    if (peopleInLine[i] === 25) {
        total25bill += 1;
    } else if (peopleInLine[i] === 50) {
        if (total25bill >= 1) {
            total25bill =-1; //gives back 1 25$ bill 
            total50bill += 1;
        } else {
            return "NO";
        }
    } else if (peopleInLine[i] === 100) {
        if ((total50bill >= 1) && (total25bill >= 1)){
            total25bill =-1; //gives back 1 25$ bill 
            total50bill =-1; //gives back 1 50$ bill 
            total100bill += 1;
        } else if (total25bill >= 3){
            total25bill =-3; //gives back 3 25$ bill 
            total100bill += 1;
        } else {
            return "NO";
        }
    }
  }
  return "YES";
}
于 2016-05-30T18:17:28.680 回答
2

Walle 指出，您必须跟踪每笔账单。下面是一个递归定义，它有 3 个状态变量 、a和b，c一个用于跟踪每种账单类型。

function isEmpty(xs) { return xs.length === 0; }
function first(xs) { return xs[0]; }
function rest(xs) { return xs.slice(1); }

function tickets(xs) {
  function loop(a,b,c,xs) {
    // validate drawer, a=$25, b=$50, c=$100
    if (a < 0 || b < 0 || c < 0)
      return "NO";

    // if the drawer is valid and the line of people is empty...
    else if (isEmpty(xs))
      return "YES";

    // otherwise, process the next person in line
    else
      switch (first(xs)) {
        case 25:                                
          return loop(a+1, b,   c, rest(xs)); // give back $0
        case 50:
          return loop(a-1, b+1, c, rest(xs)); // give back $25
        case 100:
          return b > 0                          // if drawer has a $50..
            ? loop(a-1, b-1, c+1, rest(xs))     // give back $25 + $50 
            : loop(a-3, b,   c+1, rest(xs))     // give back 3 * $25
          ;
      }
  }
  // start the loop with 0 of each bill in the drawer
  return loop(0,0,0,xs);
}

我喜欢这个函数，因为没有重复的逻辑，并且循环中的每个分支只有一个合理的返回值。

我也喜欢案例分析看起来像是每种账单类型的交易。

// in the case of someone paying with a $50
// give 1 a
// gain 1 b
// c stays the same
return loop(a-1, b+1, c, rest(xs))

这些状态变化使得推理程序的行为变得非常容易。

最简单的情况，1 人 25 美元

tickets([25])
=> 'YES'

1 人 50 美元。没有零钱给他:(

tickets([50])
//=> 'NO'

1 人 100 美元。这个人也没有变化

tickets([100])
//=> 'NO'

2人，先用$25。第二个拥有 50 美元的人将获得 25 美元的零钱

tickets([25,50])
//=> 'YES'

3人。首先是 25 美元。第二个人得到第一个人的 25 美元找零。我们不能为抽屉里只有 50 美元的第三人找零。

tickets([25,50,100])
//=> 'NO'

与上述情况相同，但在我们处理 100 美元的账单之前需要额外支付 25 美元。这次我们有足够的变化。

tickets([25,50,25,100])
//=> 'YES'

如果 3x 25 美元出现在 100 美元钞票之前，它也会起作用，因为 3* 25 美元（75 美元）是 100 美元的有效找零。

tickets([25,25,25,100])
//=> 'YES'
于 2016-05-30T21:16:13.120 回答