首页 > 试题广场 >

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

算法知识视频讲解

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)