力扣-202. 快乐数解析-弗洛伊德循环查找算法

这篇具有很好参考价值的文章主要介绍了力扣-202. 快乐数解析-弗洛伊德循环查找算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目链接

力扣-202. 快乐数解析-弗洛伊德循环查找算法,算法,LeetCode,算法,leetcode,java 力扣-202. 快乐数解析-弗洛伊德循环查找算法,算法,LeetCode,算法,leetcode,java

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 

可以发现

力扣-202. 快乐数解析-弗洛伊德循环查找算法,算法,LeetCode,算法,leetcode,java

归纳一下这些简单数字就可以发现,对于任意一个非快乐数,最终会进入重复循环, ···不难发现,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;
        }

    }

力扣-202. 快乐数解析-弗洛伊德循环查找算法,算法,LeetCode,算法,leetcode,java

感觉不太行 

想了一想 其实这道题为弗洛伊德查找算法提供了很好的条件

弗洛伊德查找算法原理见此处链接

代码如下:

{
    //弗洛伊德循环查找算法
    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)

力扣-202. 快乐数解析-弗洛伊德循环查找算法,算法,LeetCode,算法,leetcode,java

第一次更新值

力扣-202. 快乐数解析-弗洛伊德循环查找算法,算法,LeetCode,算法,leetcode,java

力扣-202. 快乐数解析-弗洛伊德循环查找算法,算法,LeetCode,算法,leetcode,java

第二次

力扣-202. 快乐数解析-弗洛伊德循环查找算法,算法,LeetCode,算法,leetcode,java

力扣-202. 快乐数解析-弗洛伊德循环查找算法,算法,LeetCode,算法,leetcode,java

第三次

力扣-202. 快乐数解析-弗洛伊德循环查找算法,算法,LeetCode,算法,leetcode,java

力扣-202. 快乐数解析-弗洛伊德循环查找算法,算法,LeetCode,算法,leetcode,java

第四次

力扣-202. 快乐数解析-弗洛伊德循环查找算法,算法,LeetCode,算法,leetcode,java

力扣-202. 快乐数解析-弗洛伊德循环查找算法,算法,LeetCode,算法,leetcode,java

第五次

力扣-202. 快乐数解析-弗洛伊德循环查找算法,算法,LeetCode,算法,leetcode,java

力扣-202. 快乐数解析-弗洛伊德循环查找算法,算法,LeetCode,算法,leetcode,java

第六次

力扣-202. 快乐数解析-弗洛伊德循环查找算法,算法,LeetCode,算法,leetcode,java

力扣-202. 快乐数解析-弗洛伊德循环查找算法,算法,LeetCode,算法,leetcode,java

第七次

力扣-202. 快乐数解析-弗洛伊德循环查找算法,算法,LeetCode,算法,leetcode,java

力扣-202. 快乐数解析-弗洛伊德循环查找算法,算法,LeetCode,算法,leetcode,java

第八次

力扣-202. 快乐数解析-弗洛伊德循环查找算法,算法,LeetCode,算法,leetcode,java

力扣-202. 快乐数解析-弗洛伊德循环查找算法,算法,LeetCode,算法,leetcode,java

此时slow== fast

发现为循环链表(这里没有存储之前的值算不上链表)

return false

力扣-202. 快乐数解析-弗洛伊德循环查找算法,算法,LeetCode,算法,leetcode,java

舒服了

如果觉得有用请点赞收藏, 谢谢啦

力扣-202. 快乐数解析-弗洛伊德循环查找算法,算法,LeetCode,算法,leetcode,java文章来源地址https://www.toymoban.com/news/detail-809423.html

到了这里,关于力扣-202. 快乐数解析-弗洛伊德循环查找算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 弗洛伊德算法(求最短路径)

    在一个加权图中,如果想找到各个顶点之间的最短路径,可以考虑使用弗洛伊德算法。 弗洛伊德算法既适用于无向加权图,也适用于有向加权图。使用弗洛伊德算法查找最短路径时,只允许环路的权值为负数,其它路径的权值必须为非负数,否则算法执行过程会出错。 弗洛

    2024年02月06日
    浏览(43)
  • Floyd - Warshall (弗洛伊德算法)

    图中任意两点之间的最短路径问题 Dijkstra和Bellman-Ford也可以以所有点为源点,求出任意两点之间的最短距离,但是Dijstra不能解决带负权的的边,Bellman-Ford 效率慢点 Floyd算法考虑的是一条最短路径的中间节点,即简单路径p={v1 , v2,  ...  ,vn}上除v1和vn的任意节点 设K是p的一个

    2024年02月06日
    浏览(37)
  • 今天学习了弗洛伊德算法(floyed)

    我自己写的模板 嘿嘿 Dijkstra算法SPFA算法但是我知道还有这些,但是今天是周末哎,我有点不想学了,我今天学的是比较差劲的一个算法(但是它好像比较好记啊),改天再学其他比较好一点的算法加强自己 输入 输出 后言:提醒自己加权值是分题目来不同权值,不是像示例

    2024年02月11日
    浏览(33)
  • 【数据结构】图—弗洛伊德(Floyd)算法

    上文介绍了迪杰斯特拉(Dijkstra)算法,计算网图的某个源点到其余各个顶点的最短路径问题(边权值为非负值),本文介绍另一个求最短路径的算法——弗洛伊德算法,它是计算所有顶点到所有顶点的最短路径,其时间复杂度为 O ( n 3 ) O(n^3) O ( n 3 ) ,其算法相比Dijkstra算法更加

    2024年02月12日
    浏览(51)
  • 12.25~12.27并查集(查找与合并),全排列,约瑟夫问题(队列,数组)upper/lower_bound,重构二叉树,最优矩阵,线段树(构建),淘汰赛(构建树,队列),医院问题(最短路,弗洛伊德

    题目背景 若某个家族人员过于庞大,要判断两个是否是亲戚,确实还很不容易,现在给出某个亲戚关系图,求任意给出的两个人是否具有亲戚关系。 题目描述 规定:�x 和 �y 是亲戚,�y 和 �z 是亲戚,那么 �x 和 �z 也是亲戚。如果 �x,�y 是亲戚,那么 �

    2024年01月23日
    浏览(48)
  • 算法——弗洛伊德算法(Floyd-Warshall)(图论)(c++)

    (蒟蒻的第四篇文章,希望dalao勿喷) (希望没问题) 声明: 1.本人变量定义的名称很low 2.本人用的方法也很low 3.但我觉得文章应该不low  (盲目自信) 第四篇文章讲讲Floyd算法 Floyd算法是一种寻找最短路径的常见算法,其特点是: 短,好理解(虽然其他算法也挺好理解的

    2023年04月09日
    浏览(33)
  • 弗洛伊德(Floyd's)算法—解决最短路径经典算法

    弗洛伊德算法(Floyd\\\'s algorithm)是一种用于解决图中最短路径问题的经典算法。由美国计算机科学家罗伯特·弗洛伊德于1962年提出,该算法通过动态规划的思想,在图中寻找任意两个节点之间的最短路径,具有广泛的应用。本文将详细介绍弗洛伊德算法的原理、实现细节以及应用

    2024年02月04日
    浏览(38)
  • 弗洛伊德(Floyd)算法求个顶点之间最短路径问题(详解+图解)

    具体来说,弗洛伊德算法通过求解所有点对之间的最短路径来实现。在算法开始时,我们假设图中的所有节点之间都是不联通的,即它们之间的距离为无穷大。然后,我们对图进行“松弛”操作,即尝试更新每个节点之间的距离估计值,以寻找更短的路径。具体来说,对于图

    2024年02月08日
    浏览(41)
  • 大话数据结构-迪杰斯特拉算法(Dijkstra)和弗洛伊德算法(Floyd)

      最短路径,对于图来说,是两顶点之间经过的边数最少的路径;对于网来说,是指两顶点之间经过的边上权值之和最小的路径。路径上第一个顶点为源点,最后一个顶点是终点。   以如下无向图为例:   我们来计算下标为0的顶点,到其他顶点的最短路径,首先定义

    2024年02月06日
    浏览(39)
  • 【数据结构】最短路径算法实现(Dijkstra(迪克斯特拉),FloydWarshall(弗洛伊德) )

    最短路径问题 :从在带权有向图G中的某一顶点出发,找出一条通往另一顶点的最短路径,最短也就是沿路径各边的权值总和达到最小。 单源最短路径问题:给定一个图G = ( V , E ) G=(V,E)G=(V,E),求源结点s ∈ V s∈Vs∈V到图 中每个结点v ∈ V v∈Vv∈V的最短路径 针对一个带权

    2024年02月04日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包