我的LeetCode：https://leetcode-cn.com/u/ituring/

我的LeetCode刷題源碼[GitHub]：https://github.com/izhoujie/Algorithmcii

LeetCode 202. 快樂數

題目

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

「快樂數」定義為：對於一個正整數，每一次將該數替換為它每個位置上的數字的平方和，然後重覆這個過程直到這個數變為 1，也可能是 無限迴圈 但始終變不到 1。如果 可以變為  1，那麼這個數就是快樂數。

如果 n 是快樂數就返回 True ；不是，則返回 False 。

示例：

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

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/happy-number
著作權歸領扣網路所有。商業轉載請聯繫官方授權，非商業轉載請註明出處。

解題思路

• 比較容易想到的是順序計算並判斷，因為可能存在迴圈，所以再額外需要set來保存計算過的值用以後續驗重；
• 另一種思路是快慢指針，因為快樂數的計算最終只會有兩種結果：
  • 進入1迴圈；
  • 進入某迴圈鏈無終止迴圈；
• 純數學分析規律，對上面思路更清晰化的解釋，即最終的迴圈結果：
  • 進入1迴圈；
  • 進入 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 迴圈鏈；

純數學的分析優化的是非快樂數的迴圈鏈，有了鏈就可以直接建立速查表避免了邊計算邊存數

思路1-按步驟計算用set保存每次計算結果；

演算法複雜度:

• 時間複雜度： $ {\color{Magenta}{\Omicron\left(logn\right)}} $
• 空間複雜度： $ {\color{Magenta}{\Omicron\left(logn\right)}} $

思路2-建立快慢指針

演算法複雜度:

• 時間複雜度： $ {\color{Magenta}{\Omicron\left(logn\right)}} $
• 空間複雜度： $ {\color{Magenta}{\Omicron\left(1\right)}} $

思路2-數學分析規律建立速查表

演算法複雜度:

• 時間複雜度： $ {\color{Magenta}{\Omicron\left(logn\right)}} $
• 空間複雜度： $ {\color{Magenta}{\Omicron\left(1\right)}} $

演算法源碼示例

package leetcode;

import java.util.Arrays;
import java.util.HashSet;

/**
 * @author ZhouJie
 * @date 2020年4月30日 下午10:24:08 
 * @Description: 202. 快樂數
 *
 */
public class LeetCode_0202 {

}

class Solution_0202 {
	/**
	 * @author: ZhouJie
	 * @date: 2020年4月30日 下午10:53:37 
	 * @param: @param n
	 * @param: @return
	 * @return: int
	 * @Description: 快樂數計算
	 *
	 */
	private int happyHelper(int n) {
		int temp = 0;
		while (n > 0) {
			temp += (n % 10) * (n % 10);
			n /= 10;
		}
		return temp;
	}

	/**
	 * @author: ZhouJie
	 * @date: 2020年4月30日 下午10:24:31 
	 * @param: @param n
	 * @param: @return
	 * @return: boolean
	 * @Description: 1-每次計算後，若為1則是快樂數，否則看是否在set，在則不是快樂數，不在則繼續迴圈計算；（迴圈有限的，所以代碼最後的return其實永遠不會執行）
	 *
	 */
	public boolean isHappy_1(int n) {
		HashSet<Integer> noHappy = new HashSet<Integer>();
		while (n != 1 && !noHappy.contains(n)) {
			noHappy.add(n);
			n = happyHelper(n);
		}
		return n == 1;
	}

	/**
	 * @author: ZhouJie
	 * @date: 2020年4月30日 下午10:36:06 
	 * @param: @param n
	 * @param: @return
	 * @return: boolean
	 * @Description: 2-快慢指針；原理：若為1退出迴圈；若有環，則快指針最終會追上慢指針（多一個迴圈）；
	 *
	 */
	public boolean isHappy_2(int n) {
		int slow = n, fast = happyHelper(n);
		while (slow != fast) {
			if (slow == 1 || fast == 1) {
				return true;
			} else {
				slow = happyHelper(slow);
				fast = happyHelper(happyHelper(fast));
			}
		}
		return slow == 1;
	}

	/**
	 * @author: ZhouJie
	 * @date: 2020年4月30日 下午10:45:26 
	 * @param: @param n
	 * @param: @return
	 * @return: boolean
	 * @Description: 3-數學規律，任意數最終會進入兩個迴圈，一個是：1自身迴圈，一個是： 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4
	 *
	 */
	public boolean isHappy_3(int n) {
		// 建立不快樂數的最終迴圈自查表
		HashSet<Integer> noHappy = new HashSet<Integer>(Arrays.asList(4, 16, 37, 58, 89, 145, 42, 20));
		while (n != 1 && !noHappy.contains(n)) {
			n = happyHelper(n);
		}
		return n == 1;
	}
}