Easy

题目描述

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

解题思路

这道题的关键在于理解快乐数的定义和如何检测循环。我们需要不断计算数字各位的平方和，直到结果为1或进入循环。

解题思路：

  1. 哈希集合法：用集合记录出现过的数字，如果再次遇到说明进入循环，返回false。

  2. 快慢指针法（推荐）：类似检测链表环的思想，用快慢指针检测循环。快指针每次走两步，慢指针每次走一步，如果有循环它们必然相遇。

核心操作：

  • 计算数字各位平方和：提取每一位数字，求平方后相加
  • 循环检测：当结果不为1时，需要判断是否进入循环

快慢指针法更优雅，空间复杂度更低，是面试中的经典技巧。当快指针到达1时说明是快乐数；当快慢指针相遇且不为1时说明进入循环，不是快乐数。

这种方法避免了额外的存储空间，体现了算法设计的巧妙性。

代码实现

class Solution {
public:
    bool isHappy(int n) {
        auto getNext = [](int num) {
            int sum = 0;
            while (num > 0) {
                int digit = num % 10;
                sum += digit * digit;
                num /= 10;
            }
            return sum;
        };
        
        int slow = n;
        int fast = getNext(n);
        
        while (fast != 1 && slow != fast) {
            slow = getNext(slow);
            fast = getNext(getNext(fast));
        }
        
        return fast == 1;
    }
};

class Solution:
    def isHappy(self, n: int) -> bool:
        def get_next(num):
            total_sum = 0
            while num > 0:
                digit = num % 10
                total_sum += digit * digit
                num //= 10
            return total_sum
        
        slow = n
        fast = get_next(n)
        
        while fast != 1 and slow != fast:
            slow = get_next(slow)
            fast = get_next(get_next(fast))
        
        return fast == 1

public class Solution {
    public bool IsHappy(int n) {
        int GetNext(int num) {
            int sum = 0;
            while (num > 0) {
                int digit = num % 10;
                sum += digit * digit;
                num /= 10;
            }
            return sum;
        }
        
        int slow = n;
        int fast = GetNext(n);
        
        while (fast != 1 && slow != fast) {
            slow = GetNext(slow);
            fast = GetNext(GetNext(fast));
        }
        
        return fast == 1;
    }
}

/**
 * @param {number} n
 * @return {boolean}
 */
var isHappy = function(n) {
    const seen = new Set();
    
    while (n !== 1 && !seen.has(n)) {
        seen.add(n);
        let sum = 0;
        while (n > 0) {
            let digit = n % 10;
            sum += digit * digit;
            n = Math.floor(n / 10);
        }
        n = sum;
    }
    
    return n === 1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

方法时间复杂度空间复杂度
快慢指针法O(log n)O(1)
哈希集合法O(log n)O(log n)

说明：

  • 时间复杂度：O(log n)，因为数字的位数是 log n，而循环的长度是有限的
  • 空间复杂度：快慢指针法为 O(1)，哈希集合法为 O(log n)

相关题目