scala - 使用Scala的回文

Question

我碰到了这个problem from CodeChef。问题指出以下内容:

A positive integer is called a palindrome if its representation in the decimal system is the same when read from left to right and from right to left. For a given positive integer K of not more than 1000000 digits, write the value of the smallest palindrome larger than K to output.

我可以定义一个isPalindrome方法，如下所示:

def isPalindrome(someNumber:String):Boolean = someNumber.reverse.mkString == someNumber

我面临的问题是，当整数满足isPalindrome方法时，如何从初始给定的数字开始循环并中断并返回第一个回文？另外，有没有更好(有效)的方法来编写isPalindrome方法？

在这里获得一些指导将是很棒的

Answer 1

如果您知道类似123xxx的数字，则xxx必须在321以下-那么下一个回文是123321。

或xxx在上面，则不能保留3，而下一个必须是124421。

这是一些没有保证的代码，不是很优雅，但是中间的(多个)Nines的情况有点毛茸茸(19992):

object Palindrome extends App {

def nextPalindrome (inNumber: String): String = {
  val len = inNumber.length ()
  if (len == 1 && inNumber (0) != '9') 
    "" + (inNumber.toInt + 1) else {
    val head = inNumber.substring (0, len/2)
    val tail = inNumber.reverse.substring (0, len/2)
    val h = if (head.length > 0) BigInt (head) else BigInt (0)
    val t = if (tail.length > 0) BigInt (tail) else BigInt (0)

    if (t < h) {
      if (len % 2 == 0) head + (head.reverse)
      else inNumber.substring (0, len/2 + 1) + (head.reverse)
    } else {
     if (len % 2 == 1) {
       val s2 = inNumber.substring (0, len/2 + 1) // 4=> 4
       val h2 = BigInt (s2) + 1  // 5 
       nextPalindrome (h2 + (List.fill (len/2) ('0').mkString)) // 5 + "" 
     } else {
       val h = BigInt (head) + 1
       h.toString + (h.toString.reverse)
     }
    }
  }
}

def check (in: String, expected: String) = {
  if (nextPalindrome (in) == expected) 
    println ("ok: " + in) else 
    println (" - fail: " + nextPalindrome (in) + " != " + expected + " for: " + in)
}
//
val nums = List (("12345", "12421"), // f
  ("123456", "124421"), 
  ("54321", "54345"), 
  ("654321", "654456"), 
  ("19992", "20002"),
  ("29991", "29992"),
  ("999", "1001"),
  ("31", "33"),
  ("13", "22"),
  ("9", "11"),
  ("99", "101"),
  ("131", "141"),
  ("3", "4")
)
nums.foreach (n => check (n._1, n._2))
println (nextPalindrome ("123456678901234564579898989891254392051039410809512345667890123456457989898989125439205103941080951234566789012345645798989898912543920510394108095"))

}

我想它也可以处理一百万位整数的情况。