我的吉米城: [LeetCode] Happy Number 快樂數字 (No.202)

2016/7/22

[LeetCode] Happy Number 快樂數字 (No.202)

Write an algorithm to determine if a number is "happy".

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

Example: 19 is a happy number

12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

Ref: https://leetcode.com/problems/happy-number/

中文簡單說明：
給你一個數字，要你算算看這個數字是不是「快樂數字」！
而所謂的快樂數字，就是把一個數字拆成個、十、百、千…位數後，每個位數各自平方後相加，直到得到個位數為1的就是了。
不過要特別注意的是，這個數字有可能會無限迴圈的喔！像是數字4、5……

解法：
我的解法並不是最速解，不過是我自己想出來，認為我最容易閱讀的方式。
簡單來說，利用一個迴圈，做出該數字是否大於9的判斷後，把該數字轉成字元陣列後計算總和，如果總和只有個位數，則直接進入一個switch-case的判斷，其中只有1跟7會得到true，其他都是false。

而我查到的較快解，則是先建立一個HashSet放入數字，如果發現數字無法正常加入，代表有重覆，那就是進入了迴圈，直接回傳false；而沒有的話，就看看總和是否是一，不是的話就繼續計算。
Ref: https://discuss.leetcode.com/topic/25026/beat-90-fast-easy-understand-java-solution-with-brief-explanation/2

部份程式碼：

	public boolean isHappy(int n) {
	// 小於0就直接回FALSE
	if (n < 0) {
	return false;
	}
	// 大於10才去算，要不然就直接查是否是HAPPY NUMBER
	while (n > 9) {
	// 抓出SUM放到N中
	n = getSum(n);
	}
	return isHappyNumber(n);
	}
	private Integer getSum(Integer num) {
	Integer sum = 0;
	// 把數字轉成CHAR陣列後一個一個讀取並算出SUM
	for (Character eachChar : num.toString().toCharArray()) {
	Double eachNum = Double.valueOf(eachChar.toString());
	if (eachNum.intValue() != 0) {
	sum += (int) Math.pow(eachNum, 2d);
	}
	}
	return sum;
	}
	private boolean isHappyNumber(Integer num) {
	switch (num) {
	case 0:
	return false;
	case 1:
	return true;
	case 2:
	return false;
	case 3:
	return false;
	case 4:
	return false;
	case 5:
	return false;
	case 6:
	return false;
	case 7:
	return true;
	case 8:
	return false;
	case 9:
	return false;
	default:
	return false;
	}
	}
	// Ref:
	// https://discuss.leetcode.com/topic/25026/beat-90-fast-easy-understand-java-solution-with-brief-explanation/6
	public boolean isHappy2(int n) {
	// 用HASHSET來確認是否進入LOOP裡面
	Set<Integer> inLoop = new HashSet<Integer>();
	int squareSum, remain;
	while (inLoop.add(n)) {
	squareSum = 0;
	// 求得最新的REMAIN和SQUARESUM
	while (n > 0) {
	remain = n % 10;
	squareSum += remain * remain;
	n /= 10;
	}
	if (squareSum == 1)
	return true;
	else
	n = squareSum;
	}
	// 跳出WHILE迴圈代表進入了LOOP中，回傳FALSE
	return false;
	}