【題目描述】
LFU (Least Frequently Used) is a famous cache eviction algorithm.For a cache with capacity k, if the cache is full and need to evict a key in it, the key with the lease frequently used will be kicked out.Implement set and get method for LFU cache.
LFU是一個(gè)著名的緩存算法。實(shí)現(xiàn)LFU中的set 和 get
【題目鏈接】
http://www.lintcode.com/en/problem/lfu-cache/
【題目解析】
這道題讓我們實(shí)現(xiàn)一個(gè)LRU緩存器，LRU是Least Recently Used的簡(jiǎn)寫(xiě)，就是最近最少使用的意思。那么這個(gè)緩存器主要有兩個(gè)成員函數(shù)，get和set，其中g(shù)et函數(shù)是通過(guò)輸入key來(lái)獲得value，如果成功獲得后，這對(duì)(key, value)升至緩存器中最常用的位置（頂部），如果key不存在，則返回-1。而set函數(shù)是插入一對(duì)新的(key, value)，如果原緩存器中有該key，則需要先刪除掉原有的，將新的插入到緩存器的頂部。如果不存在，則直接插入到頂部。若加入新的值后緩存器超過(guò)了容量，則需要?jiǎng)h掉一個(gè)最不常用的值，也就是底部的值。具體實(shí)現(xiàn)時(shí)我們需要三個(gè)私有變量，cap, l和m，其中cap是緩存器的容量大小，l是保存緩存器內(nèi)容的列表，m是哈希表，保存關(guān)鍵值key和緩存器各項(xiàng)的迭代器之間映射，方便我們以O(shè)(1)的時(shí)間內(nèi)找到目標(biāo)項(xiàng)。
【參考答案】
