题解 | #火车站出站#

为什么这个递归不需要终止条件？

这个不是栈牛逼，这个对递归思路的运用达到了登峰造极之境界。

代码牛！脑瓜子都想秃噜皮了

非常优秀的思路和代码，bravo！ 给所有代码打了注释，帮助后来的同学理解: public class Main { static List<string> l = new ArrayList<>(); public static void main(String[] args) { Scanner in = new Scanner(System.in); while (in.hasNextInt()) { l.clear(); //static variable has to be cleared each time int nums = in.nextInt(); //number of trains int[] id = new int[nums]; //used to store the incoming sequence of trains Stack<integer> stack = new Stack<>(); //stack acts like the station for (int i =0; i< nums; i++) { id[i] = in.nextInt(); } //fill out the incoming sequence trainOut(id, 0, stack, "", 0); //Sort the outcome Collections.sort(l); for (String str: l) { System.out.println(str); } } in.close(); } public static void trainOut(int[] id, int i, Stack<integer> s, String str, int n) { // i indicates the position we are in the incoming sequence, n indicates the position we are in the outbound sequence. if ( n == id.length) { //It's like what we do in dfs/backtracking, we set up an ending condition //When we reached the end of the sequence, we add this answer to the output l.add(str); } if (!s.empty()) { //If we still have train in our station, we can either let another train in, or we can ride this train out. int temp = s.pop(); //We first try ride this train out. trainOut(id, i, s, str + temp + " ", n+1); //we need to add space to our answer s.push(temp); //By pushing back, we can get our initial condition in this level of dfs back, and try move this train back and see what happens. } if ( i < id.length) { //if we still have incoming trains s.push(id[i]); //let one train in trainOut(id, i+1, s, str, n); //see what we can do based on this condition s.pop(); //after this line we will get back to the previous level of recursion //so we need to restore the stack as they are literally using the same stack at the same address } } }</integer></integer></string>

我的思路和你一样,但是我的少了还原那步,一直想不到这一步,真的厉害

为什么进站不加stack.pop();出站不加 stack.push(temp);，就只有一种结果3 2 1

是不是少了递归的出口

import java.util.*; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { static List<string> output = new ArrayList<>(); public static void main(String[] args) { Scanner in = new Scanner(System.in); int count = in.nextInt(); int[] numbers = new int[count]; for (int i = 0; i < count; i++) { numbers[i] = in.nextInt(); } Stack<integer> stack = new Stack<>(); String curOut = ""; process(numbers,stack,0,curOut); Collections.sort(output); for(String curr:output){ System.out.println(curr); } } /** * stack要么进，要么出。先进一个，处理完这个进的，然后恢复原样；再出，处理完这个出的，就完事了。 * @param numbers 编号数组 * @param stack 核心栈 * @param i 当前编号 * @param curOut 当前已经出栈的数字 */ public static void process(int[] numbers, Stack<integer> stack, int i, String curOut) { //如果出栈数字已经满了，就先添加 if(curOut.length() == numbers.length) { output.add(curOut); } //如果出栈的数字没有满，此时可以出栈也可以进栈，都可以。 //这里先做出栈 //出栈需要建立在栈本身不为空的基础上 if(!stack.isEmpty()) { //出栈 int temp = stack.pop(); //继续后面的动作，一条路走到黑 //出栈，该数组添加到temp process(numbers,stack,i,curOut + temp); //这种出栈的场景走完后，下一个场景，进栈，不过先恢复原样 stack.push(temp); } //开始做入栈场景 //入账时要确保还有数据入账 if (i < numbers.length) { //入账 int temp2 = numbers[i]; stack.push(temp2); //继续后面的操作，一条路走到黑 //i位置移动到下一个 process(numbers,stack,i+ 1,curOut); //这种场景走完后，恢复原样 stack.pop(); } } } 把大佬的代码研究了几天，注释了一下</integer></integer></string>

感觉大脑的cpu烧了

这个栈真的牛逼

很秀，栈处理的逻辑复杂了就很难理解，看了很久才懂

调试都跟不上这脑瓜子

真是天才

这个聪明