Mea*_*000 14 java algorithm palindrome
首先是问题所在:
如果正整数在从左到右和从右到左读取时在十进制系统中的表示相同,则称为回文.对于给定的正整数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 < 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
}
最后我的解释和问题.
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在线评判系统.我的代码适用于所有测试可以提供但是当我提交它时,我得到超出时间限制的错误,我的答案不被接受.
有没有人对如何改进我的算法有任何建议.在写这个问题时,我认为不是我的while(offset == 0 && offsetUpdated)循环,我可以使用布尔值来确保我在下一个[i]迭代中增加偏移量.确认我的chang或任何建议将不胜感激,如果我需要让我的问题更清楚,请告诉我.
Mar*_*ers 39
这似乎是很多代码.你尝试过一种非常天真的方法吗？检查某些东西是否是回文实际上非常简单.
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. 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
这似乎与您描述的算法类似,但它从内部数字开始并移动到外部.
好吧,我有恒定的订单解决方案(至少为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
这个逻辑可以扩展
当唯一需要的操作是一个简单的添加时,没有理由摆弄个别数字.以下代码基于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"));
}
}