题解 | #火车进站#

运行时间：66ms
超过100.00% 用Java提交的代码
占用内存：13328KB
超过100.00% 用Java提交的代码

1. 递归，将出站顺序记为一个数字，对数字进行排序要比字符串排序快得多，如1,2,3记为123，这样可以使用TreeSet来自动排序。
2. 用数字还有一个好处就是数字是基本数据类型而不是引用数据类型，不需要考虑递归过程中对引用数据类型的改变。
3. 如果有n辆车，那么最终出站数字序列的量级一定是10^(n - 1)，比如3辆车的出站序列123的量级是100，判断递归终止的条件就是当前数字序列达到了量级10^(n - 1).
4. 最后将TreeSet里的数字序列依次取出来，因为每个数字的量级scale都是相同的，所以对于每个数字序列，可以很方便地从高位到低位取出每个数字进行字符串拼接。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.TreeSet;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] parts = br.readLine().split(" ");
        int[] identifiers = new int[n];
        for (int i = 0; i < n; i++) {
            identifiers[i] = Integer.parseInt(parts[i]);
        }

        Solution sl = new Solution();
        System.out.println(sl.getProgrammes(identifiers, n));
    }
}

class Solution {

    int num;
    int scale;
    int[] identifiers;

    public StringBuilder getProgrammes(int[] identifiers, int num) {
        this.num = num;
        this.identifiers = identifiers;
        scale = (int) Math.pow(10, num - 1);
        TreeSet<Integer> digitalForm = new TreeSet<>();
        dfs(digitalForm, 0, 0, 0);

        StringBuilder programmes = new StringBuilder();
        for (int digit : digitalForm) {
            int scale = this.scale;
            while (digit != 0) {
                programmes.append(digit / scale).append(" ");
                digit = digit % scale;
                scale /= 10;
            }
            programmes.append("\n");
        }
        return programmes;
    }

    public void dfs(TreeSet<Integer> digitForm, int programme, int station, int cur) {
        //进站
        if (cur < num) {
            int newStation = station * 10 + identifiers[cur];
            dfs(digitForm, programme, newStation, cur + 1);
        }
        //出站
        if (station != 0) {
            programme = programme * 10 + station % 10;
            station /= 10;
            if (programme / scale != 0) {
                digitForm.add(programme);
                return;
            }
            dfs(digitForm, programme, station, cur);
        }
    }
}