- c - 在位数组中找到第一个零
- linux - Unix 显示有关匹配两种模式之一的文件的信息
- 正则表达式替换多个文件
- linux - 隐藏来自 xtrace 的命令
首先是这里的问题:
如果正整数在从左到右和从右到左读取时在十进制系统中的表示相同,则称为回文。给定一个不超过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。我的代码适用于所有测试可以提供的内容,但是当我提交它时,出现了超出时间限制的错误,并且我的答案未被接受。
有人对我如何改进算法有任何建议吗?在写这个问题时,我认为我可以使用 boolean 值来代替我的 while (offset == 0 && offsetUpdated) 循环来确保我在下一次 [i] 迭代中增加偏移量。确认我的更改或任何建议将不胜感激,如果我需要让我的问题更清楚,也请告诉我。
最佳答案
这似乎有很多代码。您是否尝试过一种非常天真的方法?检查某事物是否是回文实际上非常简单。
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
这似乎与您描述的算法有点相似,但它是从内部数字开始向外部移动。
关于java - 找到数字字符串的下一个回文的更好算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7934519/
例如,我有一个父类Author: class Author { String name static hasMany = [ fiction: Book,
代码如下: dojo.query(subNav.navClass).forEach(function(node, index, arr){ if(dojo.style(node, 'd
我有一个带有 Id 和姓名的学生表和一个带有 Id 和 friend Id 的 Friends 表。我想加入这两个表并找到学生的 friend 。 例如,Ashley 的 friend 是 Saman
我通过互联网浏览,但仍未找到问题的答案。应该很容易: class Parent { String name Child child } 当我有一个 child 对象时,如何获得它的 paren
我正在尝试创建一个以 Firebase 作为我的后端的社交应用。现在我正面临如何(在哪里?)找到 friend 功能的问题。 我有每个用户的邮件地址。 我可以访问用户的电话也预订。 在传统的后端中,我
我主要想澄清以下几点: 1。有人告诉我,在 iOS 5 及以下版本中,如果您使用 Game Center 设置多人游戏,则“查找 Facebook 好友”(如与好友争夺战)的功能不是内置的,因此您需要
关于redis docker镜像ENTRYPOINT脚本 docker-entrypoint.sh : #!/bin/sh set -e # first arg is `-f` or `--some-
我是一名优秀的程序员,十分优秀!