在 Java 中檢查一個數字是否為快樂數字
1. 概述
我們經常在程式設計中解決數學問題。確定一個數字是否為快樂的數字是一項有趣的任務。
在本教程中，我們將了解如何定義快樂數，並探索如何實作 Java 程式來檢查給定數字是否為快樂數。
2. 理解快樂數
一個快樂的數字透過其數字的平方和的重複替換達到1。相反，一個不快樂（悲傷）的數字會陷入無限循環，永遠不會達到 1。
像往常一樣，幾個例子可以幫助我們快速理解快樂數字的定義：
Given number: 19
19 -> 1^2 + 9^2 = 82
82 -> 8^2 + 2^2 = 68
68 -> 6^2 + 8^2 = 100
100 -> 1^2 + 0^2 + 0^2 = 1
1如同上面的例子所示，我們輸入的數字19最終達到了1。因此，19是一個快樂的數字。同樣，更快樂的數字範例是 7、10、13、23 等。
然而，如果輸入是 15，我們永遠不會達到 1：
Given number: 15
15 -> 1^2 + 5^2 = 26
26 -> 2^2 + 6^2 = 40
40 -> 4^2 + 0^2 = 16
+---> 16 -> 1^2 + 6^2 = 37
| 37 -> 3^2 + 7^2 = 58
| 58 -> 5^2 + 8^2 = 89
| 89 -> 8^2 + 9^2 = 145
| 145 -> 1^2 + 4^2 + 5^2 = 42
| 42 -> 4^2 + 2^2 = 20
| 20 -> 2^2 + 0^2 = 4
| 4 -> 4^2 = 16
+------16
正如我們所看到的，該過程在 16 和 4 之間無限循環，永遠不會達到 1。因此，15 是一個悲傷的數字。
遵循這個規則，我們可以找到更多悲傷的數字，像是4、6、11、20等。
3. 實作檢查方法
現在我們了解如何定義快樂數字，讓我們實作 Java 方法來檢查給定數字是否為快樂數字。
如果由每個數字的平方和組成的序列包含一個循環，則該數字是可悲的。換句話說，給定一個數字，如果序列中已經存在一步的計算結果，那麼它就是一個可悲的數字。
我們可以利用HashSet資料結構在 Java 中實作這個邏輯。這使我們能夠儲存每個步驟的結果，並有效地檢查集合中是否已存在新計算的結果：
class HappyNumberDecider {
public static boolean isHappyNumber(int n) {
Set<Integer> checkedNumbers = new HashSet<>();
while (true) {
n = sumDigitsSquare(n);
if (n == 1) {
return true;
}
if (checkedNumbers.contains(n)) {
return false;
}
checkedNumbers.add(n);
}
}
// ...
}如上面的程式碼所示， sumDigitsSquare()方法執行實際計算並傳回結果：
private static int sumDigitsSquare(int n) {
int squareSum = 0;
while (n != 0) {
squareSum += (n % 10) * (n % 10);
n /= 10;
}
return squareSum;
}接下來，讓我們建立一個測試來驗證isHappyNumber()方法是否會報告不同輸入的預期結果：
assertTrue(HappyNumberDecider.isHappyNumber(7));
assertTrue(HappyNumberDecider.isHappyNumber(10));
assertTrue(HappyNumberDecider.isHappyNumber(13));
assertTrue(HappyNumberDecider.isHappyNumber(19));
assertTrue(HappyNumberDecider.isHappyNumber(23));
assertFalse(HappyNumberDecider.isHappyNumber(4));
assertFalse(HappyNumberDecider.isHappyNumber(6));
assertFalse(HappyNumberDecider.isHappyNumber(11));
assertFalse(HappyNumberDecider.isHappyNumber(15));
assertFalse(HappyNumberDecider.isHappyNumber(20));4. 性能分析
首先，我們來分析一下該解決方案的時間複雜度。
假設我們有一個包含k位數字的數字n 。因此，我們需要k次迭代來計算數字平方和。此外，由於k = log n （以 10 為底的對數） ，因此計算第一個結果的時間複雜度為 O(log n)。我們稱之為result1 。由於最大位數為 9，因此result1的最大值為**9^2 * log n** .
如果result1不是 1，我們必須重複呼叫sumDigitsSquare().那麼，到目前為止的時間複雜度為O(log n) + O(log (9^2 * log n)) = O(log n) + O(log 81 + log log n) 。刪除常數部分後，我們得到O(log n) + O(log log n) 。
因此，我們的總時間複雜度變成O(log n) + O(log log n) + O(log log log n) + O(log log log log n) + …直到結果達到1 或我們偵測到循環。由於log n是該表達式中的主要部分，因此解的時間複雜度為 O(log n)。
在進行空間複雜度分析之前，我們先列出k位最大數n以及對應的result1 ：
k Largest n result1
1 9 81
2 99 162
3 999 243
4 9999 324
5 99999 405
6 999999 486
7 9999999 567
8 99999999 648
9 999999999 729
10 9999999999 810
11 99999999999 891
12 999999999999 972
13 9999999999999 1053
...
1m 9..a million..9 81000000我們可以看到，給定超過三位數的數字n ，重複應用sumDigitsSquare()操作可以在幾個步驟內將n快速減少到三位數。
例如，當k=1m時， n比 Java 的Long.MAX_VALUE.只需要兩步驟就可以得到小於三位數的數字： 9..(1m)..9 -> 81000000 (9^2 * 1m = 81000000) -> 65 (8^2 + 1^2 = 65)
因此，在 Java 的int或long範圍內，可以合理地假設n需要恆定的C步驟才能達到三位或更少位數的數字。因此，我們的HashSet最多可容納C+243結果，從而產生 O(1) 的空間複雜度。
雖然此方法的空間複雜度為O(1)，但仍需要空間來儲存檢測循環的結果。
現在，我們的目標是改進解決方案，以在不使用額外空間的情況下識別快樂的數字。
5. 改進isHappyNumber()方法
Floyd 的週期偵測演算法可以偵測序列中的週期。例如，我們可以應用此演算法來檢查LinkedList是否包含圓。
這個想法是保持兩個指針， slow和fast. **slow**一次更新一步， fast每兩步更新一次。如果他們在 1 相遇，則給定的數字是快樂的。否則，如果它們相遇但值不為 1，則偵測到循環。因此，給出的數字是悲傷的。
接下來我們用Java來實作慢-快邏輯：
public static boolean isHappyNumberFloyd(int n) {
int slow = n;
int fast = n;
do {
slow = sumDigitsSquare(slow);
fast = sumDigitsSquare(sumDigitsSquare(fast));
} while (slow != fast);
return slow == 1;
}讓我們使用相同的輸入測試isHappyNumberFloyd()方法：
assertTrue(HappyNumberDecider.isHappyNumberFloyd(7));
assertTrue(HappyNumberDecider.isHappyNumberFloyd(10));
assertTrue(HappyNumberDecider.isHappyNumberFloyd(13));
assertTrue(HappyNumberDecider.isHappyNumberFloyd(19));
assertTrue(HappyNumberDecider.isHappyNumberFloyd(23));
assertFalse(HappyNumberDecider.isHappyNumberFloyd(4));
assertFalse(HappyNumberDecider.isHappyNumberFloyd(6));
assertFalse(HappyNumberDecider.isHappyNumberFloyd(11));
assertFalse(HappyNumberDecider.isHappyNumberFloyd(15));
assertFalse(HappyNumberDecider.isHappyNumberFloyd(20));最後，此解決方案的時間複雜度仍然是 O(log n)。由於它不需要額外的空間，所以它的空間複雜度是O(1)。
六，結論
在本文中，我們學習了快樂數的概念，並實作了 Java 方法來確定給定數字是否快樂。
與往常一樣，範例的完整原始程式碼可在 GitHub 上取得。