Leetcode 编程题

146. LRU 缓存

146. LRU 缓存

一、题目

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。

实现 LRUCache 类：

• LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
• int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
• void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

图的表示

算法导论-第三版

图有多种表示方法，比较常用的表示法有邻接链表和邻接矩阵。

根据边的方向，图可以分为无向图和有向图；根据边的权重，图可以分为带权图和不带权图。

对于图$G=(V,E)$，其邻接链表表示由一个包含$|V|$条链表的数组$Adj$所构成，每个结点有一条链表。对于每个结点$u \in V$，邻接链表$Adj[u]$包含所有与结点$u$之间有边相连的结点$v$，即$Adj[u]$包含图$G$中所有与$u$邻接的结点（也可以说，该链表里包含指向这些结点的指针）。由于邻接链表代表的是图的边，在伪代码里，我们将数组$Adj$看做是图的一个属性，就如我们将边集合$E$看做是图的属性一样。因此，在伪代码里，我们将看到$G.Adj[u]$这样的表示。