LeetCode 202.快乐数(简单)

haketest lv.1

发布时间：2023-09-08 03:03:16 237

题目描述:

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

「快乐数」定义为：

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

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

示例 1:

输入：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 <=

题目分析:

这道题可以使用一个 while 循环解决，但是还有一个更妙的解法，那就是使用我们之前讲过的快慢指针。我们可以把每个数字都想象成一个节点，就可以转化为环路检测，首先编写一个获取下个数字的方法，然后通过反复调用这个方法，我们就能得到一个隐式的链表。假设慢指针指向的是第一个数字，快指针指向的是第二个数字。通过循环，慢指针每次移动一步，而快指针每次移动两步，如果快慢指针相遇，则说明环路存在，说明 n 不是快乐数，直接退出循环。如果快指针最后指向的那个数刚好为 1 ，则说明 n 是快乐数。类似的快慢指针可以参考 LeetCode 142.环形链表II(中等) 。

题解:

执行用时: 1 ms

内存消耗: 35.1 MB

class Solution {
    // 获取下一个数的方法
    public int getNext(int n) {
        // 每位数平方之和
        int sum = 0;
        // 循环获取每位数的平方和
        while (n > 0) {
            int temp = n % 10;
            n = n / 10;
            sum += temp * temp;
        }
        // 平方和即为下一个数
        return sum;
    }

    public boolean isHappy(int n) {
        // 假设慢指针初始值为 n
        int slow = n;
        // 假设快指针初始值为 n 的下一个数
        int fast = getNext(n);
        // 循环，如果快慢指针相遇则证明有环
        while (fast != 1 && slow != fast) {
            // 慢指针前进一步
            slow = getNext(slow);
            // 快指针前进两步
            fast = getNext(getNext(fast));
        }
        // 如果快指针值为 1 则为返回 true
        return fast == 1;
    }
}

题目来源:力扣(LeetCode)

文章来源： https://blog.51cto.com/u_15891283/5886591

特别声明：以上内容（图片及文字）均为互联网收集或者用户上传发布，本站仅提供信息存储服务！如有侵权或有涉及法律问题请联系我们。