C++实现LeetCode(146.近最少使用页面置换缓存器)

[LeetCode] 146. LRU Cache 最近最少使用页面置换缓存器

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

Follow up:
Could you do both operations in O(1) time complexity?

Example:

LRUCache cache = new LRUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.put(4, 4);    // evicts key 1
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

这道题让我们实现一个 LRU 缓存器，LRU 是 Least Recently Used 的简写，就是最近最少使用的意思。那么这个缓存器主要有两个成员函数，get 和 put，其中 get 函数是通过输入 key 来获得 value，如果成功获得后，这对 (key, value) 升至缓存器中最常用的位置（顶部），如果 key 不存在，则返回 -1。而 put 函数是插入一对新的 (key, value)，如果原缓存器中有该 key，则需要先删除掉原有的，将新的插入到缓存器的顶部。如果不存在，则直接插入到顶部。若加入新的值后缓存器超过了容量，则需要删掉一个最不常用的值，也就是底部的值。具体实现时我们需要三个私有变量，cap, l和m，其中 cap 是缓存器的容量大小，l是保存缓存器内容的列表，m是 HashMap，保存关键值 key 和缓存器各项的迭代器之间映射，方便我们以 O(1) 的时间内找到目标项。

然后我们再来看 get 和 put 如何实现，get 相对简单些，我们在 HashMap 中查找给定的 key，若不存在直接返回 -1。如果存在则将此项移到顶部，这里我们使用 C++ STL 中的函数 splice，专门移动链表中的一个或若干个结点到某个特定的位置，这里我们就只移动 key 对应的迭代器到列表的开头，然后返回 value。这里再解释一下为啥 HashMap 不用更新，因为 HashMap 的建立的是关键值 key 和缓存列表中的迭代器之间的映射，get 函数是查询函数，如果关键值 key 不在 HashMap，那么不需要更新。如果在，我们需要更新的是该 key-value 键值对儿对在缓存列表中的位置，而 HashMap 中还是这个 key 跟键值对儿的迭代器之间的映射，并不需要更新什么。

对于 put，我们也是现在 HashMap 中查找给定的 key，如果存在就删掉原有项，并在顶部插入新来项，然后判断是否溢出，若溢出则删掉底部项(最不常用项)。代码如下：

class LRUCache{
public:
    LRUCache(int capacity) {
        cap = capacity;
    }

    int get(int key) {
        auto it = m.find(key);
        if (it == m.end()) return -1;
        l.splice(l.begin(), l, it->second);
        return it->second->second;
    }

    void put(int key, int value) {
        auto it = m.find(key);
        if (it != m.end()) l.erase(it->second);
        l.push_front(make_pair(key, value));
        m[key] = l.begin();
        if (m.size() > cap) {
            int k = l.rbegin()->first;
            l.pop_back();
            m.erase(k);
        }
    }

private:
    int cap;
    list<pair<int, int>> l;
    unordered_map<int, list<pair<int, int>>::iterator> m;
};

Github 同步地址：

https://github.com/grandyang/leetcode/issues/146

类似题目：

LFU Cache

Design In-Memory File System

Design Compressed String Iterator

参考资料：

https://leetcode.com/problems/lru-cache/

http://www.cnblogs.com/TenosDoIt/p/3417157.html

https://leetcode.com/problems/lru-cache/discuss/46285/unordered_map-list

到此这篇关于C++实现LeetCode(146.近最少使用页面置换缓存器)的文章就介绍到这了,更多相关C++实现近最少使用页面置换缓存器内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C++实现LeetCode(138.拷贝带有随机指针的链表)

    C++实现LeetCode(138.拷贝带有随机指针的链表)

    [LeetCode] 138. Copy List with Random Pointer 拷贝带有随机指针的链表 A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null. Return a deep copy of the list. Example 1: Input: {"$id"

  • C++验证LeetCode包围区域的DFS方法

    验证LeetCode Surrounded Regions 包围区域的DFS方法 在LeetCode中的Surrounded Regions 包围区域这道题中,我们发现用DFS方法中的最后一个条件必须是j > 1,如下面的红色字体所示,如果写成j > 0的话无法通过OJ,一直百思不得其解其中的原因,直到有网友告诉我说他验证了最后一个大集合在本地机子上可以通过,那么我也来验证看看吧. class Solution { public: void solve(vector<vector<

  • C++实现LeetCode(135.分糖果问题)

    [LeetCode] 135.Candy 分糖果问题 There are N children standing in a line. Each child is assigned a rating value. You are giving candies to these children subjected to the following requirements: Each child must have at least one candy. Children with a high

  • C++实现LeetCode(130.包围区域)

    [LeetCode] 130. Surrounded Regions 包围区域 Given a 2D board containing 'X' and 'O'(the letter O), capture all regions surrounded by 'X'. A region is captured by flipping all 'O's into 'X's in that surrounded region. Example: X X X X X O O X X X O X X O

  • C++实现LeetCode(134.加油站问题)

    [LeetCode] 134.Gas Station 加油站问题 There are N gas stations along a circular route, where the amount of gas at station i is gas[i]. You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1)

  • C++实现LeetCode(140.拆分词句之二)

    [LeetCode] 140.Word Break II 拆分词句之二 Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences. Not

  • C++实现LeetCode(133.克隆无向图)

    C++实现LeetCode(133.克隆无向图)

    [LeetCode] 133. Clone Graph 克隆无向图 Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node in the graph contains a val (int) and a list (List[Node]) of its neighbors. Example: Input: {"$id":

  • C++实现LeetCode(200.岛屿的数量)

    [LeetCode] 200. Number of Islands 岛屿的数量 Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four

  • C++实现LeetCode(146.近最少使用页面置换缓存器)

    [LeetCode] 146. LRU Cache 最近最少使用页面置换缓存器 Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put. get(key) - Get the value (will always be positive) of the key if the key exist

  • 让html页面不缓存js的实现方法

    本文实例讲述了让html页面不缓存js的实现方法.分享给大家供大家参考.具体实现方法如下: 很多朋友都会碰到这样的情况:如果我们页面加载了js的话下次打开时也会是调用这个js缓存文件,但对于我们调试时是非常的不方便了,本文就来谈论如何解决这一问题,下面一起来看看. 不缓存JS的方法其实挺简单,CSS在某种条件下也可以如此使用: 先让大家了解下不缓存的一个简单的原理: 当浏览不同Url时,浏览器会自动将当前访问的地址进行一次缓存:而第二次访问时着调用缓存下来的页面,从而达到页面快速加载(页面加载优

  • ASP.NET 2.0中的页面输出缓存

    静态页面全部内容保存在服务器内存中.当再有请求时,系统将缓存中的相关数据直接输出,直到缓存数据过期.这个过程中,缓存不需要再次经过页面处理生命周期.这样可以缩短请求响应时间,提高应用程序性能.很显然,页面输出缓存适用于不需要频繁更新数据,而占用大量时间和资源才能编译生成的页面.对于那些数据经常更新的页面,则不适用.默认情况下,ASP.NET 2.0启用了页面输出缓存功能,但并不缓存任何响应的输出.开发人员必须通过设置,使得某些页面的响应成为缓存的一部分. 设置页面输出缓存可以使用以下两种方式:一

  • Ajax获取页面被缓存的解决方法

    这样的情况是是为AJAX获取时先检查本机缓存,如果本机缓存已有相同内容,则不访问远端服务器.这样的操作倒是可以提高速度和减少服务器压力.但带来的弊端也是显而易见的. 为了解决这个问题.我们必须在获取页加上一个额外的参数.比较简单的方法是用一个随机数. 例子如下 复制代码 代码如下: function idCheck() { //参数调用函数 var f = document.modify_form; var book_num = f.book_num.value; if(book_num=="&

  • 页面的缓存与不缓存设置及html页面中meta的作用

    HTML的HTTP协议头信息中控制着页面在几个地方的缓存信息,包括浏览器端,中间缓存服务器端(如:squid等),Web服务器端.本文讨论头信息 中带缓存控制信息的HTML页面(JSP/Servlet生成好出来的也是HTML页面)在中间缓存服务器中的缓存情况. HTTP协议中关于缓存的信息头关键字包括Cache-Control(HTTP1.1),Pragma(HTTP1.0),last-Modified,Expires等. HTTP1.0中通过Pragma 控制页面缓存,可以设置:Pragma或

  • 防止页面url缓存中ajax中post请求的处理方法

    防止页面url缓存中ajax中post请求的处理方法 一般我们在开发中经常会用到Ajax请求,异步发送请求,然后获取我们想要的数据,在Ajax中使用Get请求数据不会有页面缓存的问题,而使用POST请求可是有时候页面会缓存我们提交的信息,导致我们发送的异步请求不能正确的返回我们想要的数据,那么遇到这种情况,我们应该怎么办呢??? 下面介绍一种方式来防止ajax中post 请求 页面缓存 url 信息: $.post(url,data ,ranNum:Math.random()} ,functio

  • asp.net 页面输出缓存

    主要用于不经常更新和修改,而在第一次编译是时要经过大量处理的数据.页面输出缓存是缓存的整个页面 使用很简单<%@ OutPutCache Duration="60" VaryByParam="none"%> Duration:缓存时间 VaryByParam:通过参数来更新缓存的内容 还有其他的一些属性 CacheProfile:调用WebConfig中的缓存时间 例如:WebCofig中 复制代码 代码如下: <system.web> &l

  • 浅谈Vue页面级缓存解决方案feb-alive(上)

    feb-alive github地址 体验链接 使用理由 开发者无需因为动态路由或者普通路由的差异而将数据初始化逻辑写在不同的钩子里beforeRouteUpdate或者activated 开发者无需手动缓存页面状态,例如通过localStorage或者sessionStorage缓存当前页面的数据 feb-alive会帮你处理路由meta信息的存储与恢复 为什么开发feb-laive? 当我们通过Vue开发项目时候,是否会有以下场景需求? /a跳转到/b 后退到/a时候,希望从缓存中恢复页面

  • 浅谈Vue页面级缓存解决方案feb-alive (下)

    浅谈Vue页面级缓存解决方案feb-alive (下)

    feb-alive github地址 体验链接 Vue页面级缓存解决方案feb-alive (上) 在剖析feb-alive实现之前,希望大家对以下基本知识有一定的了解. keep-alive实现原理 history api vue渲染原理 vue虚拟dom原理 feb-alive与keep-alive差异性 1. 针对activated钩子差异性 keep-alive配合vue-router在动态路由切换的情况下不会触发activated钩子,因为切换的时候组件没有变化,所以只能通过befor

  • 关于vue里页面的缓存详解

    keep-alive是vue内置的一个组件,可以使被它包含的组件处于保留状态,或避免被重新渲染. 用法: 运行结果描述: input输入框内,路由切换输入框内部的内容不会发生改变. 在keep-alive标签内部添加 include:字符串或正则表达式.只有匹配的组件会被缓存 exclude: 字符串或正则表达式.任何匹配的组件都不会被缓存. 结合router缓存部分页面: 比较实用的例子: 思路:通过beforeRouterLeave这个钩子来对路由里面的keepAlive进行赋值.从而动态的

随机推荐