scala - 使用递归的不同列表的总和

Question

我又在做 CodeWars 挑战，今天我遇到了这个问题:

让我们考虑这个例子(以通用格式编写的数组):

ls = [0, 1, 3, 6, 10]

它的以下部分:

ls = [0, 1, 3, 6, 10]
ls = [1, 3, 6, 10]
ls = [3, 6, 10]
ls = [6, 10]
ls = [10]
ls = []

相应的和是(放在一个列表中):[20, 20, 19, 16, 10, 0]

函数 parts_sums(或其在其他语言中的变体)将以列表 ls 作为参数，并返回如上定义的其各部分之和的列表。

object SumsOfParts {

  def partsSums(l: List[Int]): List[Int] = {

    var x: List[Int] = List()
    if (l.isEmpty)
      x
    else {
      x :+ l.sum
      partsSums(l.tail)
    }
  }
}

以下是测试样本:

partsSums(List(0, 1, 3, 6, 10)) should return List(20, 20, 19, 16, 10, 0) Test Failed

tail of empty list Stack Trace Completed in 4ms partsSums(List(1, 2, 3, 4, 5, 6)) should return List(21, 20, 18, 15, 11, 6, 0) Test Failed

tail of empty list Stack Trace partsSums(List(744125, 935, 407, 454, 430, 90, 144, 6710213, 889, 810, 2579358)) should return List(10037855, 9293730, 9292795, 9292388, 9291934, 9291504, 9291414, 9291270, 2581057, 2580168, 2579358, 0) Test Failed

tail of empty list Stack Trace Completed in 1ms partsSums(List(30350, 76431, 156228, 78043, 98977, 80169, 32457, 182875, 162323, 17508, 57971, 171907)) should return List(1145239, 1114889, 1038458, 882230, 804187, 705210, 625041, 592584, 409709, 247386, 229878, 171907, 0) Test Failed

Answer 1

您不应该在递归函数中使用 var 来传递状态。你可以像这样修复你的方法:

def partsSums(l: List[Int]): List[Int] = {
    if (l.isEmpty)
      Nil //to finish recursion return empty list
    else {
      l.sum :: partsSums(l.tail) //prepend newly calculated sum to list returned by recursive call
    }
}

但是这个解决方案是幼稚的，因为它在每次迭代时重新计算总和。我们可以更好地从结果的头部获取先前的总和，并通过将其添加到列表的头部来计算新的总和。我还使用另一个名为 acc 的列表来累积结果，因为这样我可以使 partsSums2 尾递归:

def partsSums2(l: List[Int], acc: List[Int] = List(0)): List[Int] = {
    if(l.isEmpty) {
      acc //at the end of recursion we return acc, which holds result
    } else {
      //acc.head is previos sum and l.head is value I want to add
      partsSums2(l.tail, (l.head + acc.head) :: acc)
    }
}

为了让它工作，我们还需要在传递给方法之前反转列表:

SumsOfParts.partsSums2(List(0, 1, 3, 6, 10).reverse)

我们需要反转列表，因为 Scala 中不可变列表的实现对前置操作(O(1))非常有影响，但对追加操作(O(n )).

最后你可以使用scanRight:

def partsSums3(l: List[Int]): List[Int] = l.scanRight(0)(_ + _)