Bộ nhớ đệm LRU - LCOJ: Luyện Code Online Judge

LRU - Bộ nhớ đệm LRU

Điểm: 1,00

Giới hạn thời gian: 2.0s

Giới hạn bộ nhớ: 256M

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Go, Java, JavaScript, Kotlin, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift

Đề bài

Thiết kế một cấu trúc dữ liệu LRU (Least Recently Used) Cache với các thao tác:

get(key): Trả về giá trị của key nếu tồn tại, ngược lại trả về -1. Sau khi truy cập, key được đánh dấu là mới nhất (most recently used).
put(key, value): Chèn hoặc cập nhật cặp (key, value). Nếu số lượng phần tử vượt quá capacity, cần xóa bỏ phần tử ít được sử dụng nhất (least recently used) trước khi chèn mới.

Input

Dòng đầu tiên chứa hai số nguyên capacity và n (~1 \leq capacity \leq 10^4~, ~1 \leq n \leq 10^5~).

Tiếp theo là n dòng, mỗi dòng là một thao tác:

get x — truy cập key x
put x y — chèn/cập nhật key x với giá trị y

Các giá trị key và value đều là số nguyên (~0 \leq x, y \leq 10^9~).

Output

Với mỗi thao tác get x, in ra giá trị tương ứng trên một dòng. Nếu không tìm thấy, in -1.

Ví dụ

Input 1

2 5
put 1 1
put 2 2
get 1
put 3 3
get 2

Output 1

1
-1

Giải thích:

put 1 1: Cache = {1:1}
put 2 2: Cache = {1:1, 2:2}
get 1: Trả về 1, Cache = {2:2, 1:1} (1 được đánh dấu mới nhất)
put 3 3: Cache đầy, xóa key 2 (ít dùng nhất), Cache = {1:1, 3:3}
get 2: Không tồn tại, trả về -1

Bình luận

Please read the guidelines before commenting.

-1

include <bits/stdc++.h>

using namespace std;

int main() { ios::syncwithstdio(false); cin.tie(NULL);

int capacity, n;
cin >> capacity >> n;

list&lt;pair&lt;long long, long long>> cache; 
unordered_map&lt;long long, list&lt;pair&lt;long long, long long>>::iterator> mp;

while (n--) {
    string op;
    cin >> op;

    if (op == "get") {
        long long key;
        cin >> key;

        if (mp.find(key) == mp.end()) {
            cout << -1 << "\n";
        } else {
            auto it = mp[key];
            long long value = it->second;
            cout << value << "\n";

            // đưa lên đầu (mới dùng nhất)
            cache.erase(it);
            cache.push_front({key, value});
            mp[key] = cache.begin();
        }
    }
    else { // put
        long long key, value;
        cin >> key >> value;

        if (mp.find(key) != mp.end()) {
            // cập nhật
            cache.erase(mp[key]);
        }
        else if ((int)cache.size() == capacity) {
            // xóa phần tử ít dùng nhất
            auto last = cache.back();
            mp.erase(last.first);
            cache.pop_back();
        }

        cache.push_front({key, value});
        mp[key] = cache.begin();
    }
}

return 0;

}