HJ77 火车进站(java详解)

类似数据结构题,给一个入栈序列,有多少种出栈序列
然后运用递归 第一个问题可以产生两个子问题 入栈和出栈
直至终结条件待入队列为空,待出栈为空,递归终止
代码如下:

public static void main(String[] args){Scanner in = new Scanner(System.in);int n=in.nextInt();//定义代入队列Queue queue=new ArrayDeque<>();for(int i=0;i stack=new Stack<>();//定义出序列,记录从栈中出去的顺序List list=new ArrayList<>();//定义pop=""为了递归结束后传入出序列里面.String pop="";//递归上面定义的三个res(stack,queue,list,pop);//for循环输出list里面的数值Collections.sort(list);for(String res:list){String[] strr=res.split(" {1,}");for(int i=0;i<= strr.length-1;i++){if(i!=strr.length-1)System.out.print(strr[i]+" ");else System.out.println(strr[i]);}}}public static void res(Stack stack,Queue queue,List list,String pop){//如果当前某个子问题的待出栈以及待入队列全是空的就说明没有可以出的了,结束递归,把出栈序列pop存入list里面if(queue.isEmpty()&&stack.isEmpty()){list.add(pop);return;}//给当前文字划分两个子问题,是入栈还是出栈,这个if我给的是入栈if(!queue.isEmpty()){Queue queue1=new ArrayDeque<>(queue);Stack stack1=(Stack) stack.clone();stack1.push(queue1.poll());res(stack1,queue1,list,pop);}//给当前文字划分两个子问题,是入栈还是出栈,这个if我给的是出栈if(!stack.isEmpty()){Queue queue1=new ArrayDeque<>(queue);Stack stack1=(Stack) stack.clone();pop=pop+stack1.pop()+" ";res(stack1,queue1,list,pop);}}

总结:最重要的是list一直没有变,而生成的子问题栈和队列一直在变,直至为空添加进list里面.理解到这个层面,这道题你就很okkk喽.

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！