老鼠串门 - 华为机试真题题解

考试平台： 时习知

分值： 100分

考试时间： 两小时（共3题）

题目描述

现有一个狭小的老鼠洞，每次仅能一只老鼠进或者出(类似于栈的特性)，如果通道里有多只老鼠，那么先进洞的老鼠会比晚进洞的老鼠出来更晚，假如有一窝老鼠来串门，我们给每只老鼠单独编个数字号码，1、2、3 ...

允许老鼠进洞后，又出洞，再次进洞，且若众多老鼠都挤满到洞口了，则不再会有老鼠进洞，最后出洞的顺序就按洞口到洞底的老鼠编号输出。

假如老鼠进洞的顺序是1、2、3，那么可能的出洞顺序是3、2、1，考虑到洞未满的情况下，老鼠进洞后又出洞了，也可能是1、2、3等，但不可能是3、1、2。

现给定一个进洞序列，序列里数字可能重复，重复表示出洞后再次进洞，假定序列最后洞是满的，序列长度小于10000。

即老鼠编号范围是[1,10000]。请给出老鼠出洞的顺序?

输入

输入一行数字数列，每个数字之间用英文空格分隔。如

1 2 3

输出

3 2 1

示例1

输入：
1 2 3 2 3 4 5

输出：
3 2 5 4 3 2 1

解释： 
123后又出现2，说明2号老鼠是之前已经出洞了，再重新进洞，2号老鼠要出洞，需要3号老鼠先出洞，因而最先出洞的是3号老鼠，接着是2号老鼠。2号重新进洞后，接着3号又进洞，再是4号和5号，5号后面没其它的说明洞口满了。那么出洞顺序 就是 3 2 5 4 3 2 1

示例2

输入：
1 1 2 3 4 4 5

输出：
1 4 5 4 3 2 1

解释： 
1后面又是1，说明1号老鼠进洞后又出洞了，接着又进洞，接着是2、3、4号老鼠进洞，接着又4号老鼠进洞，说明4号老鼠也是出洞了再进洞的，5号后面没其它的说明洞口满了。那么出洞顺序 就是 1 4 5 4 3 2 1

题解

该题目属于栈的应用，具有典型的“先进后出”特性，类似于栈的操作。题目要求模拟老鼠进洞出洞的顺序，因此需要通过栈来保存进洞的老鼠编号，当老鼠出洞时，依次从栈中取出并按顺序输出。

解题思路

1. 栈的特点：栈是后进先出的数据结构，适合处理老鼠进洞的逻辑。每只老鼠进洞相当于入栈，老鼠出洞则相当于出栈。
2. 检测是否重复进洞：当老鼠的编号再次出现时，说明它已经出洞，再次进洞前，洞中其他的老鼠要依次出洞。
3. 顺序处理：每次读入一个老鼠编号时，检查它是否已经在洞里。如果是重复编号，则开始出洞操作，将编号放入结果序列，直到该老鼠重新进洞。
4. 最后出洞顺序：当所有编号处理完后，洞里剩下的老鼠依次出洞，将其加入输出序列。

时间复杂度

• 每个老鼠编号最多进洞和出洞一次，因此时间复杂度为 O(n)，其中 n 是老鼠进洞序列的长度。

空间复杂度

• 需要使用栈来存储当前在洞中的老鼠，最坏情况下栈的大小为 O(n)。

Java

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

/**
 * @author code5bug
 */
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String[] arr = in.