题目：
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
链接： http://leetcode.com/problemset/algorithms/
题解：
判断一个数字是否为Happy Number。这道题跟求无限循环小数很像，最好维护一个HashSet，假如遇见重复，则返回false。否则替换n为digits square root sum，当n == 1时循环结束返回true。
Time Complexity - O(n)， Space Complexity - O(n)。
public class Solution {
public boolean isHappy(int n) {
if(n <= 0)
return false;
Set<Integer> set = new HashSet<>();
while(n != 1) {
if(set.contains(n))
return false;
else {
set.add(n);
n = getSquareSumOfDigits(n);
}
}
return true;
}
private int getSquareSumOfDigits(int n) {
int res = 0;
while(n > 0) {
res += (n % 10) * (n % 10);
n /= 10;
}
return res;
}
}
二刷：
就是在i != 1的情况对n进行处理，使用一个Set来保存出现过的数字，假如重复则出现循环，这时候我们return false。否则跳出循环的时候n == 1，我们return true。
Java:
Time Complexity - O(n)， Space Complexity - O(n)。 时间复杂度和空间复杂度需要用数学公式来推算。这公式是什么我现在也不知道。
public class Solution {
public boolean isHappy(int n) {
if (n < 1) {
return false;
}
Set<Integer> set = new HashSet<>();
set.add(n);
int newNum = 0;
while (n != 1) {
while (n != 0) {
newNum += (n % 10) * (n % 10);
n /= 10;
}
if (!set.add(newNum)) {
return false;
}
n = newNum;
newNum = 0;
}
return true;
}
}
题外话： 今天试了一下Coursera的Crytography I，感觉难度比较大，需要很好的概率知识。做作业的时候参考了别人在github上写的Python代码，好简洁。自己也要好好练起来。又发现了几个比较优美的算法课件，都是来自Kevin Wayne，要好好看一看。其实至今为止自己收集了很多资料，包括书籍，课件，Source Code， Video等等，但总觉得没准备好，心里没底，也许是因为这leetcode到现在第一遍还没完成吧。说不定真刷到了5遍7遍的，融会贯通了以后，才会安心一点。
三刷:
Java:
public class Solution {
public boolean isHappy(int n) {
if (n < 1) {
return false;
}
Set<Integer> set = new HashSet<>();
set.add(n);
while (n != 1) {
n = getSquareSum(n);
if (!set.add(n)) {
return false;
}
}
return true;
}
private int getSquareSum(int num) {
int res = 0;
while (num != 0) {
int remainder = num % 10;
res += remainder * remainder;
num /= 10;
}
return res;
}
}
Update:
public class Solution {
public boolean isHappy(int n) {
if (n < 1) return false;
Set<Integer> set = new HashSet<>();
while (n != 1) {
int num = 0;
while (n != 0) {
num += (n % 10) * (n % 10);
n /= 10;
}
if (!set.add(num)) return false;
n = num;
}
return true;
}
}
更好的解可以把Space Complexity 简化到 O(1)，使用 fast / slow pointer进行Cycle Detection的思路，很巧妙。 更奇妙的是运行时间也减少了。
public class Solution {
public boolean isHappy(int n) {
if (n < 1) {
return false;
}
int x = n, y = getDigitSquareSum(n);
while (x != y) {
x = getDigitSquareSum(x);
y = getDigitSquareSum(getDigitSquareSum(y));
}
return x == 1;
}
private int getDigitSquareSum(int n) {
int res = 0;
while (n > 0) {
int curDigit = n % 10;
res += curDigit * curDigit;
n /= 10;
}
return res;
}
}
Update:
public class Solution {
public boolean isHappy(int n) {
if (n < 1) return false;
int slow = n, fast = getSquareSum(n);
while (slow != fast) {
slow = getSquareSum(slow);
fast = getSquareSum(getSquareSum(fast));
}
return slow == 1;
}
private int getSquareSum(int n) {
int num = 0;
while (n != 0) {
num += (n % 10) * (n % 10);
n /= 10;
}
return num;
}
}
四刷:
class Solution {
Set<Integer> set = new HashSet<>();
public boolean isHappy(int n) {
if (n < 1) return false;
if (set.contains(n)) return n == 1;
else set.add(n);
return isHappy(getSquareSum(n));
}
private int getSquareSum(int n) {
int num = 0;
while (n != 0) {
num += (n % 10) * (n % 10);
n /= 10;
}
return num;
}
}
Reference:
https://leetcode.com/discuss/33055/my-solution-in-c-o-1-space-and-no-magic-math-property-involved
https://leetcode.com/discuss/71625/explanation-those-posted-algorithms-mathematically-valid
https://leetcode.com/discuss/33349/o-1-space-java-solution
http://www.cs.princeton.edu/courses/archive/spring13/cos423/lectures.php
http://www.cs.princeton.edu/courses/archive/fall12/cos226/lectures.php