202. 快樂數
難度：簡單
題目
編寫一個算法來判斷一個數 n 是不是快樂數。
「快樂數」 定義為：
- 對于一個正整數，每一次將該數替換為它每個位置上的數字的平方和。
- 然后重復這個過程直到這個數變為 1，也可能是 無限循環 但始終變不到 1。
- 如果這個過程 結果為 1，那么這個數就是快樂數。
如果 n 是 快樂數 就返回 true ；不是，則返回 false 。
示例 1：
輸入：n = 19
輸出：true
解釋：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
示例 2：
輸入：n = 2
輸出：false
提示：
1 <= n <= 23^1 - 1
個人題解
方法一：模擬
一開始想先寫出最簡單的方式，嘗試打表找規律，打表發現沒規律0.0
思路：
- 本題主要是要解決
無限循環的問題，用 hashSet 容器存儲已經考慮過的數字便可得到，當再次算回容器中數字便表示將會 無限循環，返回 false 即可
class Solution {public boolean isHappy(int n) {HashSet<Integer> set = new HashSet<>();set.add(n);while (n != 1) {int sum = 0;while (n >= 10) {sum += (int) Math.pow(n % 10, 2);n /= 10;}n = sum + n * n;if (set.contains(n)) {return false;}set.add(n);}return true;}
}
復雜度分析
- 時間復雜度：O(log n)
- 空間復雜度：O(log n)
官方題解
方法一：用哈希集合檢測循環
class Solution {private int getNext(int n) {int totalSum = 0;while (n > 0) {int d = n % 10;n = n / 10;totalSum += d * d;}return totalSum;}public boolean isHappy(int n) {Set<Integer> seen = new HashSet<>();while (n != 1 && !seen.contains(n)) {seen.add(n);n = getNext(n);}return n == 1;}
}
復雜度分析
- 時間復雜度：O(log n)
- 空間復雜度：O(log n)
方法二：快慢指針法
通過反復調用 getNext(n) 得到的鏈是一個隱式的鏈表。隱式意味著我們沒有實際的鏈表節點和指針，但數據仍然形成鏈表結構。起始數字是鏈表的頭 “節點”，鏈中的所有其他數字都是節點。next 指針是通過調用 getNext(n) 函數獲得。
意識到我們實際有個鏈表，那么這個問題就可以轉換為檢測一個鏈表是否有環。因此我們在這里可以使用弗洛伊德循環查找算法。這個算法是兩個奔跑選手，一個跑的快，一個跑得慢。在龜兔賽跑的寓言中，跑的慢的稱為 “烏龜”，跑得快的稱為 “兔子”。
不管烏龜和兔子在循環中從哪里開始，它們最終都會相遇。這是因為兔子每走一步就向烏龜靠近一個節點（在它們的移動方向上）。
我們不是只跟蹤鏈表中的一個值，而是跟蹤兩個值，稱為快跑者和慢跑者。在算法的每一步中，慢速在鏈表中前進 1 個節點，快跑者前進 2 個節點（對 getNext(n) 函數的嵌套調用。
如果 n 是一個快樂數，即沒有循環，那么快跑者最終會比慢跑者先到達數字 1
如果 n 不是一個快樂數，那么最終快跑者和慢跑者將在同一個數字上相遇。
class Solution {public int getNext(int n) {int totalSum = 0;while (n > 0) {int d = n % 10;n = n / 10;totalSum += d * d;}return totalSum;}public boolean isHappy(int n) {int slowRunner = n;int fastRunner = getNext(n);while (fastRunner != 1 && slowRunner != fastRunner) {slowRunner = getNext(slowRunner);fastRunner = getNext(getNext(fastRunner));}return fastRunner == 1;}
}
-
復雜度分析
- 時間復雜度：O(log n)
- 空間復雜度：O(1)
作者：力扣官方題解
鏈接：https://leetcode.cn/problems/happy-number/solutions/224894/kuai-le-shu-by-leetcode-solution/
來源：力扣（LeetCode）
著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。
