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

L33.【LeetCode题解】快乐数(双指针思想)

news 来源：原创 2025/8/28 12:42:03

1.题目

2.分析

3.代码

4.提交结果

5.题外话

证明:一定是循环的

前置知识:鸽巢原理

不严格证明

1.题目

https://leetcode.cn/problems/happy-number/

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

1 <= n <= 2^(31) - 1

2.分析

分析两个测试数据:19和2,

19-->82-->68-->100-->1-->1--->......-->1

2-->4-->16->>37-->58-->89-->145-->42-->20-->4-->16-->37-->58-->89-->145-->42-->20-->4-->...

如果画图则非常清晰:

发现本题画出的两个情况特别像之前讲过的环形链表

L10.【LeetCode题解】环形链表(判断链表中是否有环)

L22.【LeetCode题解】环形链表(返回环的入口点方法1)

只不过这道题不在于判断是否有环,而是在有环的情况下,判断循环的数是否为1

可以在这里直接套用快慢指针的解法(双指针解法),不过这里的快慢"指针"应该理解为"快慢数"

回顾L22文章的结论推导:

结论:设有两个新的指针p1和p2,p1从起始点出发,p2从相遇点出发,设p1和p2每次都走1步,则p1和p2一定相遇

设"快数"为fast,慢数为slow,初始值都为n,"快数"一次循环变化两次,"慢数"一次循环变化一次,最终"快数"的值一定等于"慢数"的值(L10文章和L22文章得到的结论),再判断"快数"和"慢数"相遇的值即可("快数"和"慢数"选任何一个判断其值),如果为1,为快乐数,反之不是快乐数

3.代码

将"对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和"变化的过程写成一个函数process,提高代码可读性

class Solution {
public:int process(int n){int sum=0;while(n){sum+=(n%10)*(n%10);n/=10;}return sum;}bool isHappy(int n) {int fast=n;int slow=n;while(1){//变化2次,嵌套调用,也可以写两遍fast=process(fast);fast=process(process(fast));slow=process(slow);//变化1次if (fast==slow)break;}return fast==1;}
};

4.提交结果

5.题外话

本题的"然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1"说明: 无论是什么数,最终结果只有一种情况:循环,没有其他不循环的情况

证明:一定是循环的

前置知识:鸽巢原理

n个鸽子放入(n+1)个鸽巢中,至少存在两个鸽子在一个鸽巢中,也可以这样说:观众席上有366位观众,至少存在两位观众生日是相同的

不严格证明

本题n的类型为int,而int类型的最大值为2147483647,process(2147483647)==260,则给定任意一个正整数n,process(n)的结果在[1,260],则经过261次运算,至少有两次process执行的结果是相同的,因此结果是循环的

1.题目

2.分析

3.代码

4.提交结果

5.题外话

证明:一定是循环的

前置知识:鸽巢原理

不严格证明

相关文章：