【算法双指针篇】快乐数

https://leetcode.cn/problems/happy-number/description/题目分析对于任意一个正整数替换k轮次后结果要么是1要么是无限循环且始终不等于1没有第三种可能。为什么只有【变为1】或【进入循环】两种可能1 n 2^31 - 1n能表示的最大整数是214748364710位数它能表示的最大的各位平方和是2609位数最大的数999999999它能表示的最大的各位平方和是9^2*9729而3位数最大的数是999它能表示的最大的各位平方和是9^2*3243即对任意整数第一次bitSum后结果一定是三位数——第二次bitSum后结果一定243也就是说无论这个数字是多少在经过两轮的bitSum之后得到的数字一定243这个过程一定会进入一个【有限状态集合】在数字243之后所有可能出现的数字只有0~242这243种可能由鸽巢定理可知进入有限状态后最多再执行244次bitSum就一定会出现一个之前出现过的数字重复的数字是1永远停留在1这就是快乐数重复的数字不是1而是一个循环非快乐数举例1.数字2非快乐数2.数字1919 → 82 → 68 → 100 → 1快乐数算法思想快慢指针快指针每次走2步慢指针每次走1步题解