我正在尝试通过 SPOJ 解决问题。但对我来说问题不是算法的实际难度;这是我的 Java 代码的性能,因为它通常会导致超出时间限制错误。
我听说 Java 在竞赛问题上的表现比 C/C++ 慢是出了名的;但是,我现在唯一可以编写代码的语言是 Java。因此,我征求建议以使我的代码更整洁、更快。以下是我的解决方案和来源问题。
public class NextPalindrome {
public static BigInteger secondHalf(BigInteger b) {
String s = b.toString();
int n = s.length();
if(n==1){
return b;
}
String end = s.substring((n + 1) / 2, n);
BigInteger End = new BigInteger(end);
return End;
}
public static BigInteger reverse(BigInteger b) {
String s = b.toString();
int n = s.length();
String beg = b.toString();
String reversebeg = "";
while (true) {
for (int i = n - 1; i >= 0; i--) {
reversebeg = reversebeg + beg.charAt(i);
}
break;
}
BigInteger reverse = new BigInteger(reversebeg);
return reverse;
}
public static BigInteger firstHalf(BigInteger b) {
String s = b.toString();
int n = s.length();
if(n==1){
return b;
}
String beg = s.substring(0, n / 2);
BigInteger Beg = new BigInteger(beg);
return Beg;
}
public static BigInteger nextPalindrom(BigInteger b) {
String s = b.toString();
int n = s.length();
if(n==1){
if(b.equals(9)){
return BigInteger.valueOf(11);
} else {
return b.add(BigInteger.valueOf(1));
}
}
if (n % 2 == 1&&n>1) {
Character c = s.charAt(n / 2);
String C = c.toString();
BigInteger med = new BigInteger(C);
BigInteger beg = firstHalf(b);
BigInteger end = secondHalf(b);
if (reverse(beg).compareTo(end) <= 0) {
beg.add(BigInteger.valueOf(1));
if (med.compareTo(BigInteger.valueOf(9)) == 0) {
c = '0';
} else {
med = med.add(BigInteger.valueOf(1));
}
}
String temp = beg.toString();
String temp1 = reverse(beg).toString();
C = med.toString();
String result = temp + C;
result = result.concat(temp1);
BigInteger B = new BigInteger(result);
return B;
}
BigInteger beg = firstHalf(b);
BigInteger end = secondHalf(b);
if (reverse(beg).compareTo(end) <= 0) {
beg = beg.add(BigInteger.valueOf(1));
}
String temp = beg.toString();
String temp1 = reverse(beg).toString();
String result = temp.concat(temp1);
BigInteger B = new BigInteger(result);
return B;
}
public static void main(String[] args)throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
String s = in.readLine();
int N = Integer.parseInt(s);
for (int i = 0; i < N; i++) {
BigInteger big = new BigInteger(in.readLine());
BigInteger palindrom = nextPalindrom(big);
System.out.println(palindrom);
}
}
}
最佳答案
BigInteger 用于精确计算,但它很慢。在这里 int 或 long 会更好。
然后有很多与 String 的转换,也很慢。
还有一些缓慢的字符串操作...
所以我建议使用 int 或 long 以及 Integer 或 Long 的静态辅助方法 操纵数字的原始位。
这应该会导致您的程序达到最佳性能。
关于java - 需要固定我的 Java 代码,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16639291/