LEetCode 460. LFU 캐 시 (해시 더 블 링크)

1. 제목
(LFU) 캐 시 를 가장 자주 사용 하지 않 는 데이터 구 조 를 설계 하고 구현 합 니 다.다음 동작 을 지원 해 야 합 니 다: get 과 put.

get(key) - 키 가 캐 시 에 존재 하면 키 의 값 (항상 정수) 을 가 져 옵 니 다. 그렇지 않 으 면 - 1 을 되 돌려 줍 니 다.

put(key, value) - 키 가 존재 하지 않 으 면 값 을 설정 하거나 삽입 하 십시오.

캐 시가 용량 에 도 달 했 을 때 새 항목 을 삽입 하기 전에 가장 자주 사용 하지 않 는 항목 을 무효 로 해 야 합 니 다.

이 문제 에서 무승부 (즉, 두 개 이상 의 키 가 같은 사용 주파 수 를 가지 고 있 음) 가 존재 할 때 최근 에 가장 적 게 사용 한 키 는 제 거 됩 니 다.

진급: O (1) 시간 복잡 도 에서 두 가지 조작 을 수행 할 수 있 습 니까?

  ：
LFUCache cache = new LFUCache( 2 /* capacity (    ) */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       //    1
cache.put(3, 3);    //    key 2
cache.get(2);       //    -1 (   key 2)
cache.get(3);       //    3
cache.put(4, 4);    //    key 1
cache.get(1);       //    -1 (    key 1)
cache.get(3);       //    3
cache.get(4);       //    4

출처: 스냅 백 (LeetCode) 링크:https://leetcode-cn.com/problems/lfu-cache 저작권 은 인터넷 에 귀속 된다.상업 전 재 는 정부 에 연락 하여 권한 을 부여 해 주 십시오. 비 상업 전 재 는 출처 를 밝 혀 주 십시오.
2. 문제 풀이

유사 한 제목: LeetCode 146. LRU 캐 시 메커니즘 (해시 링크)

class node{
public:
	int k, v, f;
	node(int key, int val, int freq):k(key),v(val),f(freq){}
};

class LFUCache {
	unordered_map<int, list<node>::iterator> kPos;//key           
    unordered_map<int, list<node>> freq_list;//             ，        
    int cap;
    int minfreq;//     
    int size;
public:
    LFUCache(int capacity) {
    	cap = capacity;
    	minfreq = 0;
    	size = 0;
    }
    
    int get(int key) {
    	if(kPos.find(key)==kPos.end())
    		return -1;
    	auto it = kPos[key];//        
    	int f = it->f;
    	int v = it->v;
    	if(f == minfreq && freq_list[f].size() == 1)
    		minfreq++;//          1 ，    ，    +1
    	freq_list[f].erase(it);//  
    	freq_list[++f].push_front(node(key,v,f));//          
    	kPos[key] = freq_list[f].begin();//       
    	return v;
    }
    
    void put(int key, int value) {
    	if(kPos.find(key)!=kPos.end())
    	{	//  key
    		auto it = kPos[key];
			int f = it->f;
			if(f == minfreq && freq_list[f].size()==1)
				minfreq++;
			freq_list[f].erase(it);
			freq_list[++f].push_front(node(key,value,f));
			kPos[key] = freq_list[f].begin();
    	}
    	else if(size < cap)//   key，     
    	{
			minfreq = 1;//      1 
			freq_list[minfreq].push_front(node(key,value,1));
			kPos[key] = freq_list[1].begin();
			size++;
    	}
    	else if(cap != 0 && size == cap)//   key，   ，     0
    	{
    		auto Node = freq_list[minfreq].back();
    		int k = Node.k;
    		freq_list[minfreq].pop_back();//            
    		kPos.erase(k);//    key      
    		size--;
    		put(key, value);
    	}
    }
};

228 ms 40 MB