招银笔试编程:检测从起点出发的可能环路

时间:2020-9-7 作者:admin

比如系统里面有五个服务节点(节点编号0~4),用五阶矩阵A表达各个服务之间的关联关系,0表示无法访问,1表示有访问,比如下面:

{0,1,0,0,0}
{0,0,1,1,0}
{1,0,0,0,0}
{0,0,0,0,1}
{0,1,1,0,0}

A[0][1]=1,表示节点0会调用节点1;

A[4][0]=0,表示节点4不会调用节点0;

将矩阵画出之后,可以观察到从服务4出发,存在环:

4-1-3-4

4-2-0-1-3-4

请编程满足一下输入:

M

0 1 0 0 0  0 0 1 1 0 1 0 0 0 0 0 0 0 0 1 0 1 1 0 0

N

(注):M表示M阶矩阵,下面一行表示矩阵里面的数据,N表示起始的服务节点。

输出:

413

42013

也就是环。


思路:递归调用,参数里面一个双向链表保存当前的所有路径上的节点,然后每次调到别的节点的时候,查询双向链表的开头和当前的服务节点是否一样,一样就直接放入结果集,最后如果当前链表的长度够了,也要检验下一个节点是不是双向链表的开头。

注:不能使用contains来检查,而必须使用peekFirst,因为题目要求的是大环:4-2-0-1-3-4这样的(我叫做大环),而4-2-0-2这种是不算的(我把这种环叫做小环),所以必须检查链表的开头,所以我才会使用双向链表。

public static List<List<Integer>> res;
	public static void process(int[][] arr,int n,int cur,LinkedList<Integer> tmp){
		if(tmp.size()==n){//查看是大环还是小环
			int[] save=arr[cur];
			for(int i=0;i<n;i++){//查看下一个
				if(save[i]==1&&i==tmp.peekFirst()){//大环
					res.add(new LinkedList<Integer>(tmp));
				}
			}
			return ;
		}
		int[] savetmp=arr[cur];
		for(int i=0;i<n;i++){
			if(savetmp[i]==1){
				if(i==tmp.peekFirst()){//如果之前有了
					res.add(new LinkedList<Integer>(tmp));
					continue;
				}
				else{//如果之前没有
					tmp.add(i);
					process(arr,n,i,tmp);
					tmp.remove(tmp.size()-1);
				}
			}
		}
	}
	public static void print(List<List<Integer>> res){
		for(List<Integer> a:res){
			for(Integer b:a){
				System.out.print(b);
			}
			System.out.println();
		}
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		//int[][] arr={{0,1,0,0,0},{0,0,1,1,0},{1,0,0,0,0},{0,0,0,0,1},{0,1,1,0,0}};
		int n=sc.nextInt();
		int[][] arr=new int[n][n];
		sc.nextLine();
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				arr[i][j]=sc.nextInt();
			}
		}
		sc.nextLine();
		int k=sc.nextInt();
		res=new LinkedList<>();//结果集
		LinkedList<Integer> tmp= new LinkedList<>();//双向链表,暂存路径
		tmp.addLast(k);//加入起始的服务节点
		process( arr,n,k,tmp);
		print(res);
			
	}

 

声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。