题解 | #火车进站#
还是dfs，这是第二次自己递归调用栈一步一步调试出来的。注意，递归调用dfs，需要克隆栈状态和出栈顺序。
import java.util.*;
public class Main {
static List<List<Integer>> result = new ArrayList<>();
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] car = new int[n];
for (int i = 0; i < n; i++) {
car[i] = sc.nextInt();
}
List<Integer> sb = new ArrayList<>(); // 存储单词出站顺序
List<Integer> list = new ArrayList<>(); // 当做一个栈使用
dfs(list, car, sb, 0);
// 排序处理
List<String> sortedResult = new ArrayList<>();
while (result.size() != 0) {
List<Integer> listTmp = result.remove(0);
String str = listTmp.toString();
str = str.replaceAll(",", "");
sortedResult.add(str.substring(1, str.length()-1));
}
Collections.sort(sortedResult);
for (String str : sortedResult) {
System.out.println(str);
}
}
public static void dfs(List<Integer> list, int[] car, List<Integer> sb, int cur) {
if (cur == car.length - 1) {
sb.add(car[cur]);
while (!list.isEmpty()) {
sb.add(list.remove(list.size()-1));
}
result.add(sb);
return;
}
// 此位置直接进栈
list.add(car[cur]);
List<Integer> tmpList1 = new ArrayList<>(list);
List<Integer> tmpSb1 = new ArrayList<>(sb);
dfs(tmpList1, car, tmpSb1, cur+1);
// 此位置出栈（出栈元素加到sb中）
// 此处是用while，不能用if，因为可以一直出栈再栈空
while (!list.isEmpty()) {
sb.add(list.remove(list.size()-1));
List<Integer> tmpList2 = new ArrayList<>(list);
List<Integer> tmpSb2 = new ArrayList<>(sb);
dfs(tmpList2, car, tmpSb2, cur+1);
}
}
}
查看19道真题和解析