202.快乐数

发表于： 分类于：
字数： 661 阅读：≈ 2分钟

😹 202.快乐数

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

「快乐数」 定义为：

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

思路

基本思想

基本思想就是对一个数分离各个位上的数并平方求和，如果不是1就继续分离并求和，直到遇到1，但是分离并求和的过程中肯定不是一直分离下去，一旦遇到之前求和过的结果，肯定会陷入死循环，此时这个数肯定不是快乐数

所以需要将问题分解，首先求当前数的分离之后的平方和结果，判断这个数是否之前出现过，这一步需要借助一个容器存储之前出现的所有结果，这里使用unordered_set，因为他的存储效率和查询速度在这里最适合

将问题分解之后就是简单的代码了

执行流程

  1. 定义分离求平方和的函数
  2. 对当前的数求平方和
  3. 判断平方和是否为1，是的话就是快乐数，返回true
  4. 不是的话需要判断这个结果之前是否出现过
  5. 出现过说明陷入死循环，直接返回false
  6. 没出现过继续对当前的数分离求平方和

代码

根据以上分析，得出以下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
public:
    bool isHappy(int n) {
        unordered_set<int> uset;
        while(1){
            //计算当前的sum
            int sum=getSum(n);
            if(sum==1)
                return true;
            else{//不等于1判断是否需要计算新的sum
                if(uset.find(sum)!=uset.end())
                    return false;
                else    
                    uset.insert(sum);
            }
            //重新计算新的sum
            n=sum;
        }
    }
    int getSum(int n){
        int sum=0;
        while(n){
            sum+=(n%10)*(n%10);
            n/=10;
        }
        return sum;
    }
};

总结

主要是知道如何将一个不知道位数的数的各个位分离下来，并且知道当前的平方和在之前出现过则说明陷入死循环，当前的数一定不是快乐数