leetcode 202. 快乐数（哈希表）

àì夳堔傛蜴生んèń 2023-09-26 11:34 20阅读 0赞

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

「快乐数」 定义为：

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

示例 1：  
输入：n = 19  
输出：true  
解释：  
12 \+ 92 = 82  
82 \+ 22 = 68  
62 \+ 82 = 100  
12 \+ 02 \+ 02 = 1

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

提示：

1 <= n <= 231 \- 1

> 引用一下，因为说的很对。  
>   
> 
> 
> ![在这里插入图片描述][1a75ff62ba614ae3b21384deefeedd9b.png]

一开始想到的代码如下：

思路是：用一个数组来统计其中是否有循环，如果一个数出现一次就给数组中对应的值加一，如果一个数是快乐数，是不会有循环的，否则一定会进入一个循环。  
所以，如果数组计数中有大于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;
        }
    };

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

![在这里插入图片描述][81a524dc675a4676a9155d8ad7681ad6.png]

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() 函数也可以过。

[1a75ff62ba614ae3b21384deefeedd9b.png]: https://img-blog.csdnimg.cn/1a75ff62ba614ae3b21384deefeedd9b.png
[81a524dc675a4676a9155d8ad7681ad6.png]: https://img-blog.csdnimg.cn/81a524dc675a4676a9155d8ad7681ad6.png