【牛客】火车进站（字典序+栈的压入弹出序列+字符串字典序）

偏执的太偏执、 2021-10-03 02:18 339阅读 0赞

给定一个正整数N代表火车数量，0<N<10，接下来输入火车入站的序列，一共N辆火车，每辆火车以数字1-9编号。要求以字典序排序输出火车出站的序列号。

输入描述:

有多组测试用例，每一组第一行输入一个正整数N（0<N<10），第二行包括N个正整数，范围为1到9。

输出描述:

输出以字典序从小到大排序的火车出站序列号，每个编号以空格隔开，每个输出序列换行，具体见sample。

示例1

输入

3  
1 2 3

输出

1 2 3  
1 3 2  
2 1 3  
2 3 1  
3 2 1

import java.util.*;
    
    public class Main {
        static LinkedList<int[]> list = new LinkedList<>();
        static LinkedList<String> list1 = new LinkedList<>();
        public static void swap(int [] array,int i,int j){
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
        递归求出所有字典序
        public static void transAll(int [] array,int start,int end){
            if(start == end){
                int [] temp = array.clone();
                list.add(temp);
                return;
            }
            for(int i = start;i<=end;i++){
                swap(array,i,start);
                transAll(array,start+1,end);
                swap(array,i,start);
            }
        }
        //判断
        public static boolean panduan(int [] array1,int [] array2){
             Stack<Integer> stack = new Stack<>();
             int j = 0;
             for(int i =0;i<array1.length;i++){
                 stack.push(array1[i]);
                 while (!stack.isEmpty() && stack.peek() == array2[j]){
                     stack.pop();
                     j++;
                 }
             }
             return stack.isEmpty();
        }
            //转化成String
        public static String transforString(int []array){
            StringBuilder sb = new StringBuilder();
            for(int i = 0;i<array.length;i++){
                sb.append(array[i]);
                if(i != array.length-1 )
                    sb.append(" ");
            }
            return sb.toString();
        }
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            while (sc.hasNextInt()){
                int n = sc.nextInt();
                int [] array = new int[n];
                for(int i = 0;i<n;i++){
                    array[i] = sc.nextInt();
                }
                transAll(array,0,array.length-1);
                for(int[] num:list){
                    if(panduan(array,num) == true) {
                        list1.add(transforString(num));
                    }
                }
                Collections.sort(list1);
                for(String s:list1)
                    System.out.println(s);
            }
        }
    
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI3MTA4Ng_size_16_color_FFFFFF_t_70][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI3MTA4Ng_size_16_color_FFFFFF_t_70]: /images/20211003/5b90388fcb264ebdacb40f7a74ba1af5.png