当前位置：首页 > article >正文

[LeetCode]day18 202.快乐数

article 2025/2/11 14:37:29

题目链接

题目描述

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

题解

使用set

先创建一个calculate方法来计算一个数所有位上的平方和
用set集合来储存出现过的结果
如果某一次结果出现了重复，说明进入了循环，不是开心数，直接返回false;
最终结果为1，退出循环，是开心数，返回true;

为什么结果出现重复就进入了循环？举个例子

class Solution {
public:
    int calculate(int n){
          int sum=0;
         //算每个位上的平方和
        while(n){
            int single=n%10;
            n=n/10;
            sum+=single*single;
        }
        return sum;
    }
    bool isHappy(int n) {
        unordered_set<int> hash;
         int result=n;
         while(result!=1){
            result=calculate(result);
            if(hash.find(result)!=hash.end()){
                return false;
            }
            hash.insert(result);
         }
         return true;
    }
};

使用双指针

从Leetcode评论区学的，非常精妙啊
如果结果进入了循环，就相当于链表中进入了环一样
而我们已经学过如何判断一个链表有无环了（不知道可以看这篇文章【LeetCode】day15 142.环形链表II

class Solution {
public:
    int calculate(int n){
          int sum=0;
         //算每个位上的平方和
        while(n){
            int single=n%10;
            n=n/10;
            sum+=single*single;
        }
        return sum;
    }
    bool isHappy(int n) {
      int fast=n,slow=n;
      do{
        //慢指针走一步
        slow=calculate(slow);
        //快指针走两步
        fast=calculate(fast);
        fast=calculate(fast);
      }while(fast!=slow);

      return slow==1;
      }
};