[数据结构与算法]leetcode 202. 快乐数（哈希表）

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
如果这个过程 结果为 1，那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

示例 1：
输入：n = 19
输出：true
解释：
1² + 9² = 82
8² + 2² = 68
6² + 8² = 100
1² + 0² + 0² = 1

示例 2：
输入：n = 2
输出：false

提示：

1 <= n <= 2³¹ - 1

引用一下，因为说的很对。

一开始想到的代码如下：

思路是：用一个数组来统计其中是否有循环，如果一个数出现一次就给数组中对应的值加一，如果一个数是快乐数，是不会有循环的，否则一定会进入一个循环。
所以，如果数组计数中有大于1的数，就说明进入了循环，则不是快乐数，返回false。

class Solution {
public:
    bool isHappy(int n) {
        int a[100001]={0};
        memset(a,0,sizeof(a));
        int he=0,m=n;
        while(1){
            he=0;
            while(m){
                he+=((m%10)*(m%10));
                m/=10;
            }
            if(he==1)
                return true;
            a[he]++;
            if(a[he]>1)  //如果一个数出现了不止一次，说明有循环，返回false就可以了
                return false;
            m=he;
        }
        return false;
    }
};

因为最近学习了哈希表，而且这个题的分类就是在哈希表中，第一次代码的a数组就是用来计数的，那么哈希表也可以这么用，因为哈希表中也不允许有相同的键值，所以我们每次把计算出来的数据当作键值存入哈希表中，然后在哈希表中寻找是否有相同的键值，如果有，则说明进入了循环，否则就没有。

class Solution {
public:
    bool isHappy(int n) {
        unordered_map<int,int> hashtable;
        hashtable.insert(make_pair(n,0));//将n本身存入哈希表中，也是需要判断的，value值是多少都没关系，根本用不到
        int he=0;
        while(1){
            he=0;
            while(n){
                he+=((n%10)*(n%10));
                n/=10;
            }
            if(he==1)
                return true;
            if(hashtable.find(he)!=hashtable.end())//如果找到了一个重复的，说明其中有循环，就不是快乐数
                return false;
            else//放入哈希表中为下一次判断准备
                hashtable.insert(make_pair(he,0));
            n=he;
        }
        return false;
    }
};

在我看了评论之后觉得很对，又把代码简化了一下，这样只要出现这些数字中的任何一个就可以不用在继续算下去了。

class Solution {
public:
    bool isHappy(int n) {
        int he=0;
        while(1){
            he=0;
            while(n){
                he+=((n%10)*(n%10));
                n/=10;
            }
            if(he==1)
                return true;
            if(he==4||he==16||he==37||he==58||he==89||he==145||he==42||he==20)
                return false;//特殊判断，如果不是快乐数一定会进入这个循环
            n=he;
        }
        return false;
    }
};

看了评论之后突然又发现一个事，就是题中说的是差的绝对值小于k，但是如果是差是负数的话肯定也小于k，而且题中说了 k 是大于等于0的，那么如果差是正数的时候小于k，负数也必定小于，所以上面代码不加 abs() 函数也可以过。