4 solutions

  • 1
    @ 2024-10-3 22:55:21 
    //
// Created by jiaxiaofeng on 2024/10/3.
//

#include "iostream"
#include "vector"
#include "deque"
#include "unordered_map"
using namespace std;

vector<int> mouse_out(vector<int>& nums){
    int n = nums.size();
    vector<int> res;
    unordered_map<int, int> p;
    deque<int> q;
    for(int i = 0; i < n; i++){
        if(p.find(nums[i]) == p.end()){
            q.push_back(nums[i]);
            p[nums[i]]++;
        }else{
            while (!q.empty() && q.back() != nums[i]){
                res.push_back(q.back());
                p.erase(q.back());
                q.pop_back();
            }
            if(q.back() == nums[i] && !q.empty()){
                res.push_back(q.back());
            }
        }
    }

    while (!q.empty()){
        res.push_back(q.back());
        q.pop_back();
    }
    return res;

}

int main(){
    // 终端输入一个vector
    vector<int> nums;
    int temp;
    while (cin >> temp){
        nums.push_back(temp);
        if(cin.get() == '\n')
            break;
    }
    vector<int> res = mouse_out(nums);
    for(auto &i: res){
        cout << i << " ";
    }
    return 0;

}
    • 0
      @ 2024-10-27 10:10:47 
      data = list(map(int,input().split()))
stack = []
st = set()
res = []
for x in data:
    if x in st:
        while stack[-1]!=x:
            now = stack.pop()
            res.append(now)
            st.remove(now)
        res.append(stack[-1])
    else:
        stack.append(x)
        st.add(x)
res = res + stack[::-1]
print(*res)
      • 0
        @ 2024-9-22 16:17:58 
        #include <iostream>
#include <sstream>
#include <string>
#include <stack>
#include <unordered_set>
#include <algorithm>
#include <vector>
using namespace std;

int main()
{
    string s;
    getline(cin, s);
    stringstream ss(s);
    int t;
    stack<int> stk;
    unordered_set<int> set;
    vector<int> res;
    while (ss>>t) {
        if(!set.count(t)){
        stk.push(t);
        set.insert(t);
        }else {
            while (stk.top()!=t&&!stk.empty()) {
            //其他老鼠出来给要进去的老鼠腾地方
                res.push_back(stk.top());
                set.erase(stk.top());
                stk.pop();
            }
            res.push_back(stk.top());
        }
    }
    while(!stk.empty()){
         res.push_back(stk.top());
         stk.pop();
    }
    for (int i=0; i<res.size(); i++) {
        if(i!=0){
            cout<<" ";
        }
        cout<<res[i];
    }
}
        • 0
          @ 2024-8-28 20:17:47

          题面描述:

          在这个问题中，我们处理的是老鼠进出一个狭小的老鼠洞，遵循栈的特性。每只老鼠都有一个独特的编号，进洞后可以出洞并再次进入，编号可能重复以表示老鼠重新进洞。输入为一行由空格分隔的数字序列，表示老鼠的进洞顺序。输出则是老鼠的出洞顺序，以空格分隔，遵循后进先出的原则。例如，输入为“1 2 3 2 3 4 5”，则输出为“3 2 5 4 3 2 1”，表示老鼠出洞的顺序。

          思路：栈 + 哈希表

          1.关键因素:"假定序列最后洞是满的" + 样例分析

          我们可以理解为:默认情况下老鼠不出洞。除非序列出现重复时。

          2.栈模拟 + 哈希表:

          考虑遍历每一个入洞的老鼠编号，并将其加入到栈中模拟为洞里的先进后出。

          引入哈希表：因为可能出现重复的老鼠，所以我们用哈希表记录一下某个元素是否在栈中。

          假设遍历的这个老鼠在之前出现过了，那就将这个老鼠在栈中后面的都先弹出去，然后再将其弹出。此时就可以将弹出的顺序加入到答案中。

          注意每次将老鼠弹出后要将map也做相应的更新。最后将栈中还存有的老鼠依次弹出加入到答案中。

          题解概述

          在这个问题中，我们需要模拟老鼠进出一个狭小的老鼠洞，遵循栈的后进先出原则。关键在于处理老鼠编号的重复情况，以确保最后的出洞顺序正确。为了实现这一点，我们可以使用栈和哈希表来管理老鼠的状态。

          关键因素

          1. 满洞的假设：题目说明序列的最后状态是洞满的，这意味着我们只需关注在序列中出现的老鼠编号以及它们的进出顺序。默认情况下，老鼠不出洞，除非在序列中再次出现相同的编号。

          2. 重复的处理：当我们遍历进洞的老鼠编号时，如果发现某个编号在栈中已经存在，说明这只老鼠之前已经出过洞，此时我们需要将栈中该老鼠后面的所有老鼠依次弹出，直到将这只老鼠弹出为止。

          实现步骤

          1. 使用栈模拟洞的状态：

            • 使用一个栈来存储当前在洞中的老鼠编号，确保它们遵循后进先出的顺序。

          2. 使用哈希表记录老鼠状态：

            • 使用一个哈希表（或集合）来记录老鼠编号是否已经在栈中。这可以帮助我们快速判断某只老鼠是否已经在洞中。

          3. 遍历输入序列：

            • 对于每一个老鼠编号：
              • 如果该编号不在哈希表中，说明它是第一次进洞，将其压入栈并标记为已存在。
              • 如果该编号已经在哈希表中，意味着它曾经出过洞，此时我们需要：
                • 依次弹出栈中的老鼠，直到弹出该老鼠为止，同时将弹出的老鼠编号加入到答案列表中。
                • 弹出后更新哈希表，以反映当前的状态。

          4. 处理栈中剩余的老鼠：

            • 在处理完输入序列后，栈中可能还有一些老鼠未出洞。我们需要将这些老鼠依次弹出，并将它们的编号加入到答案列表中。

          5. 输出结果：

            • 最后输出答案列表中老鼠的编号，确保顺序正确。

          代码

          Java

          import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        List<Integer> arr = new ArrayList<>();
        
        // 读取输入直到文件结束符（EOF）或换行
        while (scanner.hasNextInt()) {
            arr.add(scanner.nextInt());
        }

        Deque<Integer> stack = new ArrayDeque<>(); // 用来模拟栈操作
        Set<Integer> st = new HashSet<>(); // 用来检查元素是否在栈中
        List<Integer> res = new ArrayList<>(); // 用来存储结果

        for (int x : arr) {
            // 如果 x 在集合中，弹出栈顶元素直到栈顶元素等于 x
            if (st.contains(x)) {
                while (stack.peek() != x) {
                    int now = stack.pop();
                    // 从集合中删除元素
                    st.remove(now);
                    // 记录弹出的元素
                    res.add(now);
                }
                res.add(stack.peek());
            } else {
                // 如果 x 不在集合中，直接入栈
                stack.push(x);
                st.add(x);
            }
        }

        // 将栈中的剩余元素依次加入结果（逆序）
        while (!stack.isEmpty()) {
            res.add(stack.pop());
        }

        // 输出结果
        for (int x : res) {
            System.out.print(x + " ");
        }
        System.out.println();

        scanner.close();
    }
}

          Python

          arr = list(map(int, input().split()))
stack = []
# 用集合来判断元素是否在栈中
st = set()
res = []
for x in arr:
    # 如果x在集合中，那么一直弹出栈顶元素，直到栈顶元素等于x
    if x in st:
        while stack[-1] != x:
            now = stack.pop()
            # 从集合中删除元素
            st.remove(now)
            # 记录弹出的元素
            res.append(now)
        res.append(stack[-1])
    else:
        # 如果x不在集合中，那么直接入栈
        stack.append(x)
        st.add(x)
res += stack[::-1]
print(*res)

          C++

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

using namespace std;

int main() {
    vector<int> arr;
    int x;

    // 读取输入直到文件结束符（EOF）或换行
    while (cin >> x) {
        arr.push_back(x);
    }

    stack<int> s; // 用来模拟栈操作
    unordered_set<int> st; // 用来检查元素是否在栈中
    vector<int> res; // 用来存储结果

    for (int x : arr) {
        // 如果 x 在集合中，弹出栈顶元素直到栈顶元素等于 x
        if (st.count(x)) {
            while (s.top() != x) {
                int now = s.top();
                s.pop();
                // 从集合中删除元素
                st.erase(now);
                // 记录弹出的元素
                res.push_back(now);
            }
            res.push_back(s.top());
        } else {
            // 如果 x 不在集合中，直接入栈
            s.push(x);
            st.insert(x);
        }
    }

    // 将栈中的剩余元素依次加入结果（逆序）
    while (!s.empty()) {
        res.push_back(s.top());
        s.pop();
    }

    // 输出结果
    for (int x : res) {
        cout << x << " ";
    }
    cout << endl;

    return 0;
}
          • 1

          2024.8.28-秋招-第1题-老鼠串门

          Information

          ID
          104
          Time
          1000ms
          Memory
          256MiB
          Difficulty
          5
          Tags
          # Submissions
          681
          Accepted
          239
          Uploaded By
          1. About
          2. Contact Us
          3. Privacy
          4. Terms of Service
          5. Copyright Complaint
          6. Language
          7. Legacy mode
          8. Theme
          2. 湘ICP备2023007293号
          3. Worker 0, 23ms
          4. Powered by Hydro v4.14.1 Community