Happy Number

浏览数：41 / 时间：2015年06月11日

题目链接：https://leetcode.com/problems/happy-number/

这道题看上去很简单，如果用hashtable的话，不少童鞋应该都能做出来。只要想明白一件事儿，循环结束的条件：要么当前的数字为1，要么当前的数字曾经出现过。（至于为什么一定会出现循环，额，数学家们已有讨论，可以参考这个链接里的内容和其他链接 http://mathworld.wolfram.com/HappyNumber.html。不过简单的说，就是按这种规律一直运算，结果总会出现0, 1, 4, 16, 20, 37, 42, 58, 89, 145 这十个数中的一个）好了，这样子逻辑和明了，代码如下。

 1 class Solution {
 2 public:
 3     bool isHappy(int n) {
 4         unordered_set<int> visited;
 5         int cur = n;
 6         while(!(cur == 1 || visited.find(cur) != visited.end())) {
 7             visited.insert(cur);
 8             int temp = 0;
 9             while(cur) {
10                 temp += (cur % 10) * (cur % 10);
11                 cur = cur / 10;
12             }
13             cur = temp;
14         }
15         return cur == 1;
16     }
17 };

View Code

但其实这道题还有一种不需要hashtable的方法，就是使用Floyd Cycle detection algorithm。相信很多人在做linkedlist cycle detection的时候都用过这个方法，仔细一想，这个方法确实可以用在这道题上哦。这个方法是这样的，设置两个指针，slow和fast，然后每次slow走一步，fast走两步，（在这道题里就是slow做一次求平方和的运算，fast做两次），直到fast与slow相等或者fast为1为止。对于这个算法的简单证明大家可参考wiki：http://en.wikipedia.org/wiki/Cycle_detection或者直接找原paper。对于这个算法在linkedlist中的解释，可以参考这个博文：http://www.cnblogs.com/hiddenfox/p/3408931.html

 1 class Solution {
 2 public:
 3     bool isHappy(int n) {
 4         int slow = n;
 5         int fast = sqrtSum(n);
 6         while(fast != 1 && slow != fast) {
 7             fast = sqrtSum(fast);
 8             if(fast != 1 && slow != fast) {
 9                 fast = sqrtSum(fast);
10                 slow = sqrtSum(slow);
11             }
12         }
13         return fast == 1;
14     }
15     
16     int sqrtSum(int n) {
17         int sum = 0;
18         while(n) {
19             sum += (n % 10) * (n % 10);
20             n = n / 10;
21         }
22         return sum;
23     }
24 };