首页
学习
活动
专区
圈层
工具
发布
社区首页 >专栏 >【双指针】快乐数

【双指针】快乐数

原创
作者头像
lirendada
发布于 2026-11-16 11:38:53
发布于 2026-11-16 11:38:53
30
举报

202. 快乐数

202. 快乐数

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

「快乐数」 定义为:

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

如果 n 是 快乐数 就返回 true ;不是,则返回 false 。

示例 1:

代码语言:javascript
复制
输入:n = 19
输出:true
解释:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

示例 2:

代码语言:javascript
复制
输入:n = 2
输出:false

提示:

  • 1 <= n <= 2^31 - 1

解题思路:快慢指针

一开始可能会想,这道题还能和双指针扯上关系?没想到还真是,只需要我们将其模型抽象出来即可!

根据题目的定义,无非就是两种情况,要么最后得到是 1,要么最后就是无限循环下去,无限循环下去,其实我们就可以理解为是一个环形,不断的在重复着之前的数字,那对于最后得到的是 1 的情况,其实也是可以抽象为环形的,因为 1 怎么分解最后还是得到 1,相当于 1 一直在循环,如下图所示:

也就是说,走到环里面了,如果此时能知道环里面元素是 1,那么说明是返回 true 的,如果不是 1 的话,说明返回 false。

那问题来了,我们如何得到哪里是环❓❓❓

这时候就借用到了快慢指针来解决了,大家肯定都做过一道链表的判断环题目,用的就是快慢指针,通过快慢指针在环中的不断循环,加上其步伐的快慢,最后两个指针判断是否相等,相等说明就是相遇了,就达到是否在环内的目的!

所以我们只需要用快慢指针,最后肯定快指针先到环内循环,而慢指针则后到环内,在环内循环后两者最后肯定会相遇,判断相遇时候的元素是否为 1 即可判断返回值!

那问题又来了,那是因为在链表题中对于每个节点都有一个指针,而这里不一样啊,快慢指针到底指向什么❓❓❓

我们前面说过,双指针还是快慢指针,它们都不一定是语言级别上的指针,更多意义上表示的是一个指向,根据题目来,因为每一次都要拿这个数的每个位置上的数求平方和,那么也就说明,一次平方和,其实就是下一个位置,那我们就让慢指针指向一次平方和的结果,让快指针指向两次平方和的结果,不就达到了类似链表那样子的快慢了吗,对不对!

这样子问题就解决了!

这里再补充一点知识,有没有可能这道题的结果,不会构成环,而是一直不断增大❓❓❓

答案是必须会构成环!这里其实也很好推导,用到一个鸽巢原理(抽屉原理):其实就是说,现在有 n 个巢,有 n+1 只鸽子,那么就能推出此时至少有一个巢,里面的鸽子数量要大于 1。

为什么呢,因为如果我们如果平均分的话,每个巢就先都有一只鸽子,此时还剩下一只鸽子,所以随便怎么放的话都会至少有一个巢要大于一只鸽子的数量!

说这个有什么用呢,当然有用!根据题目给的数据范围,也就是 2^31 - 1,其大小差不多为 2147483647,也就是 int 类型的范围,此时我们为了便于计算,干脆将其放大到 9999999999,也就是十位数中的最大值!

此时根据题目的平方和计算,可以得到 9999999999 每一位的平分也就是 9 的平方就是 81,一共有十位数,所以就是 810,也就是说,计算平方和之后的范围就在 [1, 810] 之间了,也说明 2147483647 肯定也在 [1, 810] 之间。

那么此时这个区间相当于是巢,一共有 810 个巢,假设此时一个数字通过 810 次计算平方和之后得到了 810 个在 [0, 810] 区间内不重复的数字,此时只要再多算一次,也就是第 811 次,就会出现环形结构!

也就是说,不可能出现无环、一直循环下去的情况,最多计算超过 810 次了之后,也是必定会出现的环的!

接下来的代码也不难了,无非就是求一个平方和罢了,代码如下所示:

代码语言:javascript
复制
class Solution {
public:
    int cal(int n) // 获取每个位置上数字的平方和
    {
        int ret = 0;
        while(n)
        {
            ret += pow(n % 10, 2);
            n /= 10;
        }
        return ret;
    }
    bool isHappy(int n) 
    {
        // 定义快慢指针
        int slow = n, fast = cal(n);
        while(slow != fast)
        {
            slow = cal(slow);
            fast = cal(cal(fast));
        }
        return (slow == 1 ? true : false);
    }
};

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

目录
  • 202. 快乐数
    • 示例 1:
    • 示例 2:
    • 提示:
    • 解题思路:快慢指针
      • 那问题来了,我们如何得到哪里是环❓❓❓
      • 那问题又来了,那是因为在链表题中对于每个节点都有一个指针,而这里不一样啊,快慢指针到底指向什么❓❓❓
      • 这里再补充一点知识,有没有可能这道题的结果,不会构成环,而是一直不断增大❓❓❓
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档