题目链接
public static void Happy(int n) { int sum = 0; int digit = 0; for (int i = 0; i < 20; i++) { while (n != 0) { digit = n%10; sum += digit*digit; n/=10; } System.out.print(sum + " "); n = sum; sum = 0; } }
使用代码测试一下每一代数字
n = 2 : 4 16 37 58 89 145 42 20 4 16 37 58 89 145 42 20 4 16 37 58 n = 3 : 9 81 65 61 37 58 89 145 42 20 4 16 37 58 89 145 42 20 4 16 n = 4 : 16 37 58 89 145 42 20 4 16 37 58 89 145 42 20 4 16 37 58 89 n = 5 : 25 29 85 89 145 42 20 4 16 37 58 89 145 42 20 4 16 37 58 89 n = 6 : 36 45 41 17 50 25 29 85 89 145 42 20 4 16 37 58 89 145 42 20 n = 7 : 49 97 130 10 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
可以发现
归纳一下这些简单数字就可以发现,对于任意一个非快乐数,最终会进入重复循环, ···不难发现,4即之后的结果就是新一轮循环。
那么我的第一个做法是检测4出现的次数 如果4出现次数超过两次, 那么就不是快乐数
{
int sum = 0;
int n1 = n;
int count = 0;
for (int i = 0; ; i++) {
while (true) {
int a = n%10;
sum += a*a;
n /= 10;
if (n == 0){break;}
}
if (sum==4){
count++;
}
if (sum==1){return true;}
if (count==2){return false;}
n = sum;
sum=0;
}
}
感觉不太行
想了一想 其实这道题为弗洛伊德查找算法提供了很好的条件
弗洛伊德查找算法原理见此处链接
代码如下:
{
//弗洛伊德循环查找算法
public static boolean isHappy(int n) {
int slow = n;
int fast = n;
while (true) {
slow = Next(slow);
fast = Next(Next(fast));
if (fast == 1) {
return true;
} else if (fast == slow) {
return false;
}
}
}
public static int Next(int n){
int sum = 0;
while (n != 0){
int digit = n % 10;
sum += digit*digit;
n /= 10;
}
return sum;
}
public static void main(String[] args) {
System.out.println(isHappy(19));
}
}
当测试用例为2这个数字的时候
4 16 37 58 89 145 42 20 4 16 37 58 89 145 42 20 4 16 37 58
第一步初始化slow和fast两个指针为头结点 (就是2)
第一次更新值
第二次
第三次
第四次
第五次
第六次
第七次
第八次
此时slow== fast
发现为循环链表(这里没有存储之前的值算不上链表)
return false
舒服了
如果觉得有用请点赞收藏, 谢谢啦文章来源:https://www.toymoban.com/news/detail-809423.html
文章来源地址https://www.toymoban.com/news/detail-809423.html
到了这里,关于力扣-202. 快乐数解析-弗洛伊德循环查找算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!