2

我正在尝试解决 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);
    }

 }
}
4

2 回答 2

0

如果不评论您的代码（其他人已解决），您不应该相信您听到的关于 Java 性能缓慢的所有内容。您必须非常努力地想出一种算法来解决竞争问题，该算法将在 C++ 的时间限制下运行，但在 Java 中则不行。导致缓慢的是您选择的算法，而不是 Java。

于 2013-05-20T06:12:41.763 回答
0

BigInteger 用于精确计算，但速度较慢。int 或 long 在这里会更好。

然后还有许多与 String 之间的转换，这些转换也很慢。

还有一些缓慢的字符串操作......

所以我建议使用 int 或 long 以及 Integer 或 Long 的静态辅助方法来操作数字的原始位。

这应该会导致您的程序的最佳性能。

于 2013-05-19T20:47:38.167 回答