Palindromes使用Scala

Question

我从CodeChef遇到了这个问题.问题表明如下:

如果正整数在从左到右和从右到左读取时在十进制系统中的表示相同,则称为回文.对于给定的正整数K不超过1000000个数字,写入大于K的最小回文值输出.

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

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

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

在这里获得一些指导会很棒

Answer 1

如果你有一个像123xxx这样的数字,你知道xxx必须低于321 - 那么下一个palindrom是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"))

}

我想它也会处理一百万位Int的情况.

Answer 2

倒退不是最好的主意。最好从字符串的开头和结尾开始，然后逐元素进行迭代和比较。即使在第一个和最后一个元素不匹配的情况下，您也要浪费时间复制整个String并反转它。在具有一百万个数字的东西上，这将是巨大的浪费。

对于较大的数字，这比反向速度快几个数量级：

def isPalindrome2(someNumber:String):Boolean = {
  val len = someNumber.length;
  for(i <- 0 until len/2) {
    if(someNumber(i) != someNumber(len-i-1)) return false; 
  }
  return true;
}

基于镜像字符串的前半部分，甚至可能有一个更快的方法。我看看我现在能否得到...

更新因此，这应该在几乎恒定的时间内找到下一个回文。没有循环。我只是将其刮掉了，所以我确定它可以清除。

def nextPalindrome(someNumber:String):String = {
  val len = someNumber.length;
  if(len==1) return "11";
  val half = scala.math.floor(len/2).toInt;
  var firstHalf = someNumber.substring(0,half);
  var secondHalf = if(len % 2 == 1) {
    someNumber.substring(half+1,len);
  } else {
    someNumber.substring(half,len);
  }

  if(BigInt(secondHalf) > BigInt(firstHalf.reverse)) {
    if(len % 2 == 1) {
      firstHalf += someNumber.substring(half, half+1);
      firstHalf = (BigInt(firstHalf)+1).toString;
      firstHalf + firstHalf.substring(0,firstHalf.length-1).reverse
    } else {
      firstHalf = (BigInt(firstHalf)+1).toString;
      firstHalf + firstHalf.reverse;
    }
  } else {
    if(len % 2 == 1) {
      firstHalf + someNumber.substring(half,half+1) + firstHalf.reverse;
    } else {
      firstHalf + firstHalf.reverse;
    }
  }
}