我从 CodeChef 遇到了这个问题。问题说明如下：
如果一个正整数在十进制系统中的表示在从左到右和从右到左读取时相同，则称为回文。对于给定的不超过 1000000 位的正整数 K，将大于 K 的最小回文的值写入输出。
我可以定义一个 isPalindrome 方法，如下所示：
def isPalindrome(someNumber:String):Boolean = someNumber.reverse.mkString == someNumber
我面临的问题是，当整数满足 isPalindrome 方法时，如何从初始给定数字循环并中断并返回第一个回文？另外，是否有更好（有效）的方法来编写 isPalindrome 方法？
在这里获得一些指导会很棒
如果你有一个像 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"))
}
我想它也可以处理一百万位整数的情况。
做反向不是最好的主意。最好从字符串的开头和结尾开始，逐个元素地迭代和比较。即使在第一个和最后一个元素不匹配的情况下，您也正在浪费时间复制整个 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;
}
}
}
这是我可以实现的最通用和最清晰的解决方案：
编辑：摆脱BigInt's，现在计算百万位数只需不到一秒钟。
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
}
根据您的无范围建议：同样的事情，但使用 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 所说，它是直接的暴力破解，对于大量用户来说并不实用。
使用切片检查任何类型的列表是否是回文，没有任何循环
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
}
您可以简单地使用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)
验证字符串是否为回文的解决方案
此解决方案不会反转字符串。但是我不确定它会更快。
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"
}
然后，一个与整数的字符串表示进行比较的函数：（函数“比较”不适用于这种情况）
/* 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
}
}
}
你可以尝试这样的事情，我使用的是基本递归：
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"
}
}
@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))