使用Scala编写回文数

Question

我遇到了这个CodeChef上的问题。问题陈述如下：

正整数如果在十进制下从左往右读和从右往左读相同，则称其为回文数。给定一个不超过1000000位的正整数K，编写代码输出大于K的最小回文数。

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

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

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

在这里获得一些指导将会很好。

- sc_ray

Answer 1

如果有一个数像123xxx，你会知道，要么xxx必须小于321 - 那么下一个回文数是123321。

或者xxx是大于它，那么3不能保留，而124421就必须是下一个回文数。

这里有一些不保证的代码，不是很优雅，但在中间有（多个）九的情况比较棘手（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"))

}

我猜它也可以处理一百万位数的整型。

- user unknown

---

是的，那正是我所想的。 - Eve Freeman

有一种情况会导致此方法失败：check("999", "1001")。 - incrop

你的测试用例中缺少一个逗号，位于“29992”）之后。虽然这只是一个字符，但对于复制粘贴来说并不好处理。我无法编辑它。在我看来，使用大整数并不是必要的，因为这将会花费很多时间，而且使用字符串可以轻松实现必要的功能。 - Christopher Chiche

在您的解释中，我不同意 12400421必须是接下来的一个，它应该是 124421，没有必要包含一些零。 - Christopher Chiche

@ChrisJamesC：你说得对，那只是解释上的一个错误。代码针对 nextPalindrome ("123456") => res301: String = 124421 的输出结果是符合预期的。我已经更正了文本，加了逗号，谢谢。 - user unknown

Answer 2

反转字符串不是最好的方法。最好从字符串的开头和结尾开始迭代并逐个比较元素。即使在第一个和最后一个元素不匹配的情况下，您也会浪费时间复制整个字符串并将其反转。对于有数百万位数字的内容，这将是巨大的浪费。

对于更大的数字，这比反转几个数量级要快得多：

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;
    }
  }
}

- Eve Freeman

---

谢谢。我知道一定有更好的方法来获取回文。 - sc_ray

发布了一个改进的算法。 - Eve Freeman

жИСиЃ§дЄЇ nextPalindrome("5") еЇФиѓ•жШѓ "6"пЉМиАМ nextPalindrome("121") еЇФиѓ•жШѓ "131"гАВеЊИжК±ж≠ЙжИСжЬЙзВєйЪЊжРЮ :) - incrop

是的，那可能是真的。 :) - Eve Freeman

如果失败快速，这会快几个数量级。对于回文，它仍然检查整个列表，这是*O(n)*。 - Dan Burton

这是真的。如果您通过逐个增加1（就像他所做的那样）进行处理，那么大多数情况下很快就会失败。 - Eve Freeman

Answer 3

这是我能够实现的最通用和清晰的解决方案：
编辑：去掉了 BigInt，现在计算百万位数只需要不到一秒钟。

def incStr(num: String) = {  // helper method to increment number as String
  val idx = num.lastIndexWhere('9'!=, num.length-1)
  num.take(idx) + (num.charAt(idx)+1).toChar + "0"*(num.length-idx-1)
}

def palindromeAfter(num: String) = {
  val lengthIsOdd = num.length % 2 
  val halfLength  = num.length / 2 + lengthIsOdd
  val leftHalf  = num.take(halfLength)               // first half of number (including central digit)
  val rightHalf = num.drop(halfLength - lengthIsOdd) // second half of number (also including central digit)      

  val (newLeftHalf, newLengthIsOdd) =  // we need to calculate first half of new palindrome and whether it's length is odd or even
    if (rightHalf.compareTo(leftHalf.reverse) < 0) // simplest case - input number is like 123xxx and xxx < 321
      (leftHalf, lengthIsOdd) 
    else if (leftHalf forall ('9'==))              // special case - if number is like '999...', then next palindrome will be like '10...01' and one digit longer
      ("1" + "0" * (halfLength - lengthIsOdd), 1 - lengthIsOdd)
    else                                           // other cases - increment first half of input number before making palindrome
      (incStr(leftHalf), lengthIsOdd)

  // now we can create palindrome itself
  newLeftHalf + newLeftHalf.dropRight(newLengthIsOdd).reverse
}   

- incrop

---

@incorp - 感谢您的回复，但我注意到对于palindromeAfter("1422")，我得到的是1551，而不是1441。在您的逻辑中，如果leftHalf < rightHalf，则将leftHalf增加1，我不确定这是否是我们应该做的。 - sc_ray

哦，谢谢。当然，在比较之前我应该反转左半部分（如@user unknown所提议的），而不是右半部分。已经修复了。 - incrop

非常抱歉以如此零碎的方式并且有这么长时间的延迟提供代码审查。在您的incStr函数中，对于像9、99、999等数字会失败。它会抛出一个StringIndexOutOfBoundsException异常。 - sc_ray

我注意到当您有所有的9时，您没有调用该方法，但我只是想指出incStr并不完全是动词中最纯粹的增量。 - sc_ray

是的，我记得它不能处理所有输入（对于负值也会返回错误结果）。 我本可以在行内进行这些计算，但认为这样不太易读，因此将它们移到了单独的帮助方法中。 名称“incrementStringAsIntegerWhenItsNotAllNines”更好地描述了该方法的行为，但它太长了 :) - incrop

Answer 4

使用切片检查任何类型的列表是否是回文，无需任何循环

def palindrome[T](list: List[T]): Boolean = {
if(list.length==1 || list.length==0 ){
  false
}else {
  val leftSlice: List[T] = list.slice(0, list.length / 2)
  var rightSlice :List[T]=Nil
  if (list.length % 2 != 0) {
    rightSlice = list.slice(list.length / 2 + 1, list.length).reverse
  } else {
    rightSlice = list.slice(list.length / 2, list.length).reverse
  }
  leftSlice ==rightSlice
}

}

尽管最简单的解决方案是：

     def palindrome[T](list: List[T]): Boolean = {
      list == list.reverse
      }

- Abhishek Galoda

Answer 5

根据您的“无范围”提议：使用Stream实现相同的功能：

def isPalindrome(n:Int):Boolean = n.toString.reverse == n.toString
def ints(n: Int): Stream[Int] = Stream.cons(n, ints(n+1))
val result = ints(100).find(isPalindrome)

而且使用迭代器（和不同的调用方法，实际上你可以使用Stream做同样的事情）：

val result = Iterator.from(100).find(isPalindrome)

但正如@user unknown所述，这是直接暴力破解，在处理大量数据时并不实用。

- om-nom-nom

---

我不认为对于一个包含100位数字甚至百万位数字的问题来说，这是一个实用的方法。 - user unknown

@om-nom-nom - 很好！只是出于好奇，这些方法的执行顺序是什么？find() 方法是否对每个生成的数字都执行一次？此外，Stream 是否会将所有已评估的数字存储在内存中？ - sc_ray

@sc_ray Stream 是一种惰性集合（它缓存其所有使用情况）：当您创建 Stream 时，您只有头部（尾部评估被延迟）。但是，如果您调用严格方法（例如 find），它将逐个进行评估（所有已检查的数字都将存储在内存中），直到找到第一个匹配项。如果您不想使用缓存，则可以考虑查看 Iterator。 - om-nom-nom

@om-nom-nom 谢谢！在处理大数时，哪种方法会出现问题，是迭代器方法还是在isPalindrome方法中反转字符串？由于迭代器只维护当前状态，我不认为它会失败，但isPalindrome方法中肯定存在效率低下的问题。 - sc_ray

@sc_ray 哦天啊，我误解了你的问题，我的方法更容易出错，对于大数字肯定会失败，你最好接受userunknown或Wes的答案。 - om-nom-nom

Answer 6

您可以在集合上简单地使用find方法来查找与给定谓词匹配的第一个元素：

  def isPalindrome(n:Int):Boolean = n.toString.reverse == n.toString
  val (start, end) = (100, 1000)
  val result: Option[Int] = (start to end).find(isPalindrome)
  result foreach println

  >Some(101)

- Eric

---

谢谢。如果我不想指定一个范围，而是从“start”开始迭代一个无限流的数字，并在获得第一个回文数时退出迭代，该怎么办？ - sc_ray

另外，Option[Int]返回类型是什么意思？ - sc_ray

算了，我已经知道 Option[Int] 的作用了，它返回满足谓词条件的第一个 Int 类型的值。如果在范围内没有任何数字满足谓词条件，则返回“None”。我是 Scala 新手，所以问题有点幼稚。 - sc_ray

@sc_ray 如果你仍然对选项有兴趣，可以在这里查看：[https://dev59.com/EWkw5IYBdhLWcg3ws873#9698507] - om-nom-nom

我认为对于一百位数甚至一百万位数的数字，这并不是一个实用的方法。 - user unknown

Answer 7

验证一个字符串是否为回文的解决方案

这个解决方案不会翻转字符串。但是我不确定它是否会更快。

def isPalindrome(s:String):Boolean = { 
  s.isEmpty ||   
  ((s.last == s.head) && isPalindrome(s.tail.dropRight(1)))
}

查找给定字符串的下一个回文数的解决方案

这个解决方案对于Scala来说不是最好的（与Java解决方案相似），但它只涉及字符串，适用于大数字

您只需要镜像您想要的数字的前半部分，检查它是否比起始数字高，否则，增加第一半的最后一位数字并再次镜像。

首先，一个将int的字符串表示增加1的函数：

def incrementString(s:String):String = {
  if(s.nonEmpty){
    if (s.last == '9')
      incrementString(s.dropRight(1))+'0'
    else
      s.dropRight(1) + (s.last.toInt +1).toChar
  }else
    "1"
}

然后，需要一个比较整数字符串表示的函数：（函数“compare”对于这种情况不起作用）

/* is less that 0 if x<y, is more than 0 if x<y, is equal to 0 if x==y */
def compareInts(x:String, y:String):Int = {
  if (x.length !=y.length)
    (x.length).compare(y.length)
  else
    x.compare(y)
}

现在是计算下一个回文数的函数：

def nextPalindrome(origin_ :String):String = {
  /*Comment if you want to have a strictly bigger number, even if you already have a palindrome as input */
  val origin = origin_
  /* Uncomment if you want to have a strictly bigger number, even if you already have a palindrome as input */
  //val origin = incrementString(origin_)

  val length = origin.length
  if(length % 2 == 0){
    val (first, last) = origin.splitAt(length/2); 
    val reversed = first.reverse
    if (compareInts(reversed,last) > -1)
      first ++ reversed
    else{
      val firstIncr = incrementString(first)
      firstIncr ++ firstIncr.reverse
    }
  } else {
    val (first,last) = origin.splitAt((length+1)/2)
    val reversed = first.dropRight(1).reverse
    if (compareInts(reversed,last) != -1)
      first ++ reversed
    else{
      val firstIncr = incrementString(first)
      firstIncr ++ firstIncr.dropRight(1).reverse
    }
  }
}

- Christopher Chiche

---

我做了很多测试用例都失败了：

• 失败：999 != 1001，输入为：999
• 失败：11 != 22，输入为：13
• 失败：9 != 11，输入为：9
• 失败：99 != 101，输入为：99
• 失败：131 != 141，输入为：131
• 失败：3 != 4，输入为：3

- user unknown

嗨，一开始我把问题考虑成“大于或等于”。然后，我发现当我输入13时，它输出11，所以我会检查并编辑我的帖子。感谢（有点残酷的）建议。 - Christopher Chiche

@userunknown 感谢您的建议，我在“compareInts”函数中遇到了问题，其中我错误地将“compare”用于字符串。 - Christopher Chiche

“Brutal”的建议是我的测试用例的复制粘贴输出，你可以直接复制，因为你的界面是相同的。 - user unknown

现在所有的测试用例都可以正常工作了。如果我们考虑我在注释中提到的“严格更大”的情况。 - Christopher Chiche

Answer 8

  @tailrec
  def palindrome(str: String, start: Int, end: Int): Boolean = {
    if (start == end)
      true
    else if (str(start) != str(end))
      false
    else
      pali(str, start + 1, end - 1)
  }

  println(palindrome("arora", 0, str.length - 1))

- Avenger

---

请不要仅仅发布代码作为答案，还要提供解释您的代码是如何解决问题的。带有解释的答案通常更有帮助和更高质量，并且更有可能吸引赞同。 - Mark Rotteveel

Answer 9

你可以尝试这样做，我正在使用基本的递归：

 object Palindromo {
  def main(args: Array[String]): Unit = {

    var s: String = "arara"
    println(verificaPalindromo(s))
  }

  def verificaPalindromo(s: String): String = {
    if (s.length == 0 || s.length == 1)
      "true" 
    else
      if (s.charAt(0).toLower == s.charAt(s.length - 1).toLower)
        verificaPalindromo(s.substring(1, s.length - 1))
      else
        "false"
  }
}

- Jubs

---

这不是问题中所要求的解决方案，即“大于K的最小回文数的值”。请重新阅读所有先前的答案，以更好地了解所需内容。 - jwvh