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

首先,这里是问题所在:

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

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

输出:对于每个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上。我的代码适用于所有测试可以提供的内容,但是当我提交它时,出现了超过时间限制的错误,并且我的答案不被接受。

有谁对我如何改善算法有任何建议。在写这个问题时,我以为我可以使用布尔值来确保我在下一个[i]迭代中增加偏移量,而不是我的while(offset == 0

&& offsetUpdated)循环。确认我的更改或任何建议,也将不胜感激,如果需要让我的问题更清楚,请让我知道。

回答:

这似乎是很多代码。您是否尝试过一种非常幼稚的方法?检查某物是否是回文实际上很简单。

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”)

    b。如果右侧 左侧,则停止。

    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

这似乎与您描述的算法有点类似,但它从内部数字开始,然后移到外部数字。

以上是 查找数字字符串下一个回文的更好算法 的全部内容, 来源链接: utcz.com/qa/412057.html

回到顶部