scala - Codility TapeEquilibrium Scala

Question

我使用 Scala 编写了 Codility 上 TapeEquilibrium 问题的解决方案。我已经尝试了许多不同负载的测试输入，当我使用 Codility Develipment 环境和 eclipse 运行结果时，我得到了正确的答案。然而，当我提交结果时，它几乎在每次测试中都失败了，答案是错误的。我无法掌握确切的输入，但我用随机数生成了类似大小的输入，并且这些输入始终有效。我已经查看了我的逻辑一段时间，但无法弄清楚我做错了什么。有人能帮我吗。

测试可以找到here

这是我的代码

import org.scalacheck.Gen
import org.scalacheck._

object Problem1 extends App {

  def solution( A: Array[ Int ] ): Int = {
    var sumRight = A.foldLeft( 0 )( _ + _ )
    var sumLeft = 0;
    def absDiffer( a: Int, b: Int ) = if ( a < b ) b - a else a - b

    def minimizer( ar: List[ Int ], prevDiff: Int, sumL: Int, sumR: Int ): Int = {
      val diff = absDiffer( sumL, sumR )
      if ( diff <= prevDiff )
        minimizer( ar.tail, diff, ar.head + sumL, sumR - ar.head )
      else
        prevDiff
    }
    minimizer( A.toList, absDiffer( A.head, sumRight - A.head ), A.head, sumRight - A.head )
  }
  def randomInput( length: Int ) = {
    Gen.listOfN( length, Gen.oneOf( Range( -1000, 1000 ) ) ).sample.get
  }
  def randomPosInput( length: Int ) = {
    Gen.listOfN( length, Gen.oneOf( Range( 1, 100 ) ) ).sample.get
  }
  def randomNegInput( length: Int ) = {
    Gen.listOfN( length, Gen.oneOf( Range( -1000, -1 ) ) ).sample.get
  }

  val ar = randomPosInput( 100000 )
  val inputString = ar.mkString( "[", ", ", "]" )
  val clipboard = java.awt.Toolkit.getDefaultToolkit().getSystemClipboard()
  val sel = new java.awt.datatransfer.StringSelection( inputString )
  clipboard.setContents( sel, sel )
  println( inputString )
  println( solution( ar.toArray ) )
}

Answer 1

我不是 Scala 开发人员，但我认为您过早地结束了递归——

if ( diff <= prevDiff )
    minimizer( ar.tail, diff, ar.head + sumL, sumR - ar.head )
else
    prevDiff

我相信这应该是:

if ( diff <= prevDiff )
    minimizer( ar.tail, diff, ar.head + sumL, sumR - ar.head )
else
    minimizer( ar.tail, prevDiff, ar.head + sumL, sumR - ar.head )

最后需要选择总体最小差异。

不确定这是否有帮助，但这是我在 JS 中一起破解的解决方案(Codility 上的 100/100):

function solution(A) {
    var total, forward, test, best;
    total = 0;
    for (var i = 0; i < A.length; i++) {
        total += A[i];
    }
    forward = A[0];
    best = Math.abs(total - 2*forward);
    for (i = 1; i < A.length-1; i++) {
        forward += A[i];
        test = Math.abs(total - 2*forward);
        if (test < best) {
            best = test;
        }
    }
    return best;
}