目錄

題意

算法思路

過題圖片

算法實現

代碼解析

復雜度分析

題目鏈接

結論

---

題意

判斷正整數 n 是不是快樂數。

快樂數定義：

（1）每次將正整數替換為它每個位置上的數字的平方和。

（2）重復這個過程直到這個數變為 1，也可能是無限循環但始終變不到 1。

（3）如果可以變為 1，這個數就是快樂數。

示例
輸入：19

輸出：true

解釋：

12 + 92 = 82

82 + 22 = 68

62 + 82 = 100

12 + 02 + 02 = 1

提示
1 <= n <= 2^31 -1

算法思路

這個問題的關鍵在于處理可能的無限循環。如果一個數最終會進入一個循環，那么它肯定不是快樂數。因此，我們可以使用哈希集合來記錄在迭代過程中出現過的數。如果新生成的數已經在哈希集合中，那么我們可以確定這個數不是快樂數，因為它已經進入了循環。

過題圖片

算法實現

以下是使用Java語言實現的算法：

import java.util.Set;
import java.util.HashSet;class Solution {private int getNextNumber(int n) {int res = 0;while (n > 0) {int temp = n % 10;res += temp * temp;n = n / 10;}return res;}public boolean isHappy(int n) {Set<Integer> record = new HashSet<>();while (n != 1 && !record.contains(n)) {record.add(n);n = getNextNumber(n);}return n == 1;}
}

代碼解析

1. getNextNumber 方法：這個方法用于計算給定數的下一個數，即每個位置上的數字的平方和。它通過不斷取模和除法操作來實現。

2. isHappy 方法：這是主要的算法實現。我們使用一個哈希集合 record 來記錄出現過的數。在循環中，我們不斷計算下一個數，并檢查這個數是否已經在 record 中。如果已經在 record 中，說明進入了循環，返回 false。如果計算得到的數為1，說明找到了快樂數，返回 true。

復雜度分析

• 時間復雜度：最壞情況下，我們需要遍歷所有可能的數直到找到1或者確定循環。在最壞情況下，這個算法的時間復雜度是 O(k)，其中 k 是快樂數序列的長度。對于非快樂數，時間復雜度取決于循環的長度，但在實際應用中，這個循環通常不會太長。

• 空間復雜度：我們使用了一個哈希集合來存儲已經出現過的數，因此空間復雜度是 O(k)，其中 k 是不同數的數量。

題目鏈接

202. 快樂數 - 力扣（LeetCode）

結論

通過使用哈希集合來記錄已經出現過的數，我們可以有效地判斷一個數是否為快樂數。這種方法簡單而高效，能夠處理可能的無限循環問題。

寫在最后
如果你覺得有幫助到你，請給題解點個贊和收藏，讓更多的人看到呀~

也歡迎你關注我，解鎖更多圖解 LeetCode，一起玩轉數據結構與算法！

我是luckilyil，我們下次見！