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

Question

问题是:

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

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

输出:对于每一个K，输出大于K的最小回文。例子

输入:

2808第2133章

输出:

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 那里学到了一些东西 's answer

但是当我在 SPOJ 中运行它时，我仍然遇到 time limit exceeding error.

你能帮我改进算法吗？

欢迎任何回答...

Answer 1

确实在Mark Peters's answer中已经解释了一个好的算法

所以这只是正确实现的问题。这里有一个提示如何改进代码，使其更少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)

这几乎是完整的实现 :) 只需将正确的输入传递给 split 函数。并从计算出的“一半”中做出完整的回文。祝你好运!