java - 为什么我的 SPOJ 经典问题 5 超过了时间限制？

Question

我应该有 9 秒的时间限制，但是当我在 NetBeans 上运行 2 个接近一百万位数的数字时，输出需要 5 秒。我的 isPalindrome 方法比较对称数字（第一个和最后一个，第二个和第二个最后等......）并根据以下规则编辑数字：

1. 如果左边的数字（第一个数字，第二个数字等......）大于右边的数字（最后一个数字，第二个最后一个数字等......），使右边的数字与左边的数字匹配(9113 ---> 9119)
2. 如果左边的数字小于右边的数字，使右边的数字与左边的数字匹配，但增加右边数字旁边的数字的值（3987 ---> 3993 或 8999 ---> 9008 或 7899 ---> 7907)

我按照这些规则保留我的号码，直到找到回文。

总结一下我的问题是：为什么在 NetBeans 上我的程序在给定的时间范围内运行时会出现超出时间限制的错误？

公共类 SPOJ5 {

/**
 * @param args the command line arguments
 */
private static final String counter = "01234567890";

public static void main(String[] args) {
    int t;
    BigInteger addNum;
    List<BigInteger> k = new ArrayList();
    Scanner in = new Scanner(System.in);

    do {
        try {
            t = Integer.parseInt(in.next());
        } catch (Exception e) {
            t = 2;
        }
    } while (t < 0);

    do {
        try {
            addNum = new BigInteger(in.next());
            addNum = addNum.add(BigInteger.ONE);
            if (digitCount(addNum) < 999999) {
                k.add(addNum);
            }
        } catch (Exception e) {
            k.add(BigInteger.valueOf(9).pow(100));
        }
        t--;
    } while (t > 0);

    for (BigInteger num : k) {
        int digits = digitCount(num);
        int middleNum;
        int count = 0;
        StringBuilder number = new StringBuilder(num.toString());

        if (digits % 2 == 0) {
            middleNum = digits / 2;
            number = new StringBuilder(num.toString());

            number = isPalindrome(number, digits - 1, count, middleNum);

        } else {
            middleNum = digits / 2;
            number = isPalindrome(number, digits - 1, count, middleNum + 1);
        }

        System.out.println(number);

    }
}

public static StringBuilder isPalindrome(StringBuilder number, int lastDigitIndex, int firstDigitIndex, int middleNum) {
    while (lastDigitIndex >= middleNum) {

        if (number.charAt(firstDigitIndex) != number.charAt(lastDigitIndex)) {

            if (counter.indexOf(number.charAt(firstDigitIndex)) > counter.indexOf(number.charAt(lastDigitIndex))) {
                number.replace(lastDigitIndex, lastDigitIndex + 1, Character.toString(number.charAt(firstDigitIndex)));
                firstDigitIndex++;
                lastDigitIndex--;
            } else {
                number.replace(lastDigitIndex, lastDigitIndex + 1, Character.toString(number.charAt(firstDigitIndex)));

                do {
                    number.replace(lastDigitIndex - 1, lastDigitIndex, Character.toString(counter.charAt(counter.indexOf(number.charAt(lastDigitIndex - 1)) + 1)));
                    lastDigitIndex--;
                } while ((Character.toString(counter.charAt(counter.indexOf(number.charAt(lastDigitIndex)))).equals("0")));

                lastDigitIndex = number.length() - 1;
                firstDigitIndex = 0;
            }
        } else {
            firstDigitIndex++;
            lastDigitIndex--;
        }

    }
    return number;
}

public static int digitCount(BigInteger bi) {
    String s = bi.toString();
    return s.length();
}

}

标签： javapalindrome