回文检查 Java 中 Int 的效率

Question

我已经构建了两种检查数字回文的方法。哪个效率更高？我所说的效率是指执行时间和内存分配。首先，我将整数转换为字符串并检查它是否是回文。代码示例如下。public class Palindrome{/*Function palindromeCheckReturn type booleanParameters characterArrayChecks character array for palindrome*/ public static boolean palindromeCheck(char[] palinCheck){    boolean palindrome = true;    int firstLen = 0;    int secondLen = palinCheck.length - 1;    while(palindrome == true && firstLen < secondLen ){        if(palinCheck[firstLen] != palinCheck[secondLen]){            palindrome = false;        }        else{            firstLen++;            secondLen--;        }    } //end of while    return palindrome;} /*Main FunctionCalls palinDromeCheck functionPrints results*/public static void main(String[] args){    int palinCheck = 1221;    String dipendra = Integer.toString(palinCheck);    char[] dipendraChar = dipendra.toCharArray();    System.out.println(palindromeCheck(dipendraChar));}}第二种方法是不将其转换为字符串。public class PalindromeNumber{/*    Function: PalindromeCheck    parameters integer    ReturnType: boolean    Takes integer, checks if it is palindrome and returns accordingly*/public static boolean palindromeCheck(int number){    int firstNumber = number;    int secondNumber = 0;    while(number >= 1){        secondNumber = secondNumber* 10 + (number%10);        number = number/10;    }    return (firstNumber==secondNumber) ? true:false;}public static void main(String[] args){    System.out.println(palindromeCheck(111));}}

Answer 1

我敢打赌第二种算法会更快，而且显然更节省空间。如果您假设n是输入数字的位数，则在第一个算法中：

• Integer.toString需要n 个步骤才能将其转换为String.

• palindromeCheck需要n / 2 次比较来检查它是否是回文。

但是，第二种算法需要n 个步骤来计算倒数（仅涉及整数运算）并且只需要 1 个比较来检查。

Answer 2

我们试试吧。在以下示例中（使用一个特定数字，在我的特定机器上......）：

• 580 毫秒 - 您的第一个解决方案

• 323 毫秒 - 您的第二个解决方案

• 1045 毫秒 - BrentR 的解决方案

注意我修改了代码（但不是逻辑）。您还应该注意空格和缩进。

public class Palindrome {

    public static boolean isPalindrome1(int n) {

        char a[] = Integer.toString(n).toCharArray();

        int i = 0;

        int j = a.length - 1;

        while (i < j) {

            if (a[i++] != a[j--]) return false;

        }

        return true;

    }

    public static boolean isPalindrome2(int n) {

        int p = n, q = 0;

        while (n > 0) {

            q = 10 * q + n % 10;

            n /= 10;

        }

        return p == q;

    }

    public static boolean isPalindrome3(int n) {

         String s = Integer.toString(n);

         return s.equalsIgnoreCase(new StringBuilder(s).reverse().toString());

    }

    public static void main(String[] args) {

        final int m = 10000000;

        long t1, t2;

        boolean q;

        t1 = System.currentTimeMillis();

        for (int n = 0; n < m; n++) {

            q = isPalindrome1(123454321);

        }

        t2 = System.currentTimeMillis();

        System.out.println(t2 - t1);

        t1 = System.currentTimeMillis();

        for (int n = 0; n < m; n++) {

            q = isPalindrome2(123454321);

        }

        t2 = System.currentTimeMillis();

        System.out.println(t2 - t1);

        t1 = System.currentTimeMillis();

        for (int n = 0; n < m; n++) {

            q = isPalindrome3(123454321);

        }

        t2 = System.currentTimeMillis();

        System.out.println(t2 - t1);

    }

}

Answer 3

你为什么要重新发明轮子？

java.lang.StringBuilder 已经提供了字符串反转方法

String string = Integer.toString(10101);

boolean palindrome = string.equalsIgnoreCase(new StringBuilder(string).reverse().toString());