时间戳

首页 > 解决方案 > 如何有效地删除 Scala 中的 var

scala - 如何有效地删除 Scala 中的 var

问题描述

我正在尝试解决问题https://www.geeksforgeeks.org/connect-n-ropes-minimum-cost/

解决方案

def minCost(arr: Array[Int]):Int = {

  val minHeap = scala.collection.mutable.PriorityQueue.empty[Int].reverse
    
  arr.foreach{ ele =>
    minHeap += ele
  }
    
  var sum =0
    
  while(minHeap.size >1){
    
    val first = minHeap.dequeue()
    val second = minHeap.dequeue()
    
    val length = second + first//3+3 =6+9
    sum = sum + (first +second)//3+6+9
    
    minHeap.enqueue(length)
  }
    
  sum
}

我想摆脱while循环和var. 任何人都可以提出更好的解决方案吗？

在下面尝试

val res =minHeap.foldLeft(0){
  (x,y)=>
    val sum =x+y
    minHeap.enqueue(sum)
    sum
}

println(res)
res

标签： scalafunctional-programmingpriority-queuevar

解决方案

如果您只想删除var并且while仍然使用可变的PriorityQueue （老实说这是一个很好的折衷方案，并且可能是在实际代码中最好的做法），您可以只使用尾递归方法。

type Ropes = List[Int]

def connectRopes(ropes: Ropes): Int = {
  val queue = PriorityQueue.from(ropes).reverse
  
  @annotation.tailrec
  def loop(remaining: Int, acc: Int): Int = {
    if (remaining == 0) acc
    else if (remaining == 1) acc
    else {
      val rope1 = queue.dequeue()
      val rope2 = queue.dequeue()
      val newRope = rope1 + rope2
      queue.addOne(newRope)
      loop(remaining - 1, acc + newRope)
    }
  }
  
  loop(remaining = queue.size, acc = 0)
}

但是，如果你想编写一个完全不可变的解决方案只是为了习惯使用不可变的数据结构，你可以这样做：

def connectRopesFullImmutable(ropes: Ropes): Int = {
  @annotation.tailrec
  def loop(remaining: Ropes, acc: Int): Int =
    remaining match {
      case Nil =>
        acc
      
      case _ :: Nil =>
        acc
      
      case rope1 :: rope2 :: Nil =>
        rope1 + rope2 + acc
      
      case rope1 :: rope2 :: tail =>
        @annotation.tailrec
        def findTwoMin(remaining: Ropes, min1: Int, min2: Int, acc: Ropes): (Int, Int, Ropes) =
          remaining match {
            case rope :: tail =>
              if (rope < min1) findTwoMin(remaining = tail, min1 = rope, min2 = min1, min2:: acc)
              else if (rope < min2) findTwoMin(remaining = tail, min1, min2 = rope, min2 :: acc)
              else findTwoMin(remaining = tail, min1, min2, rope :: acc)
            
            case Nil =>
              (min1, min2, acc)
          }
      
        val (min1, min2, ropes) =
          if (rope1 < rope2) findTwoMin(remaining = tail, min1 = rope1, min2 = rope2, acc = List.empty)
          else findTwoMin(remaining = tail, min1 = rope2, min2 = rope1, acc = List.empty)
        val newRope = min1 + min2
        loop(remaining = newRope :: ropes, acc + newRope)
    }
  
  loop(remaining = ropes, acc = 0)
}

回答评论，问题的空间复杂度是(AFAIK) O(1)，因为该算法是尾递归函数，我们不消耗堆栈，我们只操作相同的列表，所以我们也不消耗堆。
时间复杂度为O(N^2)，因为我们在外循环内部有一个内循环，这意味着该算法非常低效。

我们可能会尝试通过保持剩余绳索列表始终排序来对其进行一些优化；如下所示。哪个应该使用O(N log(N))，但仍然需要大量样板文件和低效率，只是为了不使用可变优先级队列。

def connectRopesFullImmutableOptimized(ropes: Ropes): Int = {
  @annotation.tailrec
  def loop(remaining: Ropes, acc: Int): Int =
    remaining match {
      case rope1 :: rope2 :: tail =>
        val newRope = rope1 + rope2
      
        @annotation.tailrec
        def insertSorted(remaining: Ropes, acc: Ropes): Ropes =
          remaining match {
            case rope :: ropes =>
              if (newRope > rope) insertSorted(remaining = ropes, rope :: acc)
              else acc reverse_::: (newRope :: rope :: ropes)
            
            case Nil =>
              (newRope :: acc).reverse
          }
      
        loop(remaining = insertSorted(remaining = tail, acc = List.empty), acc + newRope)
      
      case _ =>
        acc
    }
  
  loop(remaining = ropes.sorted, acc = 0)
}

您可以看到在Scastie中运行的代码。

推荐阅读