华为笔试华为笔试题 0828

笔试时间：2024年08月28日秋招

历史笔试传送门：2023秋招笔试合集

第一题

题目：老鼠串门

现有一个狭小的老鼠洞，每次仅能一只老鼠进或者出（类似于栈的特性），如果通道里有多只老鼠，那么先进洞的老鼠会比晚进洞的老鼠出来更晚，假如有一窝老鼠来串门，我们给每只老鼠单独编个数字号码，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 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。

样例输入二

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。

参考题解

栈模拟 + 哈希表。使用一个栈和哈希表来进行统计。遍历数组，使用哈希表来统计所有已经出现过的元素。用栈来模拟，当当前元素已经出现过且与栈顶元素不相等的时候，弹出栈顶元素（此时说明有一个老鼠已经跑出来过了）如果当前元素未出现过，直接进入栈即可。

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
#include <sstream>
#include <vector>
#include <stack>
#include <unordered_set>
#include <algorithm>

int main() {
    string input;
    getline(cin, input);
    istringstream iss(input);
    vector<int> seq;
    int num;
    while (iss >> num) {
        seq.push_back(num);
    }

    stack<int> sk;
    unordered_set<int> occ;
    vector<int> res;

    for (int num : seq) {
        if (occ.find(num) != occ.end()) {
            while (!sk.empty() && sk.top() != num) {
                int tp = sk.top();
                sk.pop();
                res.push_back(tp);
                occ.erase(tp);
            }
            if (!sk.empty() && sk.top() == num) {
                res.push_back(num);
            }
        } else {
            occ.insert(num);
            sk.push(num);
        }
    }

    while (!sk.empty()) {
        res.push_back(sk.top());
        sk.pop();
    }

    for (size_t i = 0; i < res.size(); ++i) {
        cout << res[i];
        if (i < res.size() - 1) {
            cout << " ";
        }
    }
    cout << endl;

    return 0;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] input = scanner.nextLine().split(" ");
        List<Integer> seq = new ArrayList<>();
        for (String s : input) {
            seq.add(Integer.parseInt(s));
        }

        Stack<Integer> sk = new Stack<>();
        Set<Integer> occ = new HashSet<>();
        List<Integer> res = new ArrayList<>();

        for (int num : seq) {
            if (occ.contains(num)) {
                while (!sk.isEmpty() && sk.peek() != num) {
                    int tp = sk.pop();
                    res.add(tp);
                    occ.remove(tp);
                }
                if (!sk.isEmpty() && sk.peek() == num) {
                    res.add(num);
                }
            } else {
                occ.add(num);
                sk.push(num);
            }
        }

        while (!sk.isEmpty()) {
            res.add(sk.pop());
        }

        System.out.println(res.stream().map(String::valueOf).reduce((a, b) -> a + " " + b).orElse(""));
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

seq = [int(c) for c in input().split()]

sk = []
occ = set()
res = []
for i, num in enumerate(seq):
    if num in occ:
        while sk and sk[-1] != num:
            tp = sk.pop()
            res.append(tp)
            occ.remove(tp)
        if sk[-1] == num:
            res.append(num)
    else:
        occ.add(num)
        sk.append(num)

print(' '.join((map(str, res + sk[::-1]))))