如何在 Java 中檢查數字是否為回文

1. 概述

眾所周知，如果一個數字翻轉後保持不變，則該數字是回文數。

在本教程中，我們將探索檢查數字是否為回文的不同方法，包括迭代方法、遞歸方法以及一些實現目標的最佳化方法。

2. 問題陳述

給定一個正整數N ，我們想知道它是否是回文。

輸入： N = 12321
輸出： Yes
解釋： 12321是一個回文數，因為它的數字顛倒後變成了12321,與原來的數相同。

輸入： N = 123
輸出： No
解釋： 123不是回文數，因為它的數字顛倒後變成了321 ，與原來的數不同。

現在，讓我們討論幫助我們找出數字是否為回文數的方法。

3. 使用迭代方法

檢查數字是否為回文數的最直接方法是反轉數字並將反轉後的數字與原始數字進行比較：

public static boolean isPalindromeIterative(int number) {

 int originalNumber = number;

 int reversedNumber = 0;



 while (number > 0) {

 int digit = number % 10;


 reversedNumber = reversedNumber * 10 + digit;


 number /= 10;

 }

 return originalNumber == reversedNumber;

 }

因此，我們首先保留原始號碼的副本。這很重要，因為我們稍後需要對其進行比較。接下來，我們透過一位一位地提取數字來反轉該數字。我們透過獲取數字的最後一位數字並將其添加到我們正在建立的新數字（從0開始）來實現此目的。從原始數字中取出每個數字，我們透過除以10來縮小它。

讓我們看看迭代方法的測試案例：

@Test

 void givenNumber_whenUsingIterativeApproach_thenCheckPalindrome() {

 assertTrue(PalindromeNumber.isPalindromeIterative(12321));

 assertFalse(PalindromeNumber.isPalindromeIterative(123));

 }

一旦我們處理完所有的數字，我們就得到了原始數字的反轉版本。最後一步是將這個反轉的數字與我們之前保存的原始數字進行比較。如果它們匹配，則表示該數字是回文數。

我們來理解一下這個邏輯：

步驟1：設定originalNumber = 12321 ， reversedNumber = 0.
第二步：反轉數字
- 第一個數字：提取1 ，將反轉後的數字更新為1 ，並將number減少為1232 。
- 第二位數字：提取2 ，將reversedNumber更新為12 ，並將number減少為123 。
- 第三位：提取3 ，將reversedNumber更新為123 ，並將number減少為12 。
- 第四位：提取2 ，將reversedNumber更新為 1232 ，並將number減少為1 。
- 第五位：擷取1 ，將reversedNumber更新為12321 ，將number減少為0 。
步驟3：由於reversedNumber (12321)與originalNumber (12321)匹配，因此該數字是回文數。

此循環對數字中的每個數字運行一次。若數字有n位，則時間複雜度為O(n) 。循環內的每個運算（模、除法和乘法）都需要常數時間O(1) 。因此，總體時間複雜度為O(n) 。並且，我們為像originalNumber 、 reversedNumber和digit這樣的變數使用了恆定量的額外空間，因此空間複雜度為O(1) 。

4. 使用字串轉換

另一種方法是將數字轉換為字串，反轉它，然後與原始字串進行比較：

public static boolean isPalindromeString(int number) {

 String original = String.valueOf(number);

 String reversed = new StringBuilder(original).reverse().toString();

 return original.equals(reversed);

 }

在這種方法中，我們首先將數字轉換為字串。然後，我們使用一個名為StringBuilder的方便工具來反轉該字串。一旦我們有了反轉版本，我們就將它與原始字串進行比較。如果它們匹配，則該數字是回文數。

讓我們看看字串方法的測試案例：

@Test

 void givenNumber_whenUsingStringApproach_thenCheckPalindrome() {

 assertTrue(PalindromeNumber.isPalindromeString(12321));

 assertFalse(PalindromeNumber.isPalindromeString(123));

 }

讓我們來試運行這段程式碼：

步驟1：將數字轉換為字串： original = “12321” 。
步驟2：使用內建方法反轉字串： reversed = “12321” 。
最後一步：使用original.equals(reversed).由於它傳回true ，因此表示該數字是回文數。

此方法中的迴圈針對數字中的每個數字迭代一次，導致時間複雜度為O(n) ，其中n是數字位數。迴圈內的每個運算（例如求模、除法和乘法）都是在恆定時間O(1)內執行的。至於空間複雜度，像originalNumber 、 reversedNumber和digit這樣的變數只需要恆定量的額外空間，導致空間複雜度為O(1) 。

5. 使用遞歸方法

我們也可以使用遞歸檢查回文，儘管它更複雜且不常用：

public static boolean isPalindromeRecursive(int number) {

 return isPalindromeHelper(number, 0) == number;

 }



 private static int isPalindromeHelper(int number, int reversedNumber) {

 if (number == 0) {

 return reversedNumber;

 }

 reversedNumber = reversedNumber * 10 + number % 10;

 return isPalindromeHelper(number / 10, reversedNumber);

 }

在遞歸方法中，我們保留原始數字的副本。這很重要，因為我們稍後需要對其進行比較。接下來，我們透過一位一位地提取數字來反轉該數字。為此，我們將數字的最後一位數字添加到我們正在建立的新數字中，該數字從零開始。我們將原始數字中的每一位數字除以 10 來縮小它。

下面是遞歸方法的測試案例：

@Test

 void givenNumber_whenUsingRecursiveApproach_thenCheckPalindrome() {

 assertTrue(PalindromeNumber.isPalindromeRecursive(12321));

 assertFalse(PalindromeNumber.isPalindromeRecursive(123));

 }

讓我們空運行一下這段程式碼來檢查12321是否是回文。

步驟1：呼叫isPalindromeHelper(12321, 0) 。
步驟 2：遞歸建構反轉數
- 第一次呼叫：反轉最後一位數字1 ，將reversedNumber更新為1 ，然後呼叫isPalindromeHelper(1232, 1) 。
- 第二次呼叫： Reverse 2 ，將reversedNumber更新為12 ，並呼叫isPalindromeHelper(123, 12)
- 第三次呼叫：Reverse 3，將reversedNumber更新為123 ，然後呼叫isPalindromeHelper(12, 123) 。
- 第四次呼叫：Reverse 2，將reversedNumber更新為1232 ，並呼叫isPalindromeHelper(1, 1232) 。
- 第五次呼叫：反轉1，將reversedNumber更新為12321 ，並呼叫isPalindromeHelper(0, 12321) 。
基本情況：返回reversedNumber (12321)並與originalNumber (12321). S它們匹配，就確認該數字是回文數。

對於數字中的每個數字呼叫一次遞歸函數，因此時間複雜度為O(n) 。每個遞歸呼叫都涉及一個常數時間操作O(1) 。遞歸深度等於數字中的位數，因此由於呼叫堆疊的原因，空間複雜度為O(n) 。

6.半反轉法

這種方法比完全反轉方法更節省空間，因為它只反轉一半的數字。這個想法是將數字後半部分的數字反轉並與前半部分進行比較。

讓我們逐步了解這種方法及其實現和範例：

public static boolean isPalindromeHalfReversal(int number) {

 if (number < 0 || (number % 10 == 0 && number != 0)) {

 return false;

 }

 int reversedNumber = 0;

 while (number > reversedNumber) {

 reversedNumber = reversedNumber * 10 + number % 10;

 number /= 10;

 }

 return number == reversedNumber || number == reversedNumber / 10;

 }

這是半反轉方法的測試案例：

@Test

 void givenNumber_whenUsingHalfReversalApproach_thenCheckPalindrome() {

 assertTrue(PalindromeNumber.isPalindromeHalfReversal(12321));

 assertFalse(PalindromeNumber.isPalindromeHalfReversal(123));

 }

讓我們空運行一下這段程式碼來檢查12321是否是回文：

最初， number = 12321且reversedNumber = 0 。
第一次迭代： number = 1232 ， reversedNumber = 1.
第二次迭代： number = 123, reversedNumber = 12.
第三次迭代： number = 12, reversedNumber = 123.
循環停止，因為number (12)不再大於reversedNumber (123) 。
由於number == reversedNumber / 10 ，函數傳回true 。

由於我們只處理一半的數字，因此時間複雜度為O(n),其中n是位數，並且我們只使用少數整數變量，因此空間複雜度為O(1) 。

7.逐位比較

這種方法透過比較從數字的開頭和結尾向中心移動的數字，避免了完全反轉數字。

讓我們逐步了解這種方法及其實現和範例：

public static boolean isPalindromeDigitByDigit(int number) {

 if (number < 0) {

 return false;

 }

 int divisor = 1;

 while (number / divisor >= 10) {

 divisor *= 10;

 }

 while (number != 0) {

 int leading = number / divisor;

 int trailing = number % 10;

 if (leading != trailing) {

 return false;

 }

 number = (number % divisor) / 10;

 divisor /= 100;

 }

 return true;

 }

這是此方法的測試案例：

@Test

 void givenNumber_whenUsingDigitByDigitApproach_thenCheckPalindrome() {

 assertTrue(PalindromeNumber.isPalindromeDigitByDigit(12321));

 assertFalse(PalindromeNumber.isPalindromeDigitByDigit(123));

 }

讓我們為12321運行此程式碼：

對於12321 ，最初， divisor = 10000,即10^(number of digits – 1).
將第一個數字(1)與最後一個數字(1)進行比較。
刪除兩位數字，調整除數，然後繼續比較。
如果所有數字對匹配，則傳回true 。

由於我們比較從兩端向中心移動的數字，時間複雜度為O(n) ，其中n是位數，我們只使用幾個整數變量，因此空間複雜度仍然是O(1).

八、結論

在本文中，我們遇到了幾種檢查數字是否回文的方法。選擇正確的方法取決於我們的特定需求。如果我們追求簡單性並且能夠承受更多的記憶體使用，那麼字串轉換方法可能是我們的首選。半反轉或逐位比較方法以最小的空間開銷提供出色的效能，從而提供更有效率的解決方案，尤其是在處理大量資料時。

每種方法都有其魅力，了解這些不同的策略可以幫助我們選擇最適合我們情況的方法，無論我們優先考慮可讀性、記憶體使用還是計算效率。

與往常一樣，所有這些範例的原始程式碼都可以在 GitHub 上取得。

本作品係原創或者翻譯，採用《署名-非商業性使用-禁止演繹4.0國際》許可協議