火车进出站问题

阳光穿透心脏的1/2处 2023-06-19 05:27 7阅读 0赞

## 火车进出站问题 ##

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

解题思路：**数组的全排序+出站顺序的判定**。  
  详细过程：  
   1、数组的全排序：分治算法的经典。可参考：[数组全排序][Link 1]。我这里简单说一下，利用分治思想将大问题化为小问题，一共有n个元素，第一个位置上可以有n种选择，第二个位置上有n-1种选择，因此，**对于当前位置i来讲，将i后的所有元素都与i上的元素进行交换，若交换产生了全排序，则需要将原本i的元素再交换回来以供下次的交换使用。** 由于是采用递归，只需要关注当前位置i上的所有可能即可，eg：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ5MDQ0MA_size_16_color_FFFFFF_t_70]  
   只需要关注i位置的3中不同选择即可，前面的已被选好不需要关注，后面的还未选留给下次递归实现，本次递归也不需要关注。  
   对于该位置来讲，**后面的所有剩余元素+当前该位置上的元素，都有可能位于当前位置上**，因此，每次将当前位置上的元素替换为之后剩余元素中的某个值后，**在该值处于当前位置获取全排列结束后，需要将原来的值再替换回来**，否则，会导致重复排列。  
   代码实现：

public static void allSort(int[] arr,int start,int end,Queue<int[]> queue){
            if (start==end){
                queue.add(arr.clone());
            }else {
                for (int i = start; i <= end ; i++) {
                    swap(arr,start,i);
                    allSort(arr,start+1,end,queue);
                    swap(arr,start,i);
                }
            }
        }

2、判断数组pop是否能作为数组arr的出栈数组：将arr数组中的元素依次加入到stack栈中，在每次加入后循环判断栈顶元素（栈非空）与出栈数组pop中index（默认为0）对应的值是否相同，若相同，则将该值出栈，并将index++，最终只需要判断该栈是否为空即可，为空说明可以作为出栈数组。  
   **入栈的同时进行出栈操作，如果最终的栈为空，说明栈中的元素全部出栈，也就说明当前出栈顺序与入栈顺序可以匹配。**  
   代码实现：

public static boolean isPop(int[] arr,int[] pop){
            Stack<Integer> stack = new Stack<>();
            int index = 0;
            for (int i = 0; i < arr.length; i++) {
                stack.push(arr[i]);
                while (!stack.empty()&&pop[index]==stack.peek()){
                    stack.pop();
                    index++;
                }
            }
            return stack.isEmpty();
        }

[Link 1]: https://blog.csdn.net/u013013553/article/details/79222040
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ5MDQ0MA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191204175644430.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ5MDQ0MA==,size_16,color_FFFFFF,t_70