首页 > 试题广场 >

LRU链表

[编程题]LRU链表

热度指数：109 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

实现一个LRU链表（元素类型为整形），链表大小为N，当往链表中插入元素时（元素可能重复，如果是插入重复元素，那么不新增元素，只调整元素在链表中的位置），如果链表满了，那么淘汰最近没有被访问（这里只考虑插入这一个访问操作，不考虑查找）的元素，然后插入新元素。当插入M个元素后（M > N），打印链表中的所有元素。

输入描述:

第一行为链表大小N。
第二行为整数集合（可能有重复的元素），整数之间用空格分隔。这个集合的顺序，表示不断访问（插入）的顺序，即：将该集合中的元素逐个插入LRU链表中。

输出描述:

插入所有元素后，将链表中的元素打印出来。所有元素打印到一行，元素（整数）之间用空格分隔。

示例1

输入

3
1 2 4 2 6 9 6

输出

6 9 2

算法知识视频讲解

牛客898207889号

#include <iostream>
#include <map>
#include <list>
#include <algorithm>
using namespace std;

class Lru {
    public:
    Lru(int s) : capacity(s) {};
    void print();
    void put(int k);
    private:
    map<int, list<int>::iterator> lru_map;
    list<int> lru_list;

    int capacity;
    
};

void Lru::put(int k) {
    if (lru_map.find(k) == lru_map.end()) {
        //超出容量删除
        if (lru_list.size() == capacity) {
            lru_map.erase(lru_list.back());
            lru_list.pop_back();
        }
        //置入链表头
        lru_list.push_front(k);
        lru_map[k] = lru_list.begin();
    } else {
        //移动到链表头部
        lru_list.splice(lru_list.begin(),lru_list, lru_map[k]);
        lru_map[k] = lru_list.begin();
    }
}


void Lru::print() {
    for (auto it = lru_list.begin(); it != lru_list.end(); it++) {
        cout << *it << " ";
    }
}

int main() {
    int s;
    cin >> s;
    auto lru_item = Lru(s);
    while(cin >> s) {
        lru_item.put(s);
    }
    lru_item.print();
    return 0;

}

发表于 2022-07-16 00:58:09 回复(0)

Python

臆想者

n = int(input())
nums = list(map(int, input().split()))
lru = []
for i in nums:
    if len(lru)<n:
        if i in lru:
            lru.insert(0, lru.pop(lru.index(i)))
        else:
            lru.insert(0, i)
    else:
        if i in lru:
            lru.insert(0, lru.pop(lru.index(i)))
        else:
            lru.pop()
            lru.insert(0, i)
print(" ".join(map(str, lru)))

发表于 2022-08-25 10:59:15 回复(0)

OFFER/OFFER

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int size;
    int num;
    cin >> size;
    list<int> lru;
    vector<int> r;
    unordered_set<int> hash;
    while(cin >> num)
    {
        if(hash.find(num) == hash.end())
        {
            hash.insert(num);
            if(lru.size() >= size)
            {
                hash.erase(lru.front());
                lru.pop_front();
            }
            lru.push_back(num);
        }else
        {
            lru.remove(num);
            lru.push_back(num);
        }
    }
    for(auto it = lru.rbegin();it != lru.rend();it++)
        cout << *it << " ";
    return 0;
}

发表于 2022-03-16 20:24:16 回复(0)