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

資訊專欄INFORMATION COLUMN

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

you_De / 1415人閱讀

摘要:劍指緩存實(shí)現(xiàn)聲明文章均為本人技術(shù)筆記,轉(zhuǎn)載請(qǐng)注明出處解題思路緩存兩種功能獲取的對(duì)應(yīng),不存在返回版本版本設(shè)置緩存已滿,刪除最近最久未被使用的節(jié)點(diǎn),添加新節(jié)點(diǎn)進(jì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://segmentfault.com/u/yzwall
[2] blog.csdn.net/j_dark/

解題思路 LRU緩存兩種功能:

get(key):獲取key的對(duì)應(yīng)value,不存在返回-1

set(key, value)(lintcode版本)/put(key, value)(leetcode版本):設(shè)置

緩存已滿,刪除最近最久未被使用的節(jié)點(diǎn),添加新節(jié)點(diǎn)進(jìn)緩存

緩存未滿,

節(jié)點(diǎn)存在,修改value;

節(jié)點(diǎn)不存在,添加新節(jié)點(diǎn)進(jìn)緩存;

解題思路

由于LRU緩存插入和刪除操作頻繁,使用雙向鏈表維護(hù)緩存節(jié)點(diǎn),

“新節(jié)點(diǎn)”:凡是被訪問(wèn)(新建/修改命中/訪問(wèn)命中)過(guò)的節(jié)點(diǎn),一律在訪問(wèn)完成后移動(dòng)到雙向鏈表尾部,保證鏈表尾部始終為最“新”節(jié)點(diǎn)

“舊節(jié)點(diǎn)”保證鏈表頭部始終為最“舊”節(jié)點(diǎn),LRU策略刪除時(shí)表現(xiàn)為刪除雙向鏈表頭部;

從鏈表頭部到尾部,節(jié)點(diǎn)訪問(wèn)熱度逐漸遞增

由于鏈表不支持隨機(jī)訪問(wèn),使用HashMap+雙向鏈表實(shí)現(xiàn)LRU緩存;

HashMap中鍵值對(duì):

雙向鏈表:維護(hù)緩存節(jié)點(diǎn)CacheNode

注意點(diǎn)

使用雙向鏈表時(shí),時(shí)刻記得維護(hù)prenext指針;

題目鏈接

lintcode 134: http://www.lintcode.com/zh-cn/problem/lru-cache/

leetcode 146: https://leetcode.com/problems/lru-cache/#/description

Java代碼
/**
 * HashMap+雙向鏈表實(shí)現(xiàn)LRU緩存
 * http://www.lintcode.com/zh-cn/problem/lru-cache/
 * https://leetcode.com/problems/lru-cache/#/description
 * @author yzwall
 */
import java.util.HashMap;

class Solution {
    private HashMap map;
    private int capacity;
    // head.next和tail.next指向鏈表頭尾,包起來(lái)防止null
    private CacheNode head = new CacheNode(-1, -1);
    private CacheNode tail = new CacheNode(-1, -1);
    
    // 緩存節(jié)點(diǎn)
    private class CacheNode {
        int key, value;
        CacheNode pre, next;
        CacheNode(int key, int value) {
            this.key = key;
            this.value = value;
            this.pre = null;
            this.next = null;
        }
    }
    
    public Solution(int capacity) {
        this.map = new HashMap<>();
        this.capacity = capacity;
    }
    
    // 將已有節(jié)點(diǎn)或新建節(jié)點(diǎn)移動(dòng)到鏈表尾部
    private void moveToTail(CacheNode target, boolean isNew) {
        // 尾部節(jié)點(diǎn)顯然不需要移動(dòng)
        if (target != tail.next) {
            if (!isNew) {
                // 修改舊節(jié)點(diǎn)的雙向鏈表指針
                target.pre.next = target.next; 
                target.next.pre = target.pre;
            }
            // 添加節(jié)點(diǎn)到鏈表尾部
            tail.next.next = target;
            target.pre = tail.next;
            tail.next = target;
        }
    }
    
    // 命中節(jié)點(diǎn)添加到鏈表尾部,未命中返回-1
    public int get(int key) {
        if (map.containsKey(key)) {
            CacheNode target = map.get(key);
            // 將已有節(jié)點(diǎn)移動(dòng)到鏈表尾部
            moveToTail(target, false);
            // 此時(shí)鏈表尾部tail.next = target,更新next指向null,防止出現(xiàn)環(huán)
            tail.next.next = null;
            return target.value;
        }
        return -1;
    }
    
    /**
     * 1. 節(jié)點(diǎn)命中,修改節(jié)點(diǎn)并移動(dòng)到鏈表尾部tail.next
     * 2. 節(jié)點(diǎn)未命中,
     *    2.1 cache已滿,刪除鏈表頭部head.next
     *    2.2 cache未滿,新建節(jié)點(diǎn)并添加到鏈表尾部tail.next
     */
    public void set(int key, int value) {
        // cache中存在節(jié)點(diǎn)
        if (map.containsKey(key)) {
            CacheNode target = map.get(key);
            target.value = value;
            map.put(key, target);
            // 將訪問(wèn)過(guò)的已有節(jié)點(diǎn)移動(dòng)到鏈表尾部
            moveToTail(target, false);
        } else if(map.size() < capacity) {    // cache未滿,添加節(jié)點(diǎn)
            CacheNode newNode = new CacheNode(key, value);
            map.put(key, newNode);
            if (head.next == null) {
                head.next = newNode;
                newNode.pre = head;
                tail.next = newNode;
            } else {
                // 將新建節(jié)點(diǎn)移動(dòng)到鏈表尾部
                moveToTail(newNode, true);
            }
        } else {    // cache已滿,淘汰鏈表鏈表頭部節(jié)點(diǎn),新節(jié)點(diǎn)加入到鏈表尾部
            CacheNode newNode = new CacheNode(key, value);
            map.remove(head.next.key);
            map.put(key, newNode);
            // cache中只有一個(gè)元素
            if (head.next == tail.next) {
                head.next = newNode;
                tail.next = newNode;
            } else {    // cache中不止一個(gè)元素,刪除頭部
                head.next.next.pre = head; // 更新新頭部.pre = head
                head.next = head.next.next;// 更新新頭部
                // 將新建節(jié)點(diǎn)移動(dòng)到鏈表尾部
                moveToTail(newNode, true);
            }
        }
    }
}

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

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

相關(guān)文章

  • 從簡(jiǎn)歷被拒到收割今日頭條 offer,我用一年時(shí)間破繭成蝶!

    摘要:正如我標(biāo)題所說(shuō),簡(jiǎn)歷被拒??戳宋液?jiǎn)歷之后說(shuō)頭條競(jìng)爭(zhēng)激烈,我背景不夠,點(diǎn)到為止。。三準(zhǔn)備面試其實(shí)從三月份投遞簡(jiǎn)歷開(kāi)始準(zhǔn)備面試到四月份收,也不過(guò)個(gè)月的時(shí)間,但這都是建立在我過(guò)去一年的積累啊。 本文是 無(wú)精瘋 同學(xué)投稿的面試經(jīng)歷 關(guān)注微信公眾號(hào):進(jìn)擊的java程序員K,即可獲取最新BAT面試資料一份 在此感謝 無(wú)精瘋 同學(xué)的分享 目錄: 印象中的頭條 面試背景 準(zhǔn)備面試 ...

    tracymac7 評(píng)論0 收藏0
  • 從簡(jiǎn)歷被拒到收割今日頭條 offer,我用一年時(shí)間破繭成蝶!

    摘要:正如我標(biāo)題所說(shuō),簡(jiǎn)歷被拒??戳宋液?jiǎn)歷之后說(shuō)頭條競(jìng)爭(zhēng)激烈,我背景不夠,點(diǎn)到為止。。三準(zhǔn)備面試其實(shí)從三月份投遞簡(jiǎn)歷開(kāi)始準(zhǔn)備面試到四月份收,也不過(guò)個(gè)月的時(shí)間,但這都是建立在我過(guò)去一年的積累啊。 本文是 無(wú)精瘋 同學(xué)投稿的面試經(jīng)歷 關(guān)注微信公眾號(hào):進(jìn)擊的java程序員K,即可獲取最新BAT面試資料一份 在此感謝 無(wú)精瘋 同學(xué)的分享目錄:印象中的頭條面試背景準(zhǔn)備面試頭條一面(Java+項(xiàng)目)頭條...

    wdzgege 評(píng)論0 收藏0
  • 一個(gè)線程安全的 lrucache 實(shí)現(xiàn) --- 讀 leveldb 源碼

    摘要:在閱讀的源代碼的時(shí)候,發(fā)現(xiàn)其中的類正是一個(gè)線程安全的實(shí)現(xiàn),代碼非常優(yōu)雅。至此一個(gè)線程安全的類就已經(jīng)全部實(shí)現(xiàn),在中使用的緩存是,其實(shí)就是聚合多個(gè)實(shí)例,真正的邏輯都在類中。 緩存是計(jì)算機(jī)的每一個(gè)層次中都是一個(gè)非常重要的概念,緩存的存在可以大大提高軟件的運(yùn)行速度。Least Recently Used(lru) cache 即最近最久未使用的緩存,多見(jiàn)與頁(yè)面置換算法,lru 緩存算法在緩存的...

    widuu 評(píng)論0 收藏0
  • web技術(shù)分享| LRU 緩存淘汰算法

    摘要:雙向鏈表用于管理緩存數(shù)據(jù)結(jié)點(diǎn)的順序,新增數(shù)據(jù)和緩存命中最近被訪問(wèn)的數(shù)據(jù)被放置在結(jié)點(diǎn),尾部的結(jié)點(diǎn)根據(jù)內(nèi)存大小進(jìn)行淘汰。 了解 LRU 之前,我們應(yīng)該了解一下緩存,大家都知道計(jì)算機(jī)具有緩存內(nèi)存,可以臨時(shí)存儲(chǔ)最常用的數(shù)據(jù),當(dāng)緩存數(shù)據(jù)超過(guò)一定大小時(shí),系統(tǒng)會(huì)進(jìn)行回收,以便釋放出空間來(lái)緩存新的數(shù)據(jù),但從系統(tǒng)中檢索數(shù)據(jù)的成本...

    graf 評(píng)論0 收藏0
  • Vue的緩存算法—LRU算法

    摘要:最近在看的源碼,不得不說(shuō)的是,的源碼十分優(yōu)雅簡(jiǎn)潔,下面就來(lái)分享下的緩存利用的算法算法。關(guān)于算法的具體流程,可以來(lái)看下這個(gè),這個(gè)可視化過(guò)程,模擬了算法進(jìn)行調(diào)度的過(guò)程。 最近在看Vue的源碼,不得不說(shuō)的是,Vue的源碼十分優(yōu)雅簡(jiǎn)潔,下面就來(lái)分享下Vue的緩存利用的算法LRU算法。 LRU算法 LRU是Least recently used的簡(jiǎn)寫,主要原理是根據(jù)歷史訪問(wèn)記錄來(lái)淘汰數(shù)據(jù),說(shuō)白了...

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

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

0條評(píng)論

閱讀需要支付1元查看
<