LeetCode 202. 快乐数

Categories:

题目描述
思路分析
1. 解法一：快慢指针判环（推荐）
相似题目

题目描述

✅ 202. 快乐数

思路分析

解法一：快慢指针判环（推荐）

核心思路：

定义函数 next(x) 为将数字按位平方求和的结果。

若序列最终为 1，则是快乐数；否则会进入循环。

使用快慢指针检测环，避免额外哈希空间。

复杂度分析：

时间复杂度：O(log n)，其中 n 表示初始数字大小，每次计算只与位数有关。

空间复杂度：O(1)，仅使用常数额外空间。

class Solution {
    public boolean isHappy(int n) {
        int slow = n;
        int fast = next(n);

        while (fast != 1 && slow != fast) {
            slow = next(slow);
            fast = next(next(fast));
        }

        return fast == 1;
    }

    private int next(int x) {
        int sum = 0;
        while (x > 0) {
            int d = x % 10;
            sum += d * d;
            x /= 10;
        }
        return sum;
    }
}

func isHappy(n int) bool {
	slow := n
	fast := nextHappy(n)

	for fast != 1 && slow != fast {
		slow = nextHappy(slow)
		fast = nextHappy(nextHappy(fast))
	}

	return fast == 1
}

func nextHappy(x int) int {
	sum := 0
	for x > 0 {
		d := x % 10
		sum += d * d
		x /= 10
	}
	return sum
}

相似题目

题目	难度	考察点
141. 环形链表	简单	快慢指针、判环
142. 环形链表 II	中等	快慢指针、判环
287. 寻找重复数	中等	快慢指针、判环
258. 各位相加	简单	数学、位运算
263. 丑数	简单	数学、因子分解

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/79558975