202.快乐数

难度：简单

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

「快乐数」 定义为：

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

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

示例 1：

输入：n = 19
输出：true
解释：
1^(2) + 9^(2) = 82
8^(2) + 2^(2) = 68
6^(2) + 8^(2) = 100
1^(2) + 0^(2) + 0^(2) = 1

示例 2：

输入：n = 2
输出：false

提示：

1 <= n <= 2^(31) - 1

解题思路

使用哈希集合，来判断这个 求和的结果 是否重复出现，如果重复了就是返回 false，否则就一直找，直到求和的结果为 1

还有一个难点就是求和的过程，需要熟悉取一个数各个位上的值的操作

我的代码（哈希集合）

java

public boolean isHappy(int n) {
    // 使用HashSet来记录所有出现过的数字
    Set<Integer> record = new HashSet<>();
    // 当n不为1且n没有在之前出现过
    while (n != 1 && !record.contains(n)) {
        record.add(n);
        int res = 0;
        // 计算n的每一位数字的平方和
        while (n > 0) {
            int temp = n % 10;// 获取n的最后一位数字
            res += temp * temp;// 计算这个数字的平方并加到res中
            n /= 10;// 移除n的最后一位数字
        }
        n = res;// 更新n为其每位数的平方和
    }
    // 如果循环结束时n为1，则是快乐数，否则不是
    return n == 1;
}

时间复杂度: O(logn)

空间复杂度: O(logn)

快慢指针法

思路概述

上述算法中，通过反复对 res 进行求值，我们得到了 record 哈希集合，如果令此集合有序的话，不难看出此集合是一个隐式的链表。

隐式意味着我们虽然没有实际的链表节点和指针，但数据仍然形成了链表结构。

那么这个问题就转换为了：检测一个链表是否有环。

因此我们在这里可以使用 快慢指针法。

仿照 142 题的做法，我们使用两个指针，慢指针每步走一个节点，快指针每步走两个节点。

如果 n 是一个快乐数，说明链表无环，那么两个指针只存在一种相遇的情况：两个指针最后都指向数字 1，且一直停留在 1。

如果 n 不是一个快乐数，说明链表有环，那么当两个指针无论何时相遇，两个指针都不会指向 1。

代码展示

java

public boolean isHappy(int n) {
    // 使用快慢指针检测数字序列中的循环
    int slow = n;
    int fast = getNext(n);
    while (slow != fast) {
        slow = getNext(slow); // 慢指针每次移动一步
        fast = getNext(getNext(fast)); // 快指针每次移动两步
    }
    // 如果快指针到达1，则为快乐数
    return fast == 1;
}

public int getNext(int n) {
    int res = 0;
    while (n > 0) {
        int temp = n % 10;
        res += temp * temp; // 计算每位数字的平方和
        n /= 10;
    }
    return res;
}

时间复杂度: O(logn)

空间复杂度: O(1)

总结

遇到环形链表问题就使用快慢指针法，要形成一种条件反射。

202.快乐数 ​

解题思路 ​

我的代码（哈希集合） ​

快慢指针法 ​

思路概述 ​

代码展示 ​

总结 ​