重庆网站建设哪个好,乐陵建设网站,网站整站源码下载工具,曼联vs恩波利比分文章目录 一、题目二、C# 题解 一、题目 设计和构建一个“最近最少使用”缓存#xff0c;该缓存会删除最近最少使用的项目。缓存应该从键映射到值(允许你插入和检索特定键对应的值)#xff0c;并在初始化时指定最大容量。当缓存被填满时#xff0c;它应该删除最近最少使用的… 文章目录 一、题目二、C# 题解 一、题目 设计和构建一个“最近最少使用”缓存该缓存会删除最近最少使用的项目。缓存应该从键映射到值(允许你插入和检索特定键对应的值)并在初始化时指定最大容量。当缓存被填满时它应该删除最近最少使用的项目。 它应该支持以下操作 获取数据 get 和 写入数据 put。 获取数据 get(key) - 如果密钥 (key) 存在于缓存中则获取密钥的值总是正数否则返回 -1。 写入数据 put(key, value) - 如果密钥不存在则写入其数据值。当缓存容量达到上限时它应该在写入新数据之前删除最近最少使用的数据值从而为新的数据值留出空间。
示例: LRUCache cache new LRUCache( 2 /* 缓存容量 */ ); cache.put(1, 1); cache.put(2, 2); cache.get(1); // 返回 1 cache.put(3, 3); // 该操作会使得密钥 2 作废 cache.get(2); // 返回 -1 (未找到) cache.put(4, 4); // 该操作会使得密钥 1 作废 cache.get(1); // 返回 -1 (未找到) cache.get(3); // 返回 3 cache.get(4); // 返回 4 点击此处跳转题目。
二、C# 题解 LRU 的思想就是将不常使用的元素优先级设置最低。因此算法规则如下
新数据插入到链表头部当缓存命中即缓存数据被访问数据要移到表头当链表满的时候将链表尾部的数据丢弃。 这里使用数组存储链表结构因为简单高效。
public class LRUCache {private struct Node{public int Key, Value, Left, Right;}private int _cap, _size;private Node[] _list; // 带头结点的双向链表数组实现_list[0] 作为头结点private int FirstPos { // 第一个结点的物理位置存储在 _list[0].Right 中get _list[0].Right;set _list[0].Right value;}private int RearPos { // 尾结点的物理位置存储在 _list[0].Left 中get _list[0].Left;set _list[0].Left value;}private Dictionaryint, int _dic;public LRUCache(int capacity) {_cap capacity;_size 0;_list new Node[_cap 1]; // _list[0] 用作 head 结点存储 first 和 rear 位置_dic new Dictionaryint, int(); // 记录 key 所在结点的位置 pos}public int Get(int key) {// Cache 中存在 key则将其移到表头并返回对应的 valueif (_dic.TryGetValue(key, out int pos)) {MoveToFirst(pos);return _list[pos].Value;}// 不存在返回 -1return -1;}public void Put(int key, int value) {// Cache 中存在 key则将其移到表头并更新 valueif (_dic.TryGetValue(key, out int pos)) {MoveToFirst(pos);_list[pos].Value value;}// 不存在 keyelse {// 链表未满则直接插入新结点if (_size _cap) {AddNode(key, value, _size); // 新结点的物理位置在数组的下一个位置_dic.Add(key, _size); // 添加 key 的记录}// 链表已满需要移除尾结点将新结点插入表头else {int rear RearPos; // 记录此时的尾结点位置ReMoveAt(rear); // 移除尾结点_dic.Remove(_list[rear].Key);AddNode(key, value, rear); // 向表头插入新结点物理位置就存储在刚删掉的尾结点 rear 处_dic.Add(key, rear);}}}// 向表头插入结点结点存储在 _list[pos] 的位置中private void AddNode(int key, int value, int pos) {// 创建结点_list[pos].Key key;_list[pos].Value value;// 插入表头_list[pos].Left 0;_list[pos].Right FirstPos;_list[FirstPos].Left pos;FirstPos pos;}// 将 pos 位置处的结点移到表头private void MoveToFirst(int pos) {ReMoveAt(pos); // 将该结点从链表中移出AddNode(_list[pos].Key, _list[pos].Value, pos); // 再插入表头}// 将 _list[pos] 处的结点从链表中移除private void ReMoveAt(int pos) {int leftPos _list[pos].Left;int rightPos _list[pos].Right;_list[leftPos].Right rightPos;_list[rightPos].Left leftPos;}
}/*** Your LRUCache object will be instantiated and called as such:* LRUCache obj new LRUCache(capacity);* int param_1 obj.Get(key);* obj.Put(key,value);*/时间176 ms击败 100.00% 使用 C# 的用户内存64.35 MB击败 85.71% 使用 C# 的用户
