Algorithm/Algorithm/Solution146.cpp at master · Pancf/Algorithm

40 lines (36 loc) · 972 Bytes

//
//  Solution146.cpp
//  Algorithm
//
//  Created by Pancf on 2020/12/8.
//  Copyright © 2020 Pancf. All rights reserved.
//

#include "Solution146.hpp"

LRUCache::LRUCache(int capacity): capacity(capacity)
{
}

int LRUCache::get(int key)
{
    auto it = keyToIndex.find(key);
    if (it != keyToIndex.end()) { // find it
        keyValues.splice(keyValues.begin(), keyValues, it->second);
        return it->second->second;
    }
    return -1;
}

void LRUCache::put(int key, int value)
{
    auto it = keyToIndex.find(key);
    if (it != keyToIndex.end()) {
        it->second->second = value;
        keyValues.splice(keyValues.begin(), keyValues, it->second);
    } else {
        if (keyToIndex.size() >= capacity) {
            int keyToRemove = keyValues.back().first;
            keyToIndex.erase(keyToRemove);
            keyValues.pop_back();
        }
        keyValues.emplace_front(key, value);
        keyToIndex.insert({key, keyValues.begin()});
    }
}

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Expand file tree

Search code, repositories, users, issues, pull requests...

FilesExpand file tree

Solution146.cpp

Latest commit

History

Solution146.cpp

File metadata and controls

Expand file tree