leetcode-202-Happy Number

题目描述：

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

• 1^2 + 9^2 = 82
• 8^2 + 2^2 = 68
• 6^2 + 8^2 = 100
• 1^2 + 0^2 + 0^2 = 1

给大家翻译一下，更容易看明白。一个正数，比如19，拆开两位，求其平方和，得到1^2+9^2=82。接着82拆开两位，得到8^2+2^2=68……如此进行下去，直到最后能出现一个1，那么就说明这是一个happy number。如果陷入了循环，总是没有出现1，那么就不是happy number。

要完成的函数：

bool isHappy(int n)

说明：

1、陷入无穷尽的循环之中，那么它就不是happy number。我们先来看一下85这个数。

85　　8^2+5^2=89

89　　8^2+9^2=145

145　 1^2+4^2+5^2=42

42　　4^2+2^2=20

20　　2^2+0^2=4

4　　  4^2=16

16　　1^2+6^2=37

37　　3^2+7^2=58

58　　5^2+8^2=89

89　　8^2+9^2=145

我们可以看到85不是一个happy number，因为在85的迭代过程中，出现了不包括1的循环，在89之后还是会继续重复。

所以根据上述推理，我们能写出这样的代码。

bool isHappy(int n) 
    {
        set<int>s1;//使用集合来存储已经出现过的数
        int result=0;
        s1.insert(n);
        while(n!=1)
        {
            result=0;//记得要清零
            while(n!=0)
            {
                result+=(n%10)*(n%10);
                n/=10;    
            }
            n=result;
            if(s1.count(n)) 
                return false;
            else
                s1.insert(n);
        }
        return true;
    }

代码很简洁，实测4ms，beats 85.26% of cpp submissions。

2、日常逛discuss看大神做法。大神果然提出了好多理论。

提出了数学原理解释，笔者没有看明白……感觉表达得不是很细致，一些变量没有说明究竟指的是什么。

https://leetcode.com/problems/happy-number/discuss/56919/Explanation-of-why-those-posted-algorithms-are-mathematically-valid

提出了一些充分条件，当满足这些条件可以判断为非happy number。

https://leetcode.com/problems/happy-number/discuss/56918/all-you-need-to-know-about-testing-happy-number

根据一些充分条件，比如在循环过程中出现result=4，那么这必定是一个非happy number，我们也可以构造一个不用set的代码来实现。

另外，根据闭区间[2,6]上面的数都是非happy number的结论，我们也可以构造出如下代码：

bool isHappy(int n) 
{
    while(n>6)
    {
        int next = 0;
        while(n){next+=(n%10)*(n%10); n/=10;}
        n = next;
    }
    return n==1;
}

这份代码更省时，不需要跑完一整个循环检测到出现重复的数才停下，只需要检测到[2,6]上面的数就可以停下了。同时，避免使用set的空间以及set的一些运算。

实测3ms，beats 99.37% of cpp submissions。

本代码来自leetcode用户@orou0591。侵删。