【每日刷题】Day100

【每日刷题】Day100

🥕个人主页：开敲🍉

🔥所属专栏：每日刷题🍍

🌼文章目录🌼

1. 【模板】堆_牛客题霸_牛客网 (nowcoder.com)

2. 【模板】链表_牛客题霸_牛客网 (nowcoder.com)

3. 【模板】队列_牛客题霸_牛客网 (nowcoder.com)

1. 【模板】堆_牛客题霸_牛客网 (nowcoder.com)

//C++堆(大堆)的实现。

#include <iostream>

#include <vector>

using namespace std;

class Heap

{

public:

    Heap()

        :_size(0)

    {}

    void Swap(int& x,int& y)

    {

        int tmp = x;

        x = y;

        y = tmp;

    }

//向下调整

    void AdjustDown(int parents)

    {

        int child = parents*2+1;

        while(child<_size)

        {

            if(child+1<_size&&_arr[child+1]>_arr[child])

                child++;

            if(_arr[child]>_arr[parents])

                Swap(_arr[child],_arr[parents]);

            else

                break;

            parents = child;

            child = parents*2+1;

        }

    }

//向上调整

    void Adjustup(int child)

    {

        int parents = (child-1)/2;

        while(child>0)

        {

            if(_arr[child]>_arr[parents])

                Swap(_arr[child],_arr[parents]);

            else

                break;

            child = parents;

            parents = (child-1)/2;

        }

    }

//入堆

    void push(int val)

    {

        _arr.push_back(val);

        Adjustup(_size);

        _size++;

    }

//删除堆顶元素

    void pop()

    {

        if(_size==0)

            cout<<"empty"<<endl;

        else

        {

            cout<<_arr[0]<<endl;

            Swap(_arr[0],_arr[_size-1]);

            _arr.pop_back();

            _size--;

            AdjustDown(0);

        }

    }

//获取堆顶元素

    void top()

    {

        if(_size==0)

            cout<<"empty"<<endl;

        else

            cout<<_arr[0]<<endl;

    }

 

private:

    vector<int> _arr;

    size_t _size;

};

int main()

{

    Heap h;

    int n = 0;

    cin>>n;

    while(n--)

    {

        int data = 0;

        string s;

        cin>>s;

        if(s=="push")

        {

            cin>>data;

            h.push(data);

        }

        if(s=="top")

            h.top();

        if(s=="pop")

            h.pop();

    }

    return 0;

}

2. 【模板】链表_牛客题霸_牛客网 (nowcoder.com)

//C++链表模拟实现。

#include <iostream>

#include <list>

using namespace std;

 

class List

{

    class list_node

{

public:

    list_node(int y = -2147483648)

        :next(nullptr)

        ,val(y)

    {}

    int val;

    list_node* next;

};

public:

    List()

        :head(new list_node)

        ,_size(0)

    {}

//打印链表

    void printf()

    {

        if(_size)

        {

            list_node* pmove = head->next;

            while(pmove)

            {

                cout<<pmove->val<<' ';

                pmove = pmove->next;

            }

        }

        else

            cout<<"NULL";

    }

//在值为x的节点前插入值为y的节点

    void Insert(int x,int y)

    {

        list_node* pnext = head->next;

        list_node* prev = head;

        while(pnext&&pnext->val!=x)

        {

            prev = prev->next;

            pnext = pnext->next;

        }

        list_node* newnode = new list_node(y);

        prev->next = newnode;

        newnode->next = pnext;

        _size++;

    }

//删除值为x的节点

    void Delete(int x)

    {

        list_node* pmove = head->next;

        list_node* prev = head;

        while(pmove&&pmove->val!=x)

        {

            prev = prev->next;

            pmove = pmove->next;

        }

        if(pmove)

        {

            prev->next = pmove->next;

            _size--;

            delete pmove;

        }

    }

private:

    list_node* head;

    size_t _size;

};

int main()

{

    List l;

    int n = 0;

    cin>>n;

    while(n--)

    {

        int x,y;

        string s;

        cin>>s;

        if(s=="insert")

        {

            cin>>x>>y;

            l.Insert(x, y);

        }

        if(s=="delete")

        {

            cin>>x;

            l.Delete(x);

        }

    }

    l.printf();

    return 0;

}

3. 【模板】队列_牛客题霸_牛客网 (nowcoder.com)

//C++队列的实现。

#include <iostream>

#include <list>

#include <string>

using namespace std;

class Queue

{

    class queue_node

{

public:

    queue_node(int _val = -2147483648)

        :next(nullptr)

        ,val(_val)

    {}

    int val;

    queue_node* next;

};

public:

    Queue()

        :head(new queue_node)

        ,pmove(head)

        ,_size(0)

    {}

//获取队头元素

    void front()

    {

        if(_size)

            cout<<head->next->val<<endl;

        else

            cout<<"error"<<endl;

    }

//队尾插入元素

    void Push(int data)

    {

        queue_node* newnode = new queue_node(data);

        pmove->next = newnode;

        pmove = pmove->next;

        _size++;

    }

//队头删除元素

    void pop()

    {

        if(_size)

        {

            queue_node* pnext = head->next->next;

            queue_node* pcur = head->next;

            cout<<pcur->val<<endl;

            if(pcur==pmove)

                pmove = head;

            head->next = pnext;

            delete pcur;

            _size--;

        }

        else

            cout<<"error"<<endl;

    }

private:

    queue_node* head;

    queue_node* pmove;

    size_t _size;

};

int main()

{

    Queue q;

    int n;

    cin>>n;

    while(n--)

    {

        int data;

        string s;

        cin>>s;

        if(s=="push")

        {

            cin>>data;

            q.Push(data);

        }

        if(s=="pop")

            q.pop();

        if(s=="front")

            q.front();

    }

    return 0;

}