静态链表的做法有没有人看看
查看原帖
静态链表的做法有没有人看看
383198
xwfro楼主2024/8/8 18:04

不知道错在了哪里,感觉逻辑还是挺清晰的

#include <cstring>
#include <iostream>
#include <string>
#include <unordered_map>

struct node
{
    int id;
    int nextid;
    int group;
} nodes[100005];

std::unordered_map<int, int> find_end;
std::unordered_map<int, int> find_group;

int main()
{
    int n, m;
    std::cin >> n >> m;

    int start = -1;
    int end = -1;

    for (int i = 0; i < n; i++)
    {
        int gp;
        std::cin >> gp;
        nodes[i].id = i;
        nodes[i].group = gp;
        nodes[i].nextid = -1; // Initialize nextid to -1
    }

    for (int i = 0; i < m; i++)
    {
        find_group[i] = 0;
        find_end[i] = -1;
    }

    int T;
    std::cin >> T;
    // std::cin.ignore(); // Ignore the newline character after the integer input
    std::string process;
    for (int i = 0; i < T; i++)
    {
        std::cin >> process;

        if (process == "push")
        {
            int num;
            std::cin >> num;
            find_group[nodes[num].group]++;
            if (start == -1)
            {
                start = num;
                end = num;
                find_end[nodes[num].group] = num;
                continue;
            }
            if (find_group[nodes[num].group] == 1)
            { // First element in the group
                nodes[end].nextid = num;
                end = num;
                find_end[nodes[num].group] = num;
            }
            else if (find_group[nodes[num].group] > 1)
            { // Subsequent elements in the group
                if (find_end[nodes[num].group] != end)
                {
                    nodes[num].nextid = nodes[find_end[nodes[num].group]].nextid;
                    nodes[find_end[nodes[num].group]].nextid = num;
                    find_end[nodes[num].group] = num;
                }
                else
                {
                    nodes[num].nextid = nodes[find_end[nodes[num].group]].nextid;
                    nodes[find_end[nodes[num].group]].nextid = num;
                    find_end[nodes[num].group] = num;
                    end = num;
                }
            }
        }
        if (process == "pop")
        {
            // if (start == -1)
            // {
            //     std::cerr << "Error: Attempt to pop from an empty list." << std::endl;
            //     return 1;
            // }

            if (find_group[nodes[start].group] == 1)
            { // Last element in the group
                find_group[nodes[start].group] = 0;
                find_end[nodes[start].group] = -1;
            }
            else if (find_group[nodes[start].group] > 1)
            {
                find_group[nodes[start].group]--;
            }

            std::cout << nodes[start].id << std::endl;
            start = nodes[start].nextid;
            if (start == -1)
            {
                end = -1;
            }
        }
    }

    return 0;
}
```cpp
2024/8/8 18:04
加载中...