LeetCode第202题_快乐数-CSDN博客

本文链接：https://blog.csdn.net/qq_40263592/article/details/147869946

LeetCode 第202题：快乐数

题目描述

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

「快乐数」定义为：

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

难度

简单

题目链接

点击在LeetCode中查看题目

示例

示例 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，则是快乐数；如果出现循环，则不是快乐数

时间复杂度：O(logn)，其中n是输入的数字
空间复杂度：O(logn)

方法二：快慢指针检测循环

我们可以使用Floyd的乌龟和兔子（龟兔赛跑）算法来检测循环，这是一种空间复杂度为O(1)的算法。

关键点：

使用两个指针，一个慢指针（龟）每次走一步，一个快指针（兔）每次走两步
如果存在循环，快指针最终会与慢指针相遇
如果没有循环，快指针最终会到达1

时间复杂度：O(logn)
空间复杂度：O(1)

代码实现

C# 实现

方法一：哈希集合检测循环

public class Solution {
    public bool IsHappy(int n) {
        HashSet<int> seen = new HashSet<int>();
        
        while (n != 1 && !seen.Contains(n)) {
            seen.Add(n);
            n = GetNext(n);
        }
        
        return n == 1;
    }
    
    private int GetNext(int n) {
        int sum = 0;
        while (n > 0) {
            int digit = n % 10;
            sum += digit * digit;
            n /= 10;
        }
        return sum;
    }
}

方法二：快慢指针检测循环

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

Python 实现

方法一：哈希集合检测循环

class Solution:
    def isHappy(self, n: int) -> bool:
        seen = set()
        
        while n != 1 and n not in seen:
            seen.add(n)
            n = self.get_next(n)
        
        return n == 1
    
    def get_next(self, n: int) -> int:
        total_sum = 0
        while n > 0:
            n, digit = divmod(n, 10)
            total_sum += digit ** 2
        return total_sum

方法二：快慢指针检测循环

class Solution:
    def isHappy(self, n: int) -> bool:
        def get_next(number):
            total_sum = 0
            while number > 0:
                number, digit = divmod(number, 10)
                total_sum += digit ** 2
            return total_sum
        
        slow_runner = n
        fast_runner = get_next(n)
        
        while fast_runner != 1 and slow_runner != fast_runner:
            slow_runner = get_next(slow_runner)
            fast_runner = get_next(get_next(fast_runner))
            
        return fast_runner == 1

C++ 实现

方法一：哈希集合检测循环

class Solution {
public:
    bool isHappy(int n) {
        unordered_set<int> seen;
        
        while (n != 1 && seen.find(n) == seen.end()) {
            seen.insert(n);
            n = getNext(n);
        }
        
        return n == 1;
    }
    
private:
    int getNext(int n) {
        int sum = 0;
        while (n > 0) {
            int digit = n % 10;
            sum += digit * digit;
            n /= 10;
        }
        return sum;
    }
};

方法二：快慢指针检测循环

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

性能分析

各语言实现的性能对比：

实现语言	方法	执行用时	内存消耗	特点
C#	方法一	28 ms	16.5 MB	实现简单，易于理解
C#	方法二	24 ms	15.8 MB	空间效率高
Python	方法一	36 ms	14.9 MB	代码简洁
Python	方法二	36 ms	14.8 MB	空间效率高
C++	方法一	0 ms	6.3 MB	执行速度快
C++	方法二	0 ms	5.9 MB	最优性能和空间效率