146. LRU Cache

#LinkedList

題目

LeetCode: 146. LRU Cache

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

The functions get and put must each run in O(1) average time complexity.

想法

  1. 基本上就是操作 linked list
  2. 在存取 key 時就把 key 的 node 移動到 head
  3. 要把東西丟掉就從尾巴
  4. stl 有 std::list 可以使用
    1. 不過在移動 node 時，由於 c++ ref 上並沒有寫明假如在同一個 list 上是否可以 splice，所以這裡是先刪除再加入

Ptr Code

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127

struct Node {
    Node* prev = nullptr;
    Node* next = nullptr;
    
    int data = 0;
    
    Node(int data = 0): data(data) {}
};

// linkNode link a->b
inline void linkNode(Node* a, Node* b) {
    a->next = b;
    b->prev = a;
}

// linkNode link a->b->c
inline void linkNode(Node* a, Node* b, Node* c) {
    linkNode(a, b);
    linkNode(b, c);
}

class LinkList {
private:
    // init: head -> tail
    Node* head_;
    Node* tail_;
    
    int size_ = 0;
public:
    
    // Remove copy operation
    LinkList(const LinkList&) = delete;
    LinkList& operator=(const LinkList&) = delete;

    LinkList(): head_(new Node()), tail_(new Node()){
        head_->next = tail_;
        tail_->prev = head_;
    }
    
    ~LinkList() {
        auto cur = head_;
        while (cur != nullptr) {
            auto tmp = cur;
            cur = cur->next;
            delete tmp;
        }
    }
    
    Node* pushHead(int data) {
        // before: head->n1
        // after: head->n0->n1
        auto n0 = new Node(data);
        
        linkNode(head_, n0, head_->next);
        ++size_;
        
        return n0;
    }
    
    void nodeToHead(Node* n) {
        // before: ..n1->n->n0..
        // after: head->n->h0..
        
        linkNode(n->prev, n->next);
        linkNode(head_, n, head_->next);
    }
    
    int popTail() {
        // before: n1->n0->tail
        // after: n1->tail;
        auto n = tail_->prev;
        linkNode(n->prev, n->next);
        --size_;
        int tmp = n->data;
        delete n;
        
        return tmp;
    }
    
    int size() const {
        return size_;
    }
};

class LRUCache {
public:
    LRUCache(int capacity): sizeLimit_(capacity), cache_(1e4 + 2) {
    }
    
    int get(int key) {
        auto& pack = cache_[key];
        if (pack.node == nullptr) {
            return -1;
        }
        
        queue_.nodeToHead(pack.node);
        return pack.value;
    }
    
    void put(int key, int value) {
        auto& pack = cache_[key];
        if (pack.node != nullptr) {
            queue_.nodeToHead(pack.node);
            pack.value = value;
            return;
        }

        pack.node = queue_.pushHead(key);
        pack.value = value;
        
        if (queue_.size() > sizeLimit_) {
            int removeKey = queue_.popTail();
            cache_[removeKey].node = nullptr;
        }
    }

private:
    int sizeLimit_;
    LinkList queue_;
    
    struct Pack {
        Node* node = nullptr;
        int value;
    };
    
    vector<Pack> cache_;
};

std::list

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

class LRUCache {
public:
    LRUCache(int capacity) : sizeLimit_(capacity), cache_(1e4 + 2) {
    }

    int get(int key) {
        auto& pack = cache_[key];
        if (pack.null) {
            return -1;
        }

        // move node to front
        queue_.erase(pack.node);
        queue_.push_front(key);
        pack.node = queue_.begin();

        return pack.value;
    }

    void put(int key, int value) {
        auto& pack = cache_[key];
        if (!pack.null) {
            // move node to front
            queue_.erase(pack.node);
            queue_.push_front(key);
            pack.node = queue_.begin();

            pack.value = value;
            return;
        }

        queue_.push_front(key);
        pack.node = queue_.begin();
        pack.value = value;
        pack.null = false;

        if (queue_.size() > sizeLimit_) {
            int removeKey = queue_.back();
            queue_.pop_back();
            cache_[removeKey].null = true;
        }
    }

private:
    int sizeLimit_;
    list<int> queue_;

    struct Pack {
        bool null = true;
        list<int>::iterator node;
        int value;
    };

    vector<Pack> cache_;
};