1.題目

編寫一個算法來判斷一個數 n 是不是快樂數。

「快樂數」?定義為：

• 對于一個正整數，每一次將該數替換為它每個位置上的數字的平方和。
• 然后重復這個過程直到這個數變為 1，也可能是 無限循環 但始終變不到 1。
• 如果這個過程 結果為?1，那么這個數就是快樂數。

如果 n 是 快樂數 就返回 true ；不是，則返回 false 。

2.示例

示例 1：

輸入：n = 19
輸出：true
解釋：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

示例 2：

輸入：n = 2
輸出：false

---

3.思路

快慢指針法
???????? 如果觀察規律可以發現如果不是快樂數則會一直陷入一個循環之中。如圖

此時可以定義兩個指針，一個快指針，一個慢指針。快指針一次能走兩格，慢指針只能一次走一格 。但是兩者最后都會遇到，如果快指針先遇到1則結束循環或者龜兔兩者相遇，此時就需要判斷兩者的數字，如果遇到的值并不是1，那么就說明不存在快樂數。

4.代碼

LeetCode代碼

class Solution {public boolean isHappy(int n) {int slowPointer = n;int quickerPointer = getNext(n);while (quickerPointer!=1 &&quickerPointer!=slowPointer){quickerPointer = getNext(getNext(quickerPointer));slowPointer = getNext(slowPointer);}return quickerPointer==1;}public int getNext(int n){int sum =0;while (n>0){sum += Math.pow(n%10,2);n = n/10;}return  sum;}
}

時間復雜度O(logn)空間復雜度O(1)

具體案例代碼：

package LeetCode19;public class javaDemo {public static void main(String[] args) {boolean flag ;int n = 4;
//        烏龜int slowPointer = n;
//        兔子int quickerPointer = getNext(n);
//        當兔子不是1或者兩者還未相遇的時候則兩者繼續前進while (quickerPointer!=1 &&quickerPointer!=slowPointer){quickerPointer = getNext(getNext(quickerPointer));slowPointer = getNext(slowPointer);}
//        當兔子遇到1或者龜兔相遇時候判斷龜兔相遇的時候值是否為1flag = quickerPointer==1;
//        輸出結果System.out.println(flag);}
//    計算每一個的數字的平方和public static  int getNext(int n){
//        定義累計和int sum =0;while (n>0){sum += Math.pow(n%10,2);n = n/10;}return  sum;}
}

---

會了？試試挑戰下一題！?（＾?＾●）ﾉｼ （●′?｀）?

LeetCode150道面試經典題-- 匯總區間(簡單)_Alphamilk的博客-CSDN博客