We start by first generating a palindrome out of the given input, by mirroring first half portion over to the second half, around the center. This will give us a palindrome that is closest to the input number
For example, the mirror of 65432 is 65456, which is the next palindrome.
BUT sometimes a mirrored number might be smaller than the original. For example, the mirror of 12345 is 12321, which is smaller. In this case, we need to increment the original number from the middle and then mirror it. So when 12345 is incremented from the middle, you get 12445 which mirrors to 12421, the next palindrome. Incrementing from the middle can get tricky if there is a 9 in the middle. For example, 12945 increments to 13045 which then mirrors to 13031.
http://www.chenguanghe.com/spoj-palin-the-next-palindrome/
Code from http://fahdshariff.blogspot.com/2010/04/next-palindrome.html
Read full article from SPOJ; The Next Palindrome | Bytehood
For example, the mirror of 65432 is 65456, which is the next palindrome.
BUT sometimes a mirrored number might be smaller than the original. For example, the mirror of 12345 is 12321, which is smaller. In this case, we need to increment the original number from the middle and then mirror it. So when 12345 is incremented from the middle, you get 12445 which mirrors to 12421, the next palindrome. Incrementing from the middle can get tricky if there is a 9 in the middle. For example, 12945 increments to 13045 which then mirrors to 13031.
http://www.chenguanghe.com/spoj-palin-the-next-palindrome/
题目大意: 给任意一个数, 找到比这个数大的最小的一个回文数字.
分析: 这题要考虑的情况很多, 比如例子中的808, 我们需要把0改成1, 因为如果我们改动最后的8, 前边的8也要增加, 所以改变的总量会更大, 只能改变0. 所以第一条就是, 我们要从数字的中间改. 另一个是2133变成2222. 这个改变的过程是2133->2132->2112->2222, 这里, 我们用的是meet in mid的策略, 我们要比较前边和后边的数字, 如果他们是一样的, 那么就忽略, 如果他们不一样, 前边比后边大, 就把后边改成前边的, 这样相当于增加了,所以就结束了. 如果后边大, 把前边赋值后边, 但是继续程序.最后一种情况是, 99999->100001. 我们把所有的9变成0, 然后最后的9变成1,然后前边加1.
public void solve(int testNumber, InputReader in, OutputWriter out) {
int t = in.readInt();
for (int i = 0; i < t; i++) {
solve(in.readLine(), out);
}
}
public void solve(String s, OutputWriter out) {
char[] str = s.trim().toCharArray();
boolean flag = false;
int length = str.length;
int i = 0;
int j = length - 1;
while (i <= j) {
if (str[j] < str[i])
flag = true;
str[j] = str[i];
i++;
j--;
}
if (flag) {
out.printLine(String.valueOf(str));
return;
}
i--;
if (str[i] != '9') {
str[i]++;
str[length - 1 - i] = str[i];
out.printLine(String.valueOf(str));
return;
}
else {
while (i >= 0 && str[i] == '9') {
str[length - 1 - i] = '0';
str[i] = '0';
}
if (i >= 0) {
str[i]++;
str[length - 1 - i] = str[i];
flag = true;
}
if (flag) {
out.printLine(String.valueOf(str));
return;
}
out.printLine(1+String.valueOf(str)+1);//???
return;
}
}
Code from http://fahdshariff.blogspot.com/2010/04/next-palindrome.html
/** * Increments the middle digit. * Example: 12345 -> 12445 and 1234 -> 1334 * 9s get incremented to 0 and carried over. * Example: 12945 -> 13045 * @param s * @return incremented string */ public static String incrementFromMiddle(String s) { final char[] arr = s.toCharArray(); final int midpoint = arr.length / 2; int currPoint = arr.length % 2 == 0 ? midpoint - 1 : midpoint; boolean found = false; while (currPoint >= 0 && !found) { char c = arr[currPoint]; char inc; if (c == '9') { inc = '0'; } else { inc = (char) (c + 1); found = true; } arr[currPoint] = inc; if (!found) { currPoint--; } } if (!found) { // we have fallen off the start of the string // example 999 has become 009. Add a one on to give: 1009 final char[] newarr = new char[arr.length + 1]; newarr[0] = '1'; System.arraycopy(arr, 0, newarr, 1, arr.length); return new String(newarr); } else { return new String(arr); } } /** * Next Palindrome using the mirroring approach. * @param s * @return */ public static String getNextPalindrome(String s) { String mirrored = mirror(s); //the mirror might be smaller than original, so increment it and try again. if (compare(mirrored, s) <= 0) { mirrored = mirror(incrementFromMiddle(s)); } return mirrored; }public static String mirror(String s) { final char[] arr = s.toCharArray(); int midpoint = arr.length / 2; int i = arr.length % 2 == 0 ? midpoint : midpoint + 1; while (i < arr.length) { arr[i] = arr[midpoint - 1]; i++; midpoint--; } return new String(arr); }