AcWing 129. 火车进栈(Java)
原题链接
简单
算法1
Java 代码
import java.util.*;
//这道题一共有三个状态,每一步有两个操作,三个操作分别用集合(buffer),栈(stack),和一个整数(status)来表示。
public class Main{
void run(){
int n = sc.nextInt();
dfs(1, n);//status的初始状态就是1,然后一直往后加一,直到等于n。
}
void dfs(int status, int n){
if (cnt == 20){//cnt是记录的输出个数。如果已经输出了20个了,那就直接结束
return;
}
if (buffer.size() == n){//如果buffer的size等于了n,说明所有的车全部都在状态1中了,也就是全部都出来了,这时输出集合中全部的数,并且cnt加一
for(Object x:buffer)
System.out.print(x);
System.out.println();
cnt += 1;
}
if (!stack.isEmpty()){//第一种操作,前三步把状态2(车站中的车)中的车放到状态1(从车站出来的车)
int x = stack.peek();
buffer.add(x);
stack.pop();
dfs(status, n);
stack.push(x);//这一步和下一步还原状态
buffer.remove(buffer.size()-1);
}
if (status <= n){//第二种操作,把状态3(还没有进车站的车)的车放到状态2,
//因为先这一步一定比先进行上一中操作得到的数大,因为按字典序输出前20个,所以第一种操作放在前面。
stack.push(status);
dfs(status + 1 , n);//把状态3的车放在了状态2 ,那么再放是状态3的车的序号加一。
stack.pop();
}
}
private Stack<Integer> stack = new Stack<>();
private List buffer = new ArrayList();
private int cnt = 0;
private Scanner sc = new Scanner(System.in);
public static void main(String[] args){
Main m=new Main();
m.run();
}
}