企业官网建设流程全解析

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

题目分析：

对于任意一个正整数，替换k轮次后，结果要么是1，要么是无限循环且始终不等于1，没有第三种可能。

为什么只有【变为1】或【进入循环】两种可能？

• 1 <= n <= 2^31 - 1
• n能表示的最大整数是2147483647，10位数，它能表示的最大的各位平方和是260
• 9位数，最大的数999999999，它能表示的最大的各位平方和是9^2*9=729
• 而3位数，最大的数是999，它能表示的最大的各位平方和是9^2*3=243

即对任意整数，第一次bitSum（）后，结果一定是三位数——>第二次bitSum（）后，结果一定<=243

也就是说，无论这个数字是多少，在经过两轮的bitSum（）之后，得到的数字一定<=243

这个过程一定会进入一个【有限状态集合】：在数字<=243之后，所有可能出现的数字，只有0~242这243种可能

由鸽巢定理可知：进入有限状态后，最多再执行244次bitSum（），就一定会出现一个之前出现过的数字

• 重复的数字是1：永远停留在1，这就是快乐数
• 重复的数字不是1，而是一个循环：非快乐数

举例：

1.数字2

非快乐数

2.数字19

19 → 82 → 68 → 100 → 1

快乐数

算法思想：快慢指针

快指针：每次走2步

慢指针：每次走1步

题解：