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 は正確な計算に使用されますが、SLOW です。ここでは int または long の方が良いでしょう。

そして、文字列との間の多くの変換があり、これも遅いです。

そして、いくつかの遅い文字列操作...

したがって、int または long と Integer または Long の静的ヘルパー メソッドを使用して、数値の生のビットを操作することをお勧めします。

これにより、プログラムの最高のパフォーマンスが得られるはずです。

于 2013-05-19T20:47:38.167 に答える