成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專(zhuān)欄INFORMATION COLUMN

[Leetcode] LRU Cache 最近使用緩存

Render / 3259人閱讀

摘要：但是哈希表無(wú)序的，我們沒(méi)辦法在緩存滿(mǎn)時(shí)，將最早更新的元素給刪去。所以雙向鏈表是最好的選擇。我們用雙向鏈表實(shí)現(xiàn)一個(gè)隊(duì)列用來(lái)記錄每個(gè)元素的順序，用一個(gè)哈希表來(lái)記錄鍵和值的關(guān)系，就行了。

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


get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. 
set(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.
雙向鏈表加哈希表 復(fù)雜度

時(shí)間 Get O(1) Set O(1) 空間 O(N)

思路

緩存講究的就是快，所以我們必須做到O(1)的獲取速度，這樣看來(lái)只有哈希表可以勝任。但是哈希表無(wú)序的，我們沒(méi)辦法在緩存滿(mǎn)時(shí)，將最早更新的元素給刪去。那么是否有一種數(shù)據(jù)結(jié)構(gòu)，可以將先進(jìn)的元素先出呢？那就是隊(duì)列。所以我們將元素存在隊(duì)列中，并用一個(gè)哈希表記錄下鍵值和元素的映射，就可以做到O(1)獲取速度，和先進(jìn)先出的效果。然而，當(dāng)我們獲取一個(gè)元素時(shí)，還需要把這個(gè)元素再次放到隊(duì)列頭，這個(gè)元素可能在隊(duì)列的任意位置，可是隊(duì)列并不支持對(duì)任意位置的增刪操作。而最適合對(duì)任意位置增刪操作的數(shù)據(jù)結(jié)構(gòu)又是什么呢？是鏈表。我可以用鏈表來(lái)實(shí)現(xiàn)一個(gè)隊(duì)列，這樣就同時(shí)擁有鏈表和隊(duì)列的特性了。不過(guò)，如果僅用單鏈表的話，在任意位置刪除一個(gè)節(jié)點(diǎn)還是很麻煩的，要么記錄下該節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)，要么遍歷一遍。所以雙向鏈表是最好的選擇。我們用雙向鏈表實(shí)現(xiàn)一個(gè)隊(duì)列用來(lái)記錄每個(gè)元素的順序，用一個(gè)哈希表來(lái)記錄鍵和值的關(guān)系，就行了。

注意

這題更多的是考察用數(shù)據(jù)結(jié)構(gòu)進(jìn)行設(shè)計(jì)的能力，再寫(xiě)代碼時(shí)盡量將子函數(shù)拆分出來(lái)，先寫(xiě)個(gè)整體的框架。

移出鏈表最后一個(gè)節(jié)點(diǎn)時(shí)，要記得在鏈表和哈希表中都移出該元素，所以節(jié)點(diǎn)中也要記錄Key的信息，方便在哈希表中移除

代碼 
public class LRUCache {
    
    int size;
    int capacity;
    ListNode tail;
    ListNode head;
    Map map;
    
    public LRUCache(int capacity) {
        this.head = new ListNode(-1,-1);
        this.tail = new ListNode(-1,-1);
        head.next = tail;
        tail.prev = head;
        this.size = 0;
        this.capacity = capacity;
        this.map = new HashMap();
    }
    
    public int get(int key) {
        ListNode n = map.get(key);
        if(n != null){
            moveToHead(n);
            return n.val;
        } else {
            return -1;
        }
    }
    
    public void set(int key, int value) {
        ListNode n = map.get(key);
        if(n == null){
            n = new ListNode(value, key);
            attachToHead(n);
            size++;
        } else {
            n.val = value;
            moveToHead(n);
        }
        // 如果更新節(jié)點(diǎn)后超出容量，刪除最后一個(gè)
        if(size > capacity){
            removeLast();
            size--;
        }
        map.put(key, n);
    }
    
    // 將一個(gè)孤立節(jié)點(diǎn)放到頭部
    private void attachToHead(ListNode n){
        n.next = head.next;
        n.next.prev = n;
        head.next = n;
        n.prev = head;
    }
    
    // 將一個(gè)鏈表中的節(jié)點(diǎn)放到頭部
    private void moveToHead(ListNode n){
        n.prev.next = n.next;
        n.next.prev = n.prev;
        attachToHead(n);
    }
    
    // 移出鏈表最后一個(gè)節(jié)點(diǎn)
    private void removeLast(){
        ListNode last = tail.prev;
        last.prev.next = tail;
        tail.prev = last.prev;
        map.remove(last.key);
    }
    
    public class ListNode {
        ListNode prev;
        ListNode next;
        int val;
        int key;
        public ListNode(int v, int k){
            this.val = v;
            this.prev = null;
            this.next = null;
            this.key = k;
        }
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/64530.html

相關(guān)文章

  • 劍指offer/LeetCode146/LintCode134_LRU緩存實(shí)現(xiàn)

    摘要：劍指緩存實(shí)現(xiàn)聲明文章均為本人技術(shù)筆記，轉(zhuǎn)載請(qǐng)注明出處解題思路緩存兩種功能獲取的對(duì)應(yīng)，不存在返回版本版本設(shè)置緩存已滿(mǎn)，刪除最近最久未被使用的節(jié)點(diǎn)，添加新節(jié)點(diǎn)進(jìn)緩存緩存未滿(mǎn)，節(jié)點(diǎn)存在，修改節(jié)點(diǎn)不存在，添加新節(jié)點(diǎn)進(jìn)緩存解題思路由于緩存插入和刪除 劍指offer/LeetCode146/LintCode134_LRU緩存實(shí)現(xiàn) 聲明 文章均為本人技術(shù)筆記，轉(zhuǎn)載請(qǐng)注明出處[1] https://s...

    you_De 評(píng)論0 收藏0

  • 力扣(LeetCode)146

    摘要：當(dāng)緩存容量達(dá)到上限時(shí)，它應(yīng)該在寫(xiě)入新數(shù)據(jù)之前刪除最近最少使用的數(shù)據(jù)值，從而為新的數(shù)據(jù)值留出空間。但是無(wú)法保證是，也無(wú)法保證更新數(shù)據(jù)時(shí)是，因?yàn)檫@兩個(gè)操作必然要遍歷隊(duì)列。因?yàn)榭梢酝ㄟ^(guò)來(lái)判斷是否有這個(gè)節(jié)點(diǎn)。 題目地址：https://leetcode-cn.com/probl...題目描述：運(yùn)用你所掌握的數(shù)據(jù)結(jié)構(gòu)，設(shè)計(jì)和實(shí)現(xiàn)一個(gè) LRU (最近最少使用) 緩存機(jī)制。它應(yīng)該支持以下操作： 獲...

    zr_hebo 評(píng)論0 收藏0

  • 筆記｜緩存

    摘要：緩存算法我是，我會(huì)統(tǒng)計(jì)每一個(gè)緩存數(shù)據(jù)的使用頻率，我會(huì)把使用最少的緩存替換出緩存區(qū)。瀏覽器就是使用了我作為緩存算法。在緩存系統(tǒng)中找出最少最近的對(duì)象是需要較高的時(shí)空成本。再來(lái)一次機(jī)會(huì)的緩存算法，是對(duì)的優(yōu)化。直到新的緩存對(duì)象被放入。 緩存 什么是緩存？ showImg(https://segmentfault.com/img/bVusZg); 存貯數(shù)據(jù)（使用頻繁的數(shù)據(jù)）的臨時(shí)地方，因?yàn)槿≡?..

    elliott_hu 評(píng)論0 收藏0

  • NPM酷庫(kù)：lru-cache 基于內(nèi)存的緩存管理

    摘要：酷庫(kù)，每天兩分鐘，了解一個(gè)流行庫(kù)。而直接將數(shù)據(jù)保存在程序變量中，最經(jīng)濟(jì)快捷。但是這樣就會(huì)帶來(lái)一些其他問(wèn)題，比如緩存更新緩存過(guò)期等。用于在內(nèi)存中管理緩存數(shù)據(jù)，并且支持算法?？梢宰尦绦虿灰蕾?lài)任何外部數(shù)據(jù)庫(kù)實(shí)現(xiàn)緩存管理。 NPM酷庫(kù)，每天兩分鐘，了解一個(gè)流行NPM庫(kù)。 為了優(yōu)化程序性能，我們常常需要獎(jiǎng)數(shù)據(jù)緩存起來(lái)，根據(jù)實(shí)際情況，我們可以將數(shù)據(jù)存儲(chǔ)到磁盤(pán)、數(shù)據(jù)庫(kù)、redis等。 但是有時(shí)候要緩...

    Yumenokanata 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<