问题描述
首先这里的问题是：
一个正整数被称为回文如果其重新presentation在十进制系统是相同的读取从左到右时和从右到左。对于给定的正整数K个不超过百万位数，写最小回文大于K至输出的值。数字总是显示不带前导零。
A positive integer is called a palindrome if its representation in the decimal system is the same when read from left to right and from right to left. For a given positive integer K of not more than 1000000 digits, write the value of the smallest palindrome larger than K to output. Numbers are always displayed without leading zeros.
输入：第一行包含整数t，测试用例的数量。整数K的给定在下一吨行
Input: The first line contains integer t, the number of test cases. Integers K are given in the next t lines.
输出：对于每一个K，输出最小的回文比K.大示例
Output: For each K, output the smallest palindrome larger than K.Example
输入：
2
808
2133
输出：
818
2222
其次这里是我的code：
Secondly here is my code:
// 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 < length/2; i++){
leftPos = i;
rightPos = (length-1) - i;
offsetPos = rightPos -1; offsetUpdated = false;
// set values at opposite indices and offset
left = Integer.parseInt(String.valueOf(theNumber.charAt(leftPos)));
right = Integer.parseInt(String.valueOf(theNumber.charAt(rightPos)));
offset = Integer.parseInt(String.valueOf(theNumber.charAt(offsetPos)));
if(left != right){
// if r > 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
}
最后，我的解释和问题。
Finally my explaination and question.
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 i.e 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 e.g 78849887
we set the 9 --> 4 and increase 4 --> 5, so we must cater for this.
现在的问题是，从spoj.pl在线评判系统。我的code适用于所有的测试可以提供，但是当我提出它，我得到一个时间限制超出错误，我的回答是不能接受的。
The problem is from spoj.pl an online judge system. My code works for all the test can provide but when I submit it, I get a time limit exceeded error and my answer is not accepted.
有没有人有任何建议，我怎么能提高我的算法。在写这个问题我想代替我而（偏移== 0安培;＆安培; offsetUpdated）循环我可以用一个布尔值，以确保我增加抵消了我的下一个[I]迭代。我常或任何建议的确认将AP preciated，也让我知道，如果我需要让我的问题更加清晰。
Does anyone have any suggestions as to how I can improve my algorithm. While writing this question i thought that instead of my while (offset == 0 && offsetUpdated) loop i could use a boolean to to make sure i increment the offset on my next [i] iteration. Confirmation of my chang or any suggestion would be appreciated, also let me know if i need to make my question clearer.
推荐答案
这似乎是一个很大的code。您是否尝试过一个非常幼稚的做法吗？检查东西是否是一个回文其实很简单。
This seems like a lot of code. Have you tried a very naive approach yet? Checking whether something is a palindrome is actually very simple.
private boolean isPalindrome(int possiblePalindrome) {
String stringRepresentation = String.valueOf(possiblePalindrome);
if ( stringRepresentation.equals(stringRepresentation.reverse()) ) {
return true;
}
}
现在可能不是最高效的code，但它给你一个非常简单的出发点：
Now that might not be the most performant code, but it gives you a really simple starting point:
private int nextLargestPalindrome(int fromNumber) {
for ( int i = fromNumber + 1; ; i++ ) {
if ( isPalindrome( i ) ) {
return i;
}
}
}
现在，如果觉得不够快，你可以把它作为一个参考实现，并在降低算法复杂度的工作。
Now if that isn't fast enough you can use it as a reference implementation and work on decreasing the algorithmic complexity.
有实际上应该是一个固定时间（以及其为线性上的输入的位数）的方式找到下一个最大的回文。我给一个算法，假定的数目是偶数的位长（但可扩展到的奇数个数字）。
There should actually be a constant-time (well it is linear on the number of digits of the input) way to find the next largest palindrome. I will give an algorithm that assumes the number is an even number of digits long (but can be extended to an odd number of digits).
- 找到小数重新输入号码（2133）presentation。
- 将它分成的左半部分和右半部分（21，33）;
- 比较在左半和右半的第一个数字的最后一位数字。
一个。如果右边是大于的左侧，增加左和停止。 （22）
湾如果右边是小于左侧，停止。
C。如果右边是等于的左侧，与第二最后一位数字的左和右的第二位（依此类推）重复步骤3。 - 取左半部分和附加左半逆转。这就是你的下一个最大的回文。 （2222）
- Find the decimal representation of the input number ("2133").
- Split it into the left half and right half ("21", "33");
- Compare the last digit in the left half and the first digit in the right half.
a. If the right is greater than the left, increment the left and stop. ("22")
b. If the right is less than the left, stop.
c. If the right is equal to the left, repeat step 3 with the second-last digit in the left and the second digit in the right (and so on). - Take the left half and append the left half reversed. That's your next largest palindrome. ("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
此似乎有点类似于你所描述的算法，但它开始于内的数字，并移动到外
This seems a bit similar to the algorithm you described, but it starts at the inner digits and moves to the outer.
这篇关于一个更好的算法来寻找一些字符串的下一个回文的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！