leetcode 202. 快乐数 | 简单难度

1. 题目详情

编写一个算法来判断一个数 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

1. 原题链接

leetcode 202. 快乐数

2. 基础框架

● Cpp代码框架

class Solution {
public:
    bool isHappy(int n) {

    }
};

2. 解题思路

1. 题目分析

$(1)$ 判断一个整数n是否是快乐数：用该数的每个位置的平方和作为新值，一直进行下去，如果最终能得到1就返回false，反之无限循环就返回fasle。
$(2)$ 本题出现的无限循环指的是一个数变成一系列不同的数，直到又变成自身，然后循环往复，这个无限循环中的每个数是确定的。
$(3)$

2. 算法原理

$(1)$ 首先想到的是一种解法：
模拟数n的变化过程，同时使用哈希表记录每次变化的新数new_n，判断每次变化的新数new_n是否是1：
如果是1就是快乐数；
如果不是1就在哈希表中查找new_n自身是否已经出现过了：
————如果在哈希表中找到了自身就说明new_n出现过了，且new_n不是1，说明已经进入无限循环了，即数n一定不是快乐数；
继续变化得到下一个new_n，循环判断。

$(2)$ 第二种解法：快慢指针算法
你知道判断链表是否有环这道题是如何做的呢？
链表是否有环这道题使用了快慢双指针，慢slow每次走1步，快指针fast每次走两步，如果链表有环，最终slow和fast会相遇即slow==fast。

本题中n数n的变化也可以转换为与求链表是否有环中相类似的情况：
对于数n，
情况1：不是快乐数，n经过一系列数的变化最终会变回已经出现的数，然后又从从已经出现得数开始再继续变化，形成无限循环，形象的说就是进入了环；

情况2：如是快乐数，n经过一系列数的变化最终会变到1，而1如果继续变化，那么会一直会回1本身，此时也可以说进入了无限循环，只不过这个无限循环中变化的数都是1本身；

上面两种情况就可以合并为一种情况：数n经过一系列变化，进入循环，快指针fast一次走2步（这里的走两步是形象的说法，实际上表示的是fast变化了两次），慢指针slow一次走1步，最终会进入环，在环中快慢指针最终一定会相遇：
判断两者的值是否相等，相等时说明相遇了，
————然后判断快慢指针的值是否是1：
————————如果是1则是快乐数；反之不是快乐数。

3. 时间复杂度

为了使用n描述时间复杂度，下文描述数n时将会换成数num。

第一种解法 模拟：$O(n)$，但借助了额外n的空间。

数num的变化长度是确定的，不管是变为1还是进入无限循环。
每次都会记录数num的变化，所以相当于遍历了一遍num的所有变化情况。

第二种解法 快慢指针： $O(n)$

3. 代码实现

解法一：模拟

class Solution {
public:
    int change(int val){
        int ret = 0;
        while(val){
            int mod = val % 10;
            ret += mod * mod;
            val /= 10;
        }
        return ret;
    }
    bool isHappy(int n) {
        unordered_set<int> us;// 哈希表存储每次出现的新数

        // 模拟n的变化
        while(n != 1){
            if(us.find(n) != us.end()) return false;
            us.insert(n);
            n = change(n);
        }
        return true;
    }
};

解法二：快慢双指针

class Solution {
public:
    int change(int val){
        int newval = 0;
        while(val){
            int mod = val % 10;
            val /= 10;
            newval += mod * mod; 
        }
        return newval;
    }
    bool isHappy(int n) {
        int slow = n, fast = n;
        do{
            slow = change(slow);
            fast = change(fast);
            fast = change(fast);
        } while(slow != fast);
        return slow == 1;
    }
};

4. 知识与收获

$(1)$ 快慢双指针的应用中，判断是否有环链表是一道经典的题目，本题虽然表面上与其无关，但是在分析之后发现有很大的相关性，也就可以使用快慢指针思路解决了。

---

$The$ $End$