题目

解答

class LRUCache {
public:
    using PII = std::pair<int, int>;

    LRUCache(int capacity) {
        m_maps.reserve(capacity);
        m_capacity = capacity;
    }
    
    int get(int key) {
        auto iter = m_maps.find(key);
        if(iter == m_maps.end()) return -1;
        m_lists.splice(m_lists.begin(), m_lists, iter->second);
        return iter->second->second;
    }
    
    void put(int key, int value) {
        auto iter = m_maps.find(key);
        if(iter == m_maps.end()) {
            m_lists.push_front({key, value});
        } else {
            iter->second->second = value;
            m_lists.splice(m_lists.begin(), m_lists, iter->second);
        }

        m_maps[key] = m_lists.begin();

        if(m_lists.size() > m_capacity) {
            m_maps.erase(m_lists.back().first);
            m_lists.pop_back();
        }
    }

private:
    std::unordered_map<int, std::list<PII>::iterator> m_maps;
    std::list<PII> m_lists;
    int m_capacity;
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

复杂度

时间复杂度：O(1)

空间复杂度：O(1)

补充

splice

void splice( const_iterator pos, list& other );
void splice( const_iterator pos, list&& other );
void splice( const_iterator pos, list& other, const_iterator it );
void splice( const_iterator pos, list&& other, const_iterator it );
void splice( const_iterator pos, list& other,
             const_iterator first, const_iterator last);
void splice( const_iterator pos, list&& other,
             const_iterator first, const_iterator last );

从一个 list 向另一个 list 传递元素。

1, 2) 传递所有元素从 other 到 *this。元素被插入到 pos 位置之前。other 变成空。

3, 4) 将 it 指向的元素从 other 传递到 *this。元素被插入到 pos 位置之前。

5, 6) 传递 other 的 [first, last) 到 *this。元素被插入到 pos 位置之前。

复杂度：

1-4) 常数

5,6) 如果 other 与 *this 指向相同的 object，否则是线性的 std::distance(first, last)。

#include <iostream>
#include <list>

std::ostream& operator<<(std::ostream& ostr, const std::list<int>& list)
{
    for(auto& i : list)
        ostr << ' ' << i;
    return ostr;
}

int main()
{
    std::list<int> list1{1, 2, 3, 4, 5};
    std::list<int> list2{10, 20, 30, 40, 50};
    
    auto it = list1.begin();
    std::advance(it, 2);
    
    list1.splice(it, list2);
    
    std::cout << "list1:" << list1 << '\n';
    std::cout << "list2:" << list2 << '\n';
    
    list2.splice(list2.begin(), list1, it, list1.end());
    
    std::cout << "list1:" << list1 << '\n';
    std::cout << "list2:" << list2 << '\n';
}

list1: 1 2 10 20 30 40 50 3 4 5
list2:
list1: 1 2 10 20 30 40 50
list2: 3 4 5