leetcode-202.快乐数

数学问题

---

题目详情

编写一个算法来判断一个数 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就返回true,找到存过的平方和就返回false

我的代码：

class Solution 
{
    
public:
    // 辅函数 求各个数位平方和
    int getSum(int n)
    {
    
        int sum = 0;
        while (n)
        {
    
            sum += (n % 10) * (n % 10);
            n /= 10;
        }
        return sum;
    }
    // 主函数
    bool isHappy(int n) 
    {
    
        int sum = 0;
        unordered_set<int> set;
        while (true)
        {
    
            sum = getSum(n);
            if (sum == 1) return true; // 循环找到1就返回true
            // 循环找到重复就返回false
            if (set.find(sum) != set.end()) return false;
            //否则存入sum后更新n继续循环
            set.insert(sum);
            n = sum;
        }
    }
};

在写第一种方法的时候我们可以发现,我们其实是在一个循环中不断寻找指定元素,我们可以联想到在循环链表中的寻找元素的一种好方法:快慢指针法!
即定义慢指针slow慢指针初始在第一个节点上,快指针fast初始在第二个节点上,然后slow每次走一步,fast每次走两步,直到fast找到1(true)或者fast和slow相遇(没找到死循环false) 代码如下:

class Solution 
{
    
public:
    // 辅函数 求各个数位平方和
    int getSum(int n)
    {
    
        int sum = 0;
        while (n)
        {
    
            sum += (n % 10) * (n % 10);
            n /= 10;
        }
        return sum;
    }
    // 主函数
    bool isHappy(int n) 
    {
    
        //初始化
        int slow = n;
        int fast = getSum(n);
        // 没找到1 不相遇 就循环
        while (fast != 1 && slow != fast)
        {
    
            slow = getSum(slow);//执行一步
            fast = getSum(getSum(fast));//执行两步
        }
        return fast == 1; //最后跳出循环看fast是不是1
        
    }
};

最后还有一种方法可以通过数学规律来解决,当一个数的各位平方和最后无法循环成1,那么必定会掉入循环:4→16→37→58→89→145→42→20→4
根据这个规律我们可以写出下面代码:

class Solution 
{
    
public:
    // 辅函数 求各个数位平方和
    int getSum(int n)
    {
    
        int sum = 0;
        while (n)
        {
    
            sum += (n % 10) * (n % 10);
            n /= 10;
        }
        return sum;
    }
    unordered_set<int> set{
    4, 16, 37, 58, 89, 145, 42, 20};//初始化
    // 主函数
    bool isHappy(int n) 
    {
       // 没找到1 set中没找到(没掉入死循环)
        while (n != 1 && set.find(n) == set.end()) 
        {
    
            n = getSum(n); //就继续
        }
        return n == 1;
        
    }
};