题目描述
设计一个文件缓存系统，缓存有最大容量m（字节）。支持两种操作：
put fileName fileSize：把文件放进缓存。如果同名文件已存在，不操作。get fileName：读取缓存里的文件。如果不存在，不操作。
当缓存空间不够放新文件时，按规则删除老文件，直到空间够为止：
- 优先删除访问次数少的
- 访问次数相同，删除最近一次访问时间最早的
末尾输出缓存中所有文件名，按字典序用英文逗号分隔。如果没有文件，输出NONE。
操作数n最多 30 万。
讲个故事：小明的手机内存又满了
小明手机内存只有 128G，相册、视频、App 塞得满满当当。
他的清理策略是：
- 先看哪个 App 打开次数最少
- 打开次数一样？看哪个最久没打开
- 删掉，腾地方
这个缓存系统干的就是一样的事。
核心原理：堆 + 懒删除
这道题的关键是"按访问次数和时间删除"。每次 get 都会改变一个文件的访问次数和时间，所以我们需要一个能动态维护最小值的结构。
最小堆正好干这个活。堆里的每个元素是(访问次数, 最近访问时间, 文件名)。
但有个麻烦：get 之后，旧堆元素就过期了。直接删旧元素太慢，所以用懒删除：
- 堆里可能有很多过期条目，先不管
- 要淘汰时，从堆顶往下找，找到第一条"当前信息还匹配"的条目再删
这样每次 get 只需要往堆里 push 一个新条目，时间复杂度O(log n)。
怎么实现？
- 用字典/哈希表存每个文件的
(大小, 访问次数, 最近访问时间) - 全局一个时间戳，每次有效操作 +1
- get 操作：更新次数和时间，往堆里 push 新条目
- put 操作：如果文件已存在，忽略；否则先淘汰文件，再插入
- 末尾把剩余文件名排序输出
代码实现
C 语言
#include<stdio.h>#include<stdlib.h>#include<string.h>#defineMAXN300005typedefstruct{intcnt,time;charname[64];}HeapNode;HeapNode heap[MAXN];intheapSize=0;typedefstructFile{intsize,cnt,time;intinCache;}File;File*files[MAXN];intfileCount=0;intfileIdx(constchar*name){for(inti=0;i<fileCount;i++)if(files[i]&&strcmp(files[i]->name,name)==0)returni;return-1;}// 简单字符串哈希找文件位置，实际比赛建议用哈希表// 这里为了代码清晰，用线性查找示意voidheapSwap(inti,intj){HeapNode t=heap[i];heap[i]=heap[j];heap[j]=t;}voidheapPush(HeapNode x){inti=++heapSize;heap[i]=x;while(i>1){intp=i/2;if(heap[p].cnt<heap[i].cnt||(heap[p].cnt==heap[i].cnt&&heap[p].time<=heap[i].time))break;heapSwap(p,i);i=p;}}HeapNodeheapPop(){HeapNode top=heap[1];heap[1]=heap[heapSize--];inti=1;while(1){intl=i*2,r=l+1,min=i;if(l<=heapSize){if(heap[l].cnt<heap[min].cnt||(heap[l].cnt==heap[min].cnt&&heap[l].time<heap[min].time))min=l;}if(r<=heapSize){if(heap[r].cnt<heap[min].cnt||(heap[r].cnt==heap[min].cnt&&heap[r].time<heap[min].time))min=r;}if(min==i)break;heapSwap(i,min);i=min;}returntop;}// 由于 C 版需要配合输入输出，核心逻辑如下voidcacheSystem(intm,intn,charops[][128]){intused=0,curTime=0;// 实际实现需配合具体输入格式}C++
#include<bits/stdc++.h>usingnamespacestd;structFileInfo{intsize,cnt,time;};stringcacheSystem(intm,vector<string>ops){unordered_map<string,FileInfo>files;usingT=tuple<int,int,string>;priority_queue<T,vector<T>,greater<T>>pq;intused=0,curTime=0;for(string op:ops){stringstreamss(op);string cmd;ss>>cmd;if(cmd=="get"){string name;ss>>name;autoit=files.find(name);if(it!=files.end()){curTime++;it->second.cnt++;it->second.time=curTime;pq.push({it->second.cnt,curTime,name});}}else{string name;intsize;ss>>name>>size;if(files.count(name))continue;curTime++;while(used+size>m){while(!pq.empty()){auto[cnt,t,nname]=pq.top();autoit=files.find(nname);if(it!=files.end()&&it->second.cnt==cnt&&it->second.time==t)break;pq.pop();}if(pq.empty())break;auto[cnt,t,nname]=pq.top();pq.pop();autoit=files.find(nname);if(it!=files.end()&&it->second.cnt==cnt&&it->second.time==t){used-=it->second.size;files.erase(it);}}if(used+size<=m){files[name]={size,0,curTime};used+=size;pq.push({0,curTime,name});}}}if(files.empty())return"NONE";vector<string>names;for(auto&p:files)names.push_back(p.first);sort(names.begin(),names.end());string ans=names[0];for(inti=1;i<names.size();i++)ans+=","+names[i];returnans;}Java
importjava.util.*;publicclassMain{staticclassFileInfo{intsize,cnt,time;FileInfo(ints,intc,intt){size=s;cnt=c;time=t;}}publicstaticStringcacheSystem(intm,String[]ops){Map<String,FileInfo>files=newHashMap<>();PriorityQueue<int[]>pq=newPriorityQueue<>((a,b)->{if(a[0]!=b[0])returna[0]-b[0];returna[1]-b[1];});intused=0,curTime=0;for(Stringop:ops){String[]parts=op.split(" ");Stringcmd=parts[0];if(cmd.equals("get")){Stringname=parts[1];FileInfof=files.get(name);if(f!=null){curTime++;f.cnt++;f.time=curTime;pq.offer(newint[]{f.cnt,curTime,name.hashCode()});// 实际判重需要同时存 name，这里用额外 Map 维护}}else{Stringname=parts[1];intsize=Integer.parseInt(parts[2]);if(files.containsKey(name))continue;curTime++;while(used+size>m){while(!pq.isEmpty()){int[]top=pq.peek();FileInfof=files.get(name);// 需要 name 参与判断，建议堆元素用对象存 name// 简化展示核心逻辑break;}if(pq.isEmpty())break;pq.poll();}if(used+size<=m){files.put(name,newFileInfo(size,0,curTime));used+=size;}}}if(files.isEmpty())return"NONE";List<String>names=newArrayList<>(files.keySet());Collections.sort(names);returnString.join(",",names);}}JavaScript
functioncacheSystem(m,ops){constfiles=newMap();constpq=[];letused=0,curTime=0;constpush=(node)=>{pq.push(node);pq.sort((a,b)=>a[0]!==b[0]?a[0]-b[0]:a[1]-b[1]);};for(constopofops){constparts=op.split(' ');constcmd=parts[0];if(cmd==='get'){constname=parts[1];constf=files.get(name);if(f){curTime++;f.cnt++;f.time=curTime;push([f.cnt,curTime,name]);}}else{constname=parts[1],size=parseInt(parts[2]);if(files.has(name))continue;curTime++;while(used+size>m){while(pq.length>0){const[cnt,t,nname]=pq[0];constf=files.get(nname);if(f&&f.cnt===cnt&&f.time===t)break;pq.shift();}if(pq.length===0)break;const[cnt,t,nname]=pq.shift();constf=files.get(nname);if(f&&f.cnt===cnt&&f.time===t){used-=f.size;files.delete(nname);}}if(used+size<=m){files.set(name,{size,cnt:0,time:curTime});used+=size;push([0,curTime,name]);}}}if(files.size===0)return'NONE';constnames=Array.from(files.keys()).sort();returnnames.join(',');}Python
importheapqdefcache_system(m,ops):files={}# name -> [size, cnt, time]heap=[]# (cnt, time, name)used=0cur_time=0foropinops:parts=op.split()cmd=parts[0]ifcmd=='get':name=parts[1]ifnameinfiles:cur_time+=1files[name][1]+=1files[name][2]=cur_time heapq.heappush(heap,(files[name][1],cur_time,name))else:name,size=parts[1],int(parts[2])ifnameinfiles:continuecur_time+=1whileused+size>m:# 懒删除：找到堆顶有效的条目whileheap:cnt,t,nname=heap[0]f=files.get(nname)iffandf[1]==cntandf[2]==t:breakheapq.heappop(heap)ifnotheap:breakcnt,t,nname=heapq.heappop(heap)f=files.get(nname)iffandf[1]==cntandf[2]==t:used-=f[0]delfiles[nname]ifused+size<=m:files[name]=[size,0,cur_time]used+=size heapq.heappush(heap,(0,cur_time,name))ifnotfiles:return'NONE'return','.join(sorted(files.keys()))复杂度分析
- 每次操作最多 push 一个堆元素，
O(log n) - 懒删除的 pop 均摊也是
O(log n) - 总时间复杂度：
O(n * log n) - 空间复杂度：
O(n)，存文件信息和堆条目
总结一下
文件缓存系统 = 带访问频率的 LRU 变体。
核心思路：
- 用哈希表记录文件实时状态
- 用最小堆维护淘汰顺序
- 用懒删除处理访问次数/时间的更新
这道题最容易踩的坑是：get 之后旧堆条目没及时清理，导致淘汰了不该淘汰的文件。懒删除能完美解决。
你写缓存淘汰策略时，更喜欢用堆还是链表？欢迎在评论区聊聊。