leetcode 202. Happy Number

1.题目

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

写一个算法，确定一个数字是否是快乐数字，有关快乐数字的定义可以参考百度百科 快乐数字  

2.算法

我们从百度百科上发现，不是快乐数的数称为不快乐数（unhappy number），所有不快乐数的数位平方和计算，最後都会进入 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 的循环中。题目中要求是确定是快乐数字就返回true，不是就返回false，所以我们用hashset放平方后的数的和，如果出现循环就不是快乐数

    public boolean isHappy(int n) {        // Write your code here    if (n <= 0)	{		return false;	}	HashSet<Integer> hs = new HashSet<>();	hs.add(n);	while (n != 1)	{		int sum = calcu(n);		if (hs.contains(sum))		{			return false;		}		hs.add(sum);		n = sum;	}	return true;}PRivate int calcu(int n) {	// TODO Auto-generated method stub	int sum = 0;	while (n != 0)	{		sum += Math.pow(n % 10, 2);		n /= 10;	}	return sum;}
，其实我们可以这样做来减小空间复杂度，我们用一个快慢指针，如果循环，快慢指针就会在某一个地方相等
    public boolean isHappy(int n) {        // Write your code here    if (n <= 0)	{		return false;	}	int slow, fast;	slow = fast = n;	do {	    slow = calcu(slow);	    fast = calcu(fast);	    fast = calcu(fast);	    if (fast == 1)	    {	        return true;	    }	} while (fast != slow);	return false;}private int calcu(int n) {	// TODO Auto-generated method stub	int sum = 0;	while (n != 0)	{		sum += Math.pow(n % 10, 2);		n /= 10;	}	return sum;}