网站制作学习网站,ps怎么制作网页设计,做图网站地图,长沙企业关键词优化哪家好快乐数OJ链接#xff1a;202. 快乐数 - 力扣#xff08;LeetCode#xff09;
题目#xff1a; 题目分析: 为了房便叙述#xff0c;将「对于⼀个正整数#xff0c;每⼀次将该数替换为它每个位置上的数字的平方和」这⼀个 操作记为 x 操作#xff1b; 题目告诉我们#…快乐数OJ链接202. 快乐数 - 力扣LeetCode
题目 题目分析: 为了房便叙述将「对于⼀个正整数每⼀次将该数替换为它每个位置上的数字的平方和」这⼀个 操作记为 x 操作 题目告诉我们当我们不断重复 x 操作的时候计算⼀定会「死循环」死的方式有两种 ▪ 情况⼀⼀直在 1 中死循环即 1 - 1 - 1 - 1...... ▪ 情况⼆在历史的数据中死循环但始终变不到 1 由于上述两种情况只会出现⼀种因此只要我们能确定循环是在「情况⼀」中进行还是在「情 况⼆」中进行就能得到结果。 简单证明 a. 经过⼀次变化之后的最⼤值 9^2 * 10 810 ( 2^31-12147483647 。选⼀个更⼤的最 ⼤ 9999999999 )也就是变化的区间在 [1, 810] 之间 b. 根据「鸽巢原理」⼀个数变化 811 次之后必然会形成⼀个循环 c. 因此变化的过程最终会走到⼀个圈⾥面因此可以用「快慢指针」来解决。 4. 解法快慢指针 算法思路 根据上述的题目分析我们可以知道当重复执行 x 的时候数据会陷入到⼀个「循环」之中。 ⽽「快慢指针」有⼀个特性就是在⼀个圆圈中快指针总是会追上慢指针的也就是说他们总会 相遇在⼀个位置上。如果相遇位置的值是 1 那么这个数⼀定是快乐数如果相遇位置不是 1 的话那么就不是快乐数。 补充知识如何求⼀个数n每个位置上的数字的平方和。 a. 把数 n 每⼀位的数提取出来 循环迭代下面步骤 i. int t n % 10 拿到个位 ii. n / 10 噶掉个位 直到 n 的值变为 0 b. 提取每⼀位的时候用⼀个变量 sum 记录这⼀位的平方与之前提取位数的平方和 ▪ sum sum t * t
C:
class Solution
{
public:int bitSum(int n)//返回 n 这个数每⼀位上的平⽅和{int sum 0;while (n){int t n % 10;//拿到个位上的数sum t * t;//个位上数的平方和n / 10;//用完就噶掉一位数}return sum;}bool isHappy(int n){int slow n, fast bitSum(n);while (slow ! fast){slow bitSum(slow);fast bitSum(bitSum(fast));}return slow 1;}
}; 运行结果 PS看到这里了码字不易给个一键三连鼓励一下吧有不足或者错误之处欢迎在评论区指出
