回文检查 Java 中 Int 的效率

Question

我已经构建了两种检查数字回文的方法。哪个效率更高？我所说的效率是指执行时间和内存分配。

首先，我将整数转换为字符串并检查它是否是回文。代码示例如下。

public class Palindrome{

/*

Function palindromeCheck

Return type boolean

Parameters characterArray

Checks 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 Function

Calls palinDromeCheck function

Prints 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 {&nbsp; &nbsp; public static boolean isPalindrome1(int n) {&nbsp; &nbsp; &nbsp; &nbsp; char a[] = Integer.toString(n).toCharArray();&nbsp; &nbsp; &nbsp; &nbsp; int i = 0;&nbsp; &nbsp; &nbsp; &nbsp; int j = a.length - 1;&nbsp; &nbsp; &nbsp; &nbsp; while (i < j) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (a[i++] != a[j--]) return false;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; return true;&nbsp; &nbsp; }&nbsp; &nbsp; public static boolean isPalindrome2(int n) {&nbsp; &nbsp; &nbsp; &nbsp; int p = n, q = 0;&nbsp; &nbsp; &nbsp; &nbsp; while (n > 0) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; q = 10 * q + n % 10;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; n /= 10;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; return p == q;&nbsp; &nbsp; }&nbsp; &nbsp; public static boolean isPalindrome3(int n) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;String s = Integer.toString(n);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;return s.equalsIgnoreCase(new StringBuilder(s).reverse().toString());&nbsp; &nbsp; }&nbsp; &nbsp; public static void main(String[] args) {&nbsp; &nbsp; &nbsp; &nbsp; final int m = 10000000;&nbsp; &nbsp; &nbsp; &nbsp; long t1, t2;&nbsp; &nbsp; &nbsp; &nbsp; boolean q;&nbsp; &nbsp; &nbsp; &nbsp; t1 = System.currentTimeMillis();&nbsp; &nbsp; &nbsp; &nbsp; for (int n = 0; n < m; n++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; q = isPalindrome1(123454321);&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; t2 = System.currentTimeMillis();&nbsp; &nbsp; &nbsp; &nbsp; System.out.println(t2 - t1);&nbsp; &nbsp; &nbsp; &nbsp; t1 = System.currentTimeMillis();&nbsp; &nbsp; &nbsp; &nbsp; for (int n = 0; n < m; n++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; q = isPalindrome2(123454321);&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; t2 = System.currentTimeMillis();&nbsp; &nbsp; &nbsp; &nbsp; System.out.println(t2 - t1);&nbsp; &nbsp; &nbsp; &nbsp; t1 = System.currentTimeMillis();&nbsp; &nbsp; &nbsp; &nbsp; for (int n = 0; n < m; n++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; q = isPalindrome3(123454321);&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; t2 = System.currentTimeMillis();&nbsp; &nbsp; &nbsp; &nbsp; System.out.println(t2 - t1);&nbsp; &nbsp; }}

Answer 3

你为什么要重新发明轮子？java.lang.StringBuilder 已经提供了字符串反转方法String string = Integer.toString(10101);boolean palindrome = string.equalsIgnoreCase(new StringBuilder(string).reverse().toString());