查找数字字符串的下一个回文的更好算法

首先是问题所在：

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

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

输出：对于每个K，输出大于K的最小回文。示例

输入：

2

808

2133

输出：

818

2222

其次这是我的代码：

// I know it is bad practice to not cater for erroneous input, // however for the purpose of the execise it is omitted import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Scanner; import java.lang.Exception; import java.math.BigInteger; public class Main { public static void main(String [] args){ try{ Main instance = new Main(); // create an instance to access non-static // variables // Use java.util.Scanner to scan the get the input and initialise the // variable Scanner sc=null; BufferedReader r = new BufferedReader(new InputStreamReader(System.in)); String input = ""; int numberOfTests = 0; String k; // declare any other variables here if((input = r.readLine()) != null){ sc = new Scanner(input); numberOfTests = sc.nextInt(); } for (int i = 0; i < numberOfTests; i++){ if((input = r.readLine()) != null){ sc = new Scanner(input); k=sc.next(); // initialise the remainder of the variables sc.next() instance.palindrome(k); } //if }// for }// try catch (Exception e) { e.printStackTrace(); } }// main public void palindrome(String number){ StringBuffer theNumber = new StringBuffer(number); int length = theNumber.length(); int left, right, leftPos, rightPos; // if incresing a value to more than 9 the value to left (offset) need incrementing int offset, offsetPos; boolean offsetUpdated; // To update the string with new values String insert; boolean hasAltered = false; for(int i = 0; i  l then offest needs updating if(right > left){ // update and replace right = left; insert = Integer.toString(right); theNumber.replace(rightPos, rightPos + 1, insert); offset++; if (offset == 10) offset = 0; insert = Integer.toString(offset); theNumber.replace(offsetPos, offsetPos + 1, insert); offsetUpdated = true; // then we need to update the value to left again while (offset == 0 && offsetUpdated){ offsetPos--; offset = Integer.parseInt(String.valueOf(theNumber.charAt(offsetPos))); offset++; if (offset == 10) offset = 0; // replace insert = Integer.toString(offset); theNumber.replace(offsetPos, offsetPos + 1, insert); } // finally incase right and offset are the two middle values left = Integer.parseInt(String.valueOf(theNumber.charAt(leftPos))); if (right != left){ right = left; insert = Integer.toString(right); theNumber.replace(rightPos, rightPos + 1, insert); } }// if r > l else // update and replace right = left; insert = Integer.toString(right); theNumber.replace(rightPos, rightPos + 1, insert); }// if l != r }// for i System.out.println(theNumber.toString()); }// palindrome } 

最后我的解释和问题。

 My code compares either end and then moves in if left and right are not equal if right is greater than left (increasing right past 9 should increase the digit to its left ie 09 ---- > 10) and continue to do so if require as for 89999, increasing the right most 9 makes the value 90000 before updating my string we check that the right and left are equal, because in the middle eg 78849887 we set the 9 --> 4 and increase 4 --> 5, so we must cater for this. 

问题来自spoj.pl在线评判系统。 我的代码适用于所有测试可以提供但是当我提交它时，我得到超出时间限制错误，我的答案不被接受。

有没有人对如何改进我的算法有任何建议。 在写这个问题时，我认为不是我的while（offset == 0 && offsetUpdated）循环，我可以使用布尔值来确保我在下一个[i]迭代中增加偏移量。 确认我的行为或任何建议将不胜感激，如果我需要让我的问题更清楚，请告诉我。

Answer 1

这似乎是很多代码。 你尝试过一种非常天真的方法吗？ 检查某些东西是否是回文实际上非常简单。

 private boolean isPalindrome(int possiblePalindrome) { String stringRepresentation = String.valueOf(possiblePalindrome); if ( stringRepresentation.equals(stringRepresentation.reverse()) ) { return true; } } 

现在，这可能不是最高性能的代码，但它为您提供了一个非常简单的起点：

 private int nextLargestPalindrome(int fromNumber) { for ( int i = fromNumber + 1; ; i++ ) { if ( isPalindrome( i ) ) { return i; } } } 

现在，如果这还不够快，您可以将其用作参考实现，并努力降低算法的复杂性。

实际上应该有一个恒定时间（在输入的位数上是线性的）找到下一个最大的回文。 我将给出一个算法，假设该数字是偶数位数（但可以扩展为奇数位数）。

1. 找到输入数字的十进制表示（“2133”）。
2. 将它分成左半部分和右半部分（“21”，“33”）;
3. 比较左半部分的最后一位数字和右半部分的第一位数字。
   一个。 如果右边大于左边，则向左递增并停止。 （ “22”）
   湾 如果右边小于左边，则停止。
   C。 如果右边等于左边，重复步骤3，左边倒数第二个，右边第二个数字（依此类推）。
4. 取左半边，然后将左半边翻转。 这是你的下一个最大的回文。 （ “2222”）

适用于更复杂的数字：

 1. 1234567887654322 2. 12345678 87654322 3. 12345678 87654322 ^ ^ equal 3. 12345678 87654322 ^ ^ equal 3. 12345678 87654322 ^ ^ equal 3. 12345678 87654322 ^ ^ equal 3. 12345678 87654322 ^ ^ equal 3. 12345678 87654322 ^ ^ equal 3. 12345678 87654322 ^ ^ equal 3. 12345678 87654322 ^ ^ greater than, so increment the left 3. 12345679 4. 1234567997654321 answer 

这似乎与您描述的算法类似，但它从内部数字开始并移动到外部。

Answer 2

好吧，我有恒定的订单解决方案（至少为k阶，其中k是数字中的位数）

让我们举一些例子，假设n = 17208

将数字从中间分成两部分，并将最重要的部分可逆地写入不太重要的部分。 即17271，如果这样生成的数字大于你的n它是你的回文，如果不只是增加中心数（枢轴），即，你得到17371

其他例子

n = 17286 palidrome-attempt = 17271（因为它小于n增量枢轴，在这种情况下为2）所以palidrome = 17371

n = 5684 palidrome1 = 5665 palidrome = 5775

n = 458322回文数= 458854

现在假设n = 1219901 palidrome1 = 1219121递增枢轴使我的数字变小，所以增加邻近枢轴的数量也是1220221

这个逻辑可以扩展

Answer 3

当唯一需要的操作是一个简单的添加时，没有理由摆弄个别数字。 以下代码基于Raks的回答 。

该代码有意识地强调了执行速度的简单性。

 import static org.junit.Assert.assertEquals; import java.math.BigInteger; import org.junit.Test; public class NextPalindromeTest { public static String nextPalindrome(String num) { int len = num.length(); String left = num.substring(0, len / 2); String middle = num.substring(len / 2, len - len / 2); String right = num.substring(len - len / 2); if (right.compareTo(reverse(left)) < 0) return left + middle + reverse(left); String next = new BigInteger(left + middle).add(BigInteger.ONE).toString(); return next.substring(0, left.length() + middle.length()) + reverse(next).substring(middle.length()); } private static String reverse(String s) { return new StringBuilder(s).reverse().toString(); } @Test public void testNextPalindrome() { assertEquals("5", nextPalindrome("4")); assertEquals("11", nextPalindrome("9")); assertEquals("22", nextPalindrome("15")); assertEquals("101", nextPalindrome("99")); assertEquals("151", nextPalindrome("149")); assertEquals("123454321", nextPalindrome("123450000")); assertEquals("123464321", nextPalindrome("123454322")); } } 

Answer 4

以下代码查找数字的下一个Palandrome数字 –

 public class TestNextPalindrome { public static void main(String[] args) { int number1 = 45312; int number2 = 12345; int number3 = 12945; int number4 = 4531; int number5 = 1459; int number6 = 1997; System.out.print("For the number " + number1); getNextPalindrome(number1); System.out.print("For the number " + number2); getNextPalindrome(number2); System.out.print("For the number " + number3); getNextPalindrome(number3); System.out.print("For the number " + number4); getNextPalindrome(number4); System.out.print("For the number " + number5); getNextPalindrome(number5); System.out.print("For the number " + number6); getNextPalindrome(number6); } private static void getNextPalindrome(int number) { if (isSizeEven(number)) { getNextPalindromeForEvenLengthNumbers(number); } else { getNextPalindromeForOddLengthNumbers(number); } } private static boolean isSizeEven(int number) { if (String.valueOf(number).length() % 2 == 0) return true; return false; } private static void getNextPalindromeForEvenLengthNumbers(int number) { StringBuilder testPalindromeString = new StringBuilder(); testPalindromeString.append(number); StringBuilder convertTopalindrome = new StringBuilder(); convertTopalindrome.append(testPalindromeString.substring(0, testPalindromeString.length() / 2)); convertTopalindrome.append(testPalindromeString.delete(testPalindromeString.length() / 2, testPalindromeString.length()).reverse()); //if the palindrome is greater than the original number if (Integer.parseInt(convertTopalindrome.toString()) > number) { System.out.println(" the next palindrome is " + convertTopalindrome); } else { //get the middle elements in case of even numbers String middleElements = convertTopalindrome.substring(convertTopalindrome.length() / 2 - 1, convertTopalindrome.length() / 2 + 1); int middleElementsInt = Integer.valueOf(middleElements); //we are going to increment the middle elements by 1 so check if after this the value is not greater than 99. if (middleElementsInt + 11 < 99) { convertTopalindrome.replace(convertTopalindrome.length() / 2 - 1, convertTopalindrome.length() / 2 + 1, String.valueOf(middleElementsInt + 11)); System.out.println(" the next palindrome is " + convertTopalindrome); } else { String numberTillMiddleElement = convertTopalindrome.substring(0, convertTopalindrome.length() / 2 + 1); int numberTillMiddleElementInt = Integer.valueOf(numberTillMiddleElement); convertTopalindrome.replace(0, convertTopalindrome.length() / 2 + 1, String.valueOf(numberTillMiddleElementInt + 1)); getNextPalindrome(Integer.valueOf(convertTopalindrome.toString())); } } } private static void getNextPalindromeForOddLengthNumbers(int number) { StringBuilder testPalindromeString = new StringBuilder(); testPalindromeString.append(number); StringBuilder convertTopalindrome = new StringBuilder(); convertTopalindrome.append(testPalindromeString.substring(0, testPalindromeString.length() / 2 + 1)); convertTopalindrome.append(testPalindromeString.delete(testPalindromeString.length() / 2, testPalindromeString.length()).reverse()); //if the palindrome is greater than the original number if (Integer.parseInt(convertTopalindrome.toString()) > number) { System.out.println(" the next palindrome is " + convertTopalindrome); } else { char middleElement = convertTopalindrome.charAt(convertTopalindrome.length() / 2); int middleElementInt = Character.getNumericValue(middleElement); //we are going to increment the middle element by 1 so check if after this the value is not greater than 9. if (middleElementInt < 9) { convertTopalindrome.replace(convertTopalindrome.length() / 2, convertTopalindrome.length() / 2 + 1, String.valueOf(middleElementInt + 1)); System.out.println(" the next palindrome is " + convertTopalindrome); } else { String numberTillMiddleElement = convertTopalindrome.substring(0, convertTopalindrome.length() / 2 + 1); int numberTillMiddleElementInt = Integer.valueOf(numberTillMiddleElement); convertTopalindrome.replace(0, convertTopalindrome.length() / 2 + 1, String.valueOf(numberTillMiddleElementInt + 1)); getNextPalindrome(Integer.valueOf(convertTopalindrome.toString())); } } } } 

代码的解释可以在这里找到 - 使用Java查找Next Palindrome

Answer 5

这是我在java中的代码。 整个想法来自这里http://www.geeksforgeeks.org/given-a-number-find-next-smallest-palindrome-larger-than-this-number/

import java.util.Scanner;

公共类Main {

 public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.println("Enter number of tests: "); int t = sc.nextInt(); for (int i = 0; i < t; i++) { System.out.println("Enter number: "); String numberToProcess = sc.next(); // ne proveravam dal su brojevi nextSmallestPalindrom(numberToProcess); } } private static void nextSmallestPalindrom(String numberToProcess) { int i, j; int length = numberToProcess.length(); int[] numberAsIntArray = new int[length]; for (int k = 0; k < length; k++) numberAsIntArray[k] = Integer.parseInt(String .valueOf(numberToProcess.charAt(k))); numberToProcess = null; boolean all9 = true; for (int k = 0; k < length; k++) { if (numberAsIntArray[k] != 9) { all9 = false; break; } } // case 1, sve 9ke if (all9) { whenAll9(length); return; } int mid = length / 2; if (length % 2 == 0) { i = mid - 1; j = mid; } else { i = mid - 1; j = mid + 1; } while (i >= 0 && numberAsIntArray[i] == numberAsIntArray[j]) { i--; j++; } // case 2 already polindrom if (i == -1) { if (length % 2 == 0) { i = mid - 1; j = mid; } else { i = mid; j = i; } addOneToMiddleWithCarry(numberAsIntArray, i, j, true); } else { // case 3 not polindrom if (numberAsIntArray[i] > numberAsIntArray[j]) { // 3.1) while (i >= 0) { numberAsIntArray[j] = numberAsIntArray[i]; i--; j++; } for (int k = 0; k < numberAsIntArray.length; k++) System.out.print(numberAsIntArray[k]); System.out.println(); } else { // 3.2 like case 2 if (length % 2 == 0) { i = mid - 1; j = mid; } else { i = mid; j = i; } addOneToMiddleWithCarry(numberAsIntArray, i, j, false); } } } private static void whenAll9(int length) { for (int i = 0; i <= length; i++) { if (i == 0 || i == length) System.out.print('1'); else System.out.print('0'); } } private static void addOneToMiddleWithCarry(int[] numberAsIntArray, int i, int j, boolean palindrom) { numberAsIntArray[i]++; numberAsIntArray[j] = numberAsIntArray[i]; while (numberAsIntArray[i] == 10) { numberAsIntArray[i] = 0; numberAsIntArray[j] = numberAsIntArray[i]; i--; j++; numberAsIntArray[i]++; numberAsIntArray[j] = numberAsIntArray[i]; } if (!palindrom) while (i >= 0) { numberAsIntArray[j] = numberAsIntArray[i]; i--; j++; } for (int k = 0; k < numberAsIntArray.length; k++) System.out.print(numberAsIntArray[k]); System.out.println(); } 

}

Answer 6

 public class NextPalindrome { int rev, temp; int printNextPalindrome(int n) { int num = n; for (int i = num+1; i >= num; i++) { temp = i; rev = 0; while (temp != 0) { int remainder = temp % 10; rev = rev * 10 + remainder; temp = temp / 10; } if (rev == i) { break; } } return rev; } public static void main(String args[]) { NextPalindrome np = new NextPalindrome(); int nxtpalin = np.printNextPalindrome(11); System.out.println(nxtpalin); } } 

Answer 7

尝试这个

 public static String genNextPalin(String base){ //check if it is 1 digit if(base.length()==1){ if(Integer.parseInt(base)==9) return "11"; else return (Integer.parseInt(base)+1)+""; } boolean check = true; //check if it is all 9s for(char a: base.toCharArray()){ if(a!='9') check = false; } if(check){ String num = "1"; for(int i=0; i 

Answer 8

HI这是另一个使用python的简单算法，

  def is_palindrome(n): if len(n) <= 1: return False else: m = len(n)/2 for i in range(m): j = i + 1 if n[i] != n[-j]: return False return True def next_palindrome(n): if not n: return False else: if is_palindrome(n) is True: return n else: return next_palindrome(str(int(n)+1)) print next_palindrome('1000010') 

Answer 9

我写了一些注释来澄清每个步骤在这个python代码中做了什么。

需要考虑的一件事是输入可能非常大，我们不能简单地对它执行整数运算。 因此，将输入作为字符串然后操作它会更容易。

 tests = int(input()) results = [] for i in range(0, tests): pal = input().strip() palen = len(pal) mid = int(palen/2) if palen % 2 != 0: if mid == 0: # if the number is of single digit eg next palindrome for 5 is 6 ipal = int(pal) if ipal < 9: results.append(int(pal) + 1) else: results.append(11) # for 9 next palindrome will be 11 else: pal = list(pal) pl = l = mid - 1 pr = r = mid + 1 flag = 'n' # represents left and right half of input string are same while pl >= 0: if pal[pl] > pal[pr]: flag = 'r' # 123483489 in this case pal[pl] = 4 and pal[pr] = 3 so we just need to copy left half in right half break # 123484321 will be the answer elif pal[pl] < pal[pr]: flag = 'm' # 123487489 in this case pal[pl] = 4 and pal[pr] = 9 so copying left half in right half will make number smaller break # in this case we need to take left half increment by 1 and the copy in right half 123494321 will be the anwere else: pl = pl -1 pr = pr + 1 if flag == 'm' or flag == 'n': # increment left half by one and copy in right half if pal[mid] != '9': # if mid element is < 9 the we can simply increment the mid number only and copy left in right half pal[mid] = str(int(pal[mid]) + 1) while r < palen: pal[r] = pal[l] r = r + 1 l = l - 1 results.append(''.join(pal)) else: # if mid element is 9 this will effect entire left half because of carry pal[mid] = '0' # we need to take care of large inputs so we can not just directly add 1 in left half pl = l while pal[l] == '9': pal[l] = '0' l = l - 1 if l >= 0: pal[l] = str(int(pal[l]) + 1) while r < palen: pal[r] = pal[pl] r = r + 1 pl = pl - 1 if l < 0: pal[0] = '1' pal[palen - 1] = '01' results.append(''.join(pal)) else: while r < palen: # when flag is 'r' pal[r] = pal[l] r = r + 1 l = l - 1 results.append(''.join(pal)) else: # even length almost similar concept here with flags having similar significance as in case of odd length input pal = list(pal) pr = r = mid pl = l = mid - 1 flag = 'n' while pl >= 0: if pal[pl] > pal[pr]: flag = 'r' break elif pal[pl] < pal[pr]: flag = 'm' break else: pl = pl -1 pr = pr + 1 if flag == 'r': while r < palen: pal[r] = pal[l] r = r + 1 l = l - 1 results.append(''.join(pal)) else: if pal[l] != '9': pal[l] = str(int(pal[l]) + 1) while r < palen: pal[r] = pal[l] r = r + 1 l = l - 1 results.append(''.join(pal)) else: pal[mid] = '0' pl = l while pal[l] == '9': pal[l] = '0' l = l - 1 if l >= 0: pal[l] = str(int(pal[l]) + 1) while r < palen: pal[r] = pal[pl] r = r + 1 pl = pl - 1 if l < 0: pal[0] = '1' pal[palen - 1] = '01' results.append(''.join(pal)) for xx in results: print(xx) 

Answer 10

简单的代码和测试输出：

 class NextPalin { public static void main( String[] args ) { try { int[] a = {2, 23, 88, 234, 432, 464, 7887, 7657, 34567, 99874, 7779222, 2569981, 3346990, 229999, 2299999 }; for( int i=0; i