题解 | #火车进站#

火车进站

https://www.nowcoder.com/practice/97ba57c35e9f4749826dc3befaeae109

import java.util.*;
// 队列表示未进站的火车
// 栈表示已进站的火车
// 每次火车进站后有两种选择:1.直接出站 2.等待下列火车进站  使用递归考虑
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        while (sc.hasNext()) {
            int n = sc.nextInt();
            // 未进站的火车
            Deque<Integer> queue = new LinkedList<>();
            // 已进站的火车
            Stack<Integer> stack = new Stack<>();

            for (int i = 0; i < n; i++) {
                queue.offer(sc.nextInt());
            }

            List<String> outQueueList = new ArrayList<>();

            // 获取所有出站队列保存到outQueueList
            processOutQueue(queue, stack, "", outQueueList);

            // 排序
            Collections.sort(outQueueList);
            for (String str : outQueueList) {
                System.out.println(str);
            }

        }
    }

    private static void processOutQueue(Deque<Integer> queue, Stack<Integer> stack,
                                        String outQueue, List<String> outQueueList) {
        {
            if (queue.isEmpty() && stack.isEmpty()) {
                outQueueList.add(outQueue);
            }

            if (!stack.isEmpty()) {
                int res = stack.pop();
                String tempQueue = outQueue + res + " ";
                processOutQueue(queue, stack, tempQueue, outQueueList);
                stack.push(res);
            }

            if (!queue.isEmpty()) {

                int res = queue.poll();
                stack.push(res);
                processOutQueue(queue, stack, outQueue, outQueueList);
                stack.pop();
                queue.addFirst(res);
            }

        }

    }

}

全部评论

相关推荐

牛客383479252号:9,2学生暑期实习失利开始投小厂,给这群人整自信了
点赞 评论 收藏
分享
自由水:这HR已经很好了,多的是已读不回和不读了
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务