算法分析
(递归)
-
1、直接上y总的视频中的某一个时刻截图
-
2、维护好3个状态
-
state1表示出栈元素排队的状态,使用链表list维护
-
state2表示当前栈元素的状态,使用栈stack维护
-
state3表示当前第几个元素准备进栈,使用整数int维护
-
-
3、整个系统有两个操作情况
一:将整数state3的元素进入到state2栈中
二:将栈state2的元素出栈到state3链表中 -
4、由于题目要求按《字典序》输出前20种可能的出栈方案,所以需要优先执行二操作
注意:该2的20次方是操作次数的上界(为下一题130题做铺垫)
参考文献
参考y总的视频讲解
Java 代码
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.Scanner;
public class Main {
//维护好3个状态
static List<Integer> state1 = new ArrayList<Integer>();
static Stack<Integer> state2 = new Stack<Integer>();
static int state3 = 1;
static int cnt = 20;//执行20层
static int n;
public static void dfs()
{
if(cnt == 0) return;
//符号条件执行打印操作
if(state1.size() == n)
{
cnt --;
for(Integer i : state1) System.out.print(i);
System.out.println();
return;
}
//执行2操作
if(!state2.isEmpty())
{
state1.add(state2.pop());
dfs();
//回复现场
state2.push(state1.remove(state1.size() - 1));
}
//执行1操作
if(state3 <= n)
{
state2.push(state3);
state3 ++;
dfs();
//恢复现场
state3 --;
state2.pop();
}
//执行1操作
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
dfs();
}
}