「环上游走java」游环是什么

今天给各位分享环上游走java的知识，其中也会对游环是什么进行解释，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在开始吧！

本文目录一览：

• 1、求一段java程序，求图是否存在环。该图是有向图。要求该方法输入边的序对集合，比如3->4啊4->
• 2、Java判断单链表是否有环的两种实现方法
• 3、用java编程：输入1~20的整数n，把从1到n的n个整数摆成环,使得该环上任意

求一段java程序，求图是否存在环。该图是有向图。要求该方法输入边的序对集合，比如3->4啊4->

一个顶点a在一个环上，那么存在以它为终点的边, 假设这些边的起点集合为PreA, 考察点a能否到达点PreA中的点，如果到达就找到了一个环，否则点a不在环上。

遍历图中的顶点进行上述操作即可。

Java判断单链表是否有环的两种实现方法

方法一：首先从头节点开始，依次遍历单链表的每一个节点。每遍历到一个新节点，就从头节点重新遍历新节点之前的所有节点，用新节点id和此节点之前所有节点id依次作比较。如果发现新节点之前的所有节点当中存在相同节点id，则说明该节点被遍历过两次，链表有环；如果之前的所有节点当中不存在相同的节点，就继续遍历下一个新节点，继续重复刚才的操作。

例如这样的链表：a-b-c-d-b-c-d，

当遍历到节点d的时候，我们需要比较的是之前的节点a、b、c，不存在相同节点。这时候要遍历的下一个新节点是b，b之前的节点a、b、c、d中恰好也存在b，因此b出现了两次，判断出链表有环。

假设从链表头节点到入环点的距离是d，链表的环长是s。d+s是链表总节点数。那么算法的时间复杂度是0+1+2+3+….+(d+s-1)

=

(d+s-1)*(d+s)/2

，

可以简单地理解成

o(n*n)。而此算法没有创建额外存储空间，空间复杂度可以简单地理解成为o(1)。

方法二：首先创建一个以节点id为键的hashset集合，用来存储曾经遍历过的节点。然后同样是从头节点开始，依次遍历单链表的每一个节点。每遍历到一个新节点，就用新节点和hashset集合当中存储的节点作比较，如果发现hashset当中存在相同节点id，则说明链表有环，如果hashset当中不存在相同的节点id，就把这个新节点id存入hashset，之后进入下一节点，继续重复刚才的操作。

这个方法在流程上和方法一类似，本质的区别是使用了hashset作为额外的缓存。

假设从链表头节点到入环点的距离是d，链表的环长是s。而每一次hashset查找元素的时间复杂度是o(1),

所以总体的时间复杂度是1*(d+s)=d+s，可以简单理解为o(n)。而算法的空间复杂度还是d+s-1，可以简单地理解成o(n)。

方法三：首先创建两个指针1和2（在java里就是两个对象引用），同时指向这个链表的头节点。然后开始一个大循环，在循环体中，让指针1每次向下移动一个节点，让指针2每次向下移动两个节点，然后比较两个指针指向的节点是否相同。如果相同，则判断出链表有环，如果不同，则继续下一次循环。

例如链表a-b-c-d-b-c-d，两个指针最初都指向节点a，进入第一轮循环，指针1移动到了节点b，指针2移动到了c。第二轮循环，指针1移动到了节点c，指针2移动到了节点b。第三轮循环，指针1移动到了节点d，指针2移动到了节点d，此时两指针指向同一节点，判断出链表有环。

此方法也可以用一个更生动的例子来形容：在一个环形跑道上，两个运动员在同一地点起跑，一个运动员速度快，一个运动员速度慢。当两人跑了一段时间，速度快的运动员必然会从速度慢的运动员身后再次追上并超过，原因很简单，因为跑道是环形的。

用java编程：输入1~20的整数n，把从1到n的n个整数摆成环,使得该环上任意

不用了，这个是一个常规算法题，早就有标准代码了

public class PrimeTest {

    //判断某整数是不是质数

    public static boolean isp(int n){

        for(int i = 2; i  Math.sqrt(n)+1;i++){

            if(n % i == 0){

                return false;

            }

        }

        return true;

    }

    public static int n = 20;

    public static boolean[] vis = new boolean[n+1];//存储某数是否被使用

    public static int[] arr = new int[n+1];//存放数列

    public static void dfs(int cur){

        if(cur == n+1  isp(arr[1]+arr[n])  arr[1] == 1){//如果最后一个数放进去了，并且最后一个数和第一个的和为质数，并且第一个数是1（因为我们只输出开头是1的，避免重复）

            for(int i = 1; i = n; i++){//打印出数列

                System.out.print(arr[i]+",");

            }

            System.out.println();

        }else{

            for(int i = 1; i = n; i++){//尝试放置每个数i

                if(!vis[i]  isp(i+arr[cur-1])){//如果这个数没有被使用，并且与前一个数的和是质数

                    vis[i] = true;//标明这个数被使用

                    arr[cur] = i;//将这个数加入队列

                    dfs(cur+1);//求下一个数

                    vis[i] = false;//取消这个数

                }

            }

        }

    }

    public static void main(String[] args) {

        arr[0] = 0;

        for(int i = 0; i = n;i++){

            vis[i] = false;

        }

        dfs(1);

    }

}

1,2,3,4,7,6,5,8,9,10,13,16,15,14,17,20,11,12,19,18,

1,2,3,4,7,6,5,8,9,10,13,16,15,14,17,20,11,18,19,12,

1,2,3,4,7,6,5,8,9,10,13,18,19,12,11,20,17,14,15,16,

1,2,3,4,7,6,5,8,9,10,19,12,11,20,17,14,15,16,13,18,

1,2,3,4,7,6,5,8,9,10,19,18,13,16,15,14,17,20,11,12,

1,2,3,4,7,6,5,8,9,14,15,16,13,10,19,12,17,20,11,18,

1,2,3,4,7,6,5,8,9,14,15,16,13,10,19,18,11,20,17,12,

1,2,3,4,7,6,5,8,9,14,15,16,13,18,11,20,17,12,19,10,

1,2,3,4,7,6,5,8,9,20,11,12,17,14,15,16,13,10,19,18,

1,2,3,4,7,6,5,8,9,20,11,12,17,14,15,16,13,18,19,10,

1,2,3,4,7,6,5,8,9,20,11,18,13,10,19,12,17,14,15,16,

1,2,3,4,7,6,5,8,9,20,11,18,13,16,15,14,17,12,19,10,

底下还有好几页

关于环上游走java和游环是什么的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。