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

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 和 return 其各部分之和的列表，如上定义。

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

正如@Andrey 评论的那样，scanLeft 解决了这个问题，但这是一个递归的解决方案：


  def partsSums(l: List[Int]): List[Int] = {
    if (l.isEmpty) {
      Nil
    } else {

      def go(list: List[Int], acc: List[Int], currentSum: Int): List[Int] =

        list match {
          case Nil => (0 :: acc).reverse
          case x :: xs =>
            go(xs, currentSum :: acc, currentSum - x)
        }

      go(l, Nil, l.sum)
    }
  }

  def main(args: Array[String]): Unit = {
    println(partsSums(List(0, 1, 3, 6, 10)))
    // List(20, 20, 19, 16, 10, 0)
    println(partsSums(List(1, 2, 3, 4, 5, 6)))
    // List(21, 20, 18, 15, 11, 6, 0)
    println(partsSums(List(744125, 935, 407, 454, 430, 90, 144, 6710213, 889, 810, 2579358)))
    // List(10037855, 9293730, 9292795, 9292388, 9291934, 9291504, 9291414, 9291270, 2581057, 2580168, 2579358, 0)
    println(partsSums(List(30350, 76431, 156228, 78043, 98977, 80169, 32457, 182875, 162323, 17508, 57971, 171907)))
   // List(1145239, 1114889, 1038458, 882230, 804187, 705210, 625041, 592584, 409709, 247386, 229878, 171907, 0)
  }

Answer 2

您不应在递归函数中使用 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 tail-recursive:

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)(_ + _)

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

Sums of different lists using recursion

int

recursion

functional-programming

scala

list