在 Scala 中找到下一个回文的更好算法

Question

这是个问题：

如果正整数在十进制系统中的表示形式在从左到右和从右到左读取时相同，则称为回文。对于不超过 1000000 位的给定正整数 K，将大于 K 的最小回文值写入输出。数字始终不带前导零。

输入：第一行包含整数 t，即测试用例的数量。整数 K 在接下来的 t 行中给出。

输出：对于每个 K，输出大于 K 的最小回文。

示例

输入：

阿拉伯数字8082133

年

输出：

8182222

年

还有我的Scala代码：

object Pro_5 {
  // find the next palindrome larger than K
  def findPalindrome(input: String) = {
    // start from (k + 1)
    val tmp = (BigInt(input) + 1).toString
    val length = tmp.length
    val mid = length / 2
    val left = tmp.substring(0, length >> 1)
    val right = tmp.substring(length >> 1, length)
    // whether continue for loop
    var flag = true
    // half of the result
    var res = ""
    for (i <- 0 until mid if flag) {
      if (left(i) > right(mid - 1)) {
        res = left
        flag = false
      } else if (left(i) < right(mid - 1)) {
        res = (BigInt(left) + 1).toString()
        flag = false
      }
    }
    if (length % 2 == 0) {
      res + res.reverse
    } else {
      res + tmp(mid) + res.reverse
    }
  }
  // get K
  def getInput(times: Int) = {
    for (time <- 0 until times) yield readLine()
  }
  def main(args: Array[String]) {
    // get compute times
    val times = readInt()
    getInput(times).map(findPalindrome(_)).foreach(println)
  }
}

我从Mark Peters的回答中学到了一些东西

但是当我在SPOJ运行它时，我仍然得到了一个time limit exceeding error.

你能帮我改进算法吗？

任何答案都将是欢迎的...

Answer 1

一个好的算法已经在Mark Peters的回答中得到了解释。

所以这只是正确实施的问题。这里有一个提示，如何改进代码，减少java并支持奇数计数

def split(s: String) = {
  val mid = (s.length + 1) / 2
  val left = s.substring(0, mid)
  val right = s.substring(s.length - mid, s.length)
  (left, right)
}
//right string should be reversed
@tailrec
def compareFromIndex(left: String, right: String, i: Int): String = {
  if (i < 0) left
  if (left(i) > right(i)) left
  else if (left(i) < right(i)) (BigInt(left) + 1).toString()
  else compareFromIndex(left, right, i - 1)
}
val half = compareFromIndex(left, right.reverse, left.length - 1)

这几乎是完整的实现:)只需正确输入拆分功能即可。并从计算出的"一半"中制作完整的回文。祝你好运！