202-快乐数

Doublew2w大约 3 分钟

题目地址(202. 快乐数 - 力扣（LeetCode）)

https://leetcode.cn/problems/happy-number/

题目描述

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

「快乐数」 定义为：

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

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

示例 1：

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

示例 2：

输入：n = 2
输出：false

提示：

1 <= n <= 2³¹ - 1

前置知识

哈希表

思路

通过反复调用 getNext(n) 得到的链是一个隐式的链表。链中的所有其他数字都是节点。那问题就直接转换为「检测一个链表是否有环。」

定义两个指针slow和fast，slow在链表中前进 1 个节点，fast在链表前进 2 个节点（对 getNext(n) 函数的嵌套调用）。

如果 n 是快乐数，则就说明没有循环，fast 会先到 “1”
如果 n 不是快乐数，fast 和 slow 一定会在循环中。

关键点

将”快乐数“操作视为寻找下一个数，即看成一个链表

代码

语言支持：Java

Java Code:


class Solution {
    // 对于一个三位数来说，最大的平方和为 9^2+9^2+9^2 = 243
    // 对于一个四位数来说，最大的平方和为 81 + 81 + 81 + 81 = 324
    // 在继续往下后，4位数只会降到3位数，而不会无穷大

    public int getNext(int n) {
        int totalSum = 0;
        // 计算每一位的平方和
        while (n > 0) {
            int d = n % 10;
            n = n / 10;
            totalSum += d * d;
        }
        return totalSum;
    }

    public boolean isHappy(int n) {
        int slowRunner = n;
        int fastRunner = getNext(n);
        if(fastRunner == 1){
            return true;
        }
        // 快慢指针，不是快乐数，那么存在一个环使得算法无限循环
        // 在环中它们由于步速不一致，会相遇
        // 如果相遇，则说明不是快乐数
        // 如果是快乐数，最后会返回1
        while (slowRunner != fastRunner) {
            // slow 走一步, fast 走两步
            slowRunner = getNext(slowRunner);
            fastRunner = getNext(fastRunner);
            fastRunner = getNext(fastRunner);
        }
        return fastRunner == 1;
    }
}

复杂度分析

时间复杂度： $O(n)$
- 如果没有循环，那么fast将先到达 1，slow将到达链表中的一半。成本是 $O(2⋅logn)$ = $O(logn)$
- 一旦两个指针都在循环中，假设循环中有 k 个数字。如果他们的起点是相隔 k−1 的位置（这是他们可以开始的最远的距离），那么快跑者需要 k−1 步才能到达慢跑者，主操作不变，所以也是 O(logn)。
空间复杂度： $O(n)$