C++ HashMap and linked list


  • 0
    B

    HashMap<timestamp, Node*> to quickly access list node, then we can edit, remove, or insert node every quickly

    class HitCounter {
    public:
        struct Node
        {
            int time;
            int count;
            Node * prev;
            Node * next;
            Node(int t):time(t), count(1), prev(NULL), next(NULL){};
        };
        
        Node * head;
        Node * tail;
        unordered_map<int, Node*>mp;
        int size;
        int last;
        /** Initialize your data structure here. */
        HitCounter() {
            size = 0;
            last = -1;
            head = new Node(0);
            tail = new Node(0);
            head -> next = tail;
            tail -> prev = head;
        }
        
        void update(int timestamp)
        {
            last = timestamp;
            while(size > 0 && timestamp - head -> next -> time >= 300)
            {
                auto node = head -> next;
                size -= node -> count;
                mp.erase(node -> time);
                node -> next -> prev = head;
                head -> next = node -> next;
                delete node;
            }
        }
        
        /** Record a hit.
            @param timestamp - The current timestamp (in seconds granularity). */
        void hit(int timestamp) {
            update(timestamp);
            if(size > 0 && tail->prev->time == timestamp) mp[timestamp] -> count += 1;
            else
            {
                auto node = new Node(timestamp);
                mp[timestamp] = node;
                node -> prev = tail -> prev;
                node -> next = tail;
                tail -> prev -> next = node;
                tail -> prev = node;
            }
            size++;
        }
        
        /** Return the number of hits in the past 5 minutes.
            @param timestamp - The current timestamp (in seconds granularity). */
        int getHits(int timestamp) {
                update(timestamp);
                return size;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.