LRU Cache - 2019 회 가을 모집 전문 필기시험 (연구 개발 방향)

제목 설명
LRU Cache 기능 을 구현 하 는 데이터 구 조 를 설계 합 니 다 (Least Recently Used – 최근 최소 캐 시 사용).다음 두 가지 동작 을 지원 합 니 다: get 과 put.
int get (int key) – key 가 존재 하면 key 에 대응 하 는 값 value (항상 0 이상) 를 되 돌려 줍 니 다.키 가 존재 하지 않 으 면 - 1 을 되 돌려 줍 니 다.void put (int key, int value) – 키 가 존재 하지 않 으 면 값 을 삽입 합 니 다.키 가 존재 한다 면, 원래 존재 하 던 값 을 value 로 대체 합 니 다.용량 이 제한 되면 LRU Cache 는 새 요 소 를 삽입 하기 전에 최근 에 가장 적 게 사용 한 요 소 를 삭제 해 야 한다.
"사용" 의 정의 에 특히 주의 하 십시오. 키 를 새로 삽입 하거나 가 져 오 는 것 은 한 번 사용 되 는 것 으로 간주 합 니 다.이미 존재 하 는 값 을 교체 하여 업데이트 합 니 다. 사용 되 지 않 습 니 다.
제한: O (1) 의 시간 복잡 도 에서 상기 두 가지 조작 을 완성 하 십시오.
입력 설명
첫 줄 은 LRU Cache 의 용량 제한 을 나타 내 는 정수 n 을 읽 습 니 다.두 번 째 줄 부터 파일 끝까지 한 줄 마다 한 개의 조작 을 대표 합 니 다.
각 줄 의 첫 번 째 문자 가 p 이면 이 문자 뒤 에는 두 개의 정수 가 따라 와 put 작업 의 key 와 value 를 표시 합 니 다.
각 줄 의 첫 번 째 문자 가 g 이면 이 문자 뒤 에는 1 개의 정수 가 따라 get 작업 의 key 를 표시 합 니 다.
출력 설명
입력 중 get 작업 이 나타 나 는 순서에 따라 get 작업 의 결 과 를 줄 별로 출력 합 니 다.
예시
입력
2 p 1 1 p 2 2 g 1 p 2 102 p 3 3 g 1 g 2 g 3
출력
1 1 -1 3
설명 하 다.
2 / / cache 용량 은 2p 1 1 / put (1, 1) p 2 2 / / put (2, 2) g 1 / get (1), 1p 2 102 / / put (2, 102), 이미 존재 하 는 key 를 업데이트 합 니 다. p 3 / / put (3, 3) 를 사용 하지 않 고 용량 이 제한 을 초과 하여 최근 최소 사용 한 key = 2 를 g 1 / / get (1) 을 제거 하고 1g 2 / / get (2) 을 되 돌려 줍 니 다. - 1g 3 / / get (3) 을 되 돌려 줍 니 다.
제목 분석
이 문 제 는 (hashMap + 양 방향 링크) 의 사상 으로 완성 할 수 있다.그 중에서 양 방향 링크 의 삽입 복잡 도 는 O (1) 이 고 hashMap 의 검색 복잡 도 는 O (1) 이 며 제목 의 요구 에 부합 합 니 다.사고: put 작업: 먼저 map 에 key 값 이 나 타 났 는 지 확인 하고 key 가 나 타 났 다 면 value 를 교체 합 니 다. 나타 나 지 않 았 다 면 링크 가 가득 찼 는 지, 가득 차지 않 았 다 면 양 방향 링크 맨 앞 에 직접 삽입 합 니 다.가득 차 면 양 방향 링크 의 마지막 부분 에 있 는 요 소 를 삭제 하고 삽입 합 니 다.맵 을 동시에 업데이트 합 니 다.
get 동작:

map 에 key 값 이 나타 나 면 해당 하 는 value 를 되 돌려 주 고 링크 에 대응 하 는 key - value 를 대기 열 첫 부분 으로 올 려 map 를 업데이트 합 니 다.

나타 나 지 않 으 면 돌아 오기 - 1

hashmap 저장 을 사용 하 는 이 유 는 hashmap 에 저 장 된 value 가 양 방향 목록 의 교체 기 (요소 의 포인터) 이기 때 문 입 니 다. 그러면 목록 에서 요 소 를 조회 하 는 시간 복잡 도 를 O (N) 에서 O (1) 로 낮 출 수 있 습 니 다.자세 한 내용 은 코드 설명 을 보십시오.
코드
C + + 코드 는 다음 과 같 습 니 다.

#include 
#include 
#include 
#include 
using namespace std;
 
typedef unordered_map<int, list<pair<int, int> >::iterator> hashMap;
//          ，              
list<pair<int, int> > li;
 
hashMap map;
int capacity;
 
void put(int k,int v)
{
     
    auto it=map.find(k);//  k     
    if(it!=map.end())
    {
     
        it->second->second=v;//          
    }
    else
    {
     
        if(li.size()==capacity)
        {
     
            int key=li.back().first;//       key 
            li.pop_back();//      
            map.erase(key);//  key  
        }
        li.push_front(make_pair(k,v));//   key,value      
        map[k]=li.begin();//map          
    }
}

int get(int k)
{
     
    auto it=map.find(k);//  k       
    if(it==map.end())
        return -1;//      
    int res=it->second->second;//  key   value 
    li.erase(it->second);// value      
    li.push_front(make_pair(k,res));//     key，value        
    map[k]=li.begin();//map          
    return res;
}
int main()
{
     
    int k,v;
    char c;
    cin>>capacity;
    while(cin>>c)
    {
     
        if(c=='p')
        {
     
            cin>>k>>v;
            if(capacity<=0)//      ，    LRU，      
                continue;
            put(k,v);
        }
        if(c=='g')
        {
     
            cin>>k;
            cout<<get(k)<<endl;
        }
    }
    return 0;
}