题目描述设计一个文件缓存系统缓存有最大容量m字节。支持两种操作put fileName fileSize把文件放进缓存。如果同名文件已存在不操作。get fileName读取缓存里的文件。如果不存在不操作。当缓存空间不够放新文件时按规则删除老文件直到空间够为止优先删除访问次数少的访问次数相同删除最近一次访问时间最早的末尾输出缓存中所有文件名按字典序用英文逗号分隔。如果没有文件输出NONE。操作数n最多 30 万。讲个故事小明的手机内存又满了小明手机内存只有 128G相册、视频、App 塞得满满当当。他的清理策略是先看哪个 App 打开次数最少打开次数一样看哪个最久没打开删掉腾地方这个缓存系统干的就是一样的事。核心原理堆 懒删除这道题的关键是按访问次数和时间删除。每次 get 都会改变一个文件的访问次数和时间所以我们需要一个能动态维护最小值的结构。最小堆正好干这个活。堆里的每个元素是(访问次数, 最近访问时间, 文件名)。但有个麻烦get 之后旧堆元素就过期了。直接删旧元素太慢所以用懒删除堆里可能有很多过期条目先不管要淘汰时从堆顶往下找找到第一条当前信息还匹配的条目再删这样每次 get 只需要往堆里 push 一个新条目时间复杂度O(log n)。怎么实现用字典/哈希表存每个文件的(大小, 访问次数, 最近访问时间)全局一个时间戳每次有效操作 1get 操作更新次数和时间往堆里 push 新条目put 操作如果文件已存在忽略否则先淘汰文件再插入末尾把剩余文件名排序输出代码实现C 语言#includestdio.h#includestdlib.h#includestring.h#defineMAXN300005typedefstruct{intcnt,time;charname[64];}HeapNode;HeapNode heap[MAXN];intheapSize0;typedefstructFile{intsize,cnt,time;intinCache;}File;File*files[MAXN];intfileCount0;intfileIdx(constchar*name){for(inti0;ifileCount;i)if(files[i]strcmp(files[i]-name,name)0)returni;return-1;}// 简单字符串哈希找文件位置实际比赛建议用哈希表// 这里为了代码清晰用线性查找示意voidheapSwap(inti,intj){HeapNode theap[i];heap[i]heap[j];heap[j]t;}voidheapPush(HeapNode x){intiheapSize;heap[i]x;while(i1){intpi/2;if(heap[p].cntheap[i].cnt||(heap[p].cntheap[i].cntheap[p].timeheap[i].time))break;heapSwap(p,i);ip;}}HeapNodeheapPop(){HeapNode topheap[1];heap[1]heap[heapSize--];inti1;while(1){intli*2,rl1,mini;if(lheapSize){if(heap[l].cntheap[min].cnt||(heap[l].cntheap[min].cntheap[l].timeheap[min].time))minl;}if(rheapSize){if(heap[r].cntheap[min].cnt||(heap[r].cntheap[min].cntheap[r].timeheap[min].time))minr;}if(mini)break;heapSwap(i,min);imin;}returntop;}// 由于 C 版需要配合输入输出核心逻辑如下voidcacheSystem(intm,intn,charops[][128]){intused0,curTime0;// 实际实现需配合具体输入格式}C#includebits/stdc.husingnamespacestd;structFileInfo{intsize,cnt,time;};stringcacheSystem(intm,vectorstringops){unordered_mapstring,FileInfofiles;usingTtupleint,int,string;priority_queueT,vectorT,greaterTpq;intused0,curTime0;for(string op:ops){stringstreamss(op);string cmd;sscmd;if(cmdget){string name;ssname;autoitfiles.find(name);if(it!files.end()){curTime;it-second.cnt;it-second.timecurTime;pq.push({it-second.cnt,curTime,name});}}else{string name;intsize;ssnamesize;if(files.count(name))continue;curTime;while(usedsizem){while(!pq.empty()){auto[cnt,t,nname]pq.top();autoitfiles.find(nname);if(it!files.end()it-second.cntcntit-second.timet)break;pq.pop();}if(pq.empty())break;auto[cnt,t,nname]pq.top();pq.pop();autoitfiles.find(nname);if(it!files.end()it-second.cntcntit-second.timet){used-it-second.size;files.erase(it);}}if(usedsizem){files[name]{size,0,curTime};usedsize;pq.push({0,curTime,name});}}}if(files.empty())returnNONE;vectorstringnames;for(autop:files)names.push_back(p.first);sort(names.begin(),names.end());string ansnames[0];for(inti1;inames.size();i)ans,names[i];returnans;}Javaimportjava.util.*;publicclassMain{staticclassFileInfo{intsize,cnt,time;FileInfo(ints,intc,intt){sizes;cntc;timet;}}publicstaticStringcacheSystem(intm,String[]ops){MapString,FileInfofilesnewHashMap();PriorityQueueint[]pqnewPriorityQueue((a,b)-{if(a[0]!b[0])returna[0]-b[0];returna[1]-b[1];});intused0,curTime0;for(Stringop:ops){String[]partsop.split( );Stringcmdparts[0];if(cmd.equals(get)){Stringnameparts[1];FileInfoffiles.get(name);if(f!null){curTime;f.cnt;f.timecurTime;pq.offer(newint[]{f.cnt,curTime,name.hashCode()});// 实际判重需要同时存 name这里用额外 Map 维护}}else{Stringnameparts[1];intsizeInteger.parseInt(parts[2]);if(files.containsKey(name))continue;curTime;while(usedsizem){while(!pq.isEmpty()){int[]toppq.peek();FileInfoffiles.get(name);// 需要 name 参与判断建议堆元素用对象存 name// 简化展示核心逻辑break;}if(pq.isEmpty())break;pq.poll();}if(usedsizem){files.put(name,newFileInfo(size,0,curTime));usedsize;}}}if(files.isEmpty())returnNONE;ListStringnamesnewArrayList(files.keySet());Collections.sort(names);returnString.join(,,names);}}JavaScriptfunctioncacheSystem(m,ops){constfilesnewMap();constpq[];letused0,curTime0;constpush(node){pq.push(node);pq.sort((a,b)a[0]!b[0]?a[0]-b[0]:a[1]-b[1]);};for(constopofops){constpartsop.split( );constcmdparts[0];if(cmdget){constnameparts[1];constffiles.get(name);if(f){curTime;f.cnt;f.timecurTime;push([f.cnt,curTime,name]);}}else{constnameparts[1],sizeparseInt(parts[2]);if(files.has(name))continue;curTime;while(usedsizem){while(pq.length0){const[cnt,t,nname]pq[0];constffiles.get(nname);if(ff.cntcntf.timet)break;pq.shift();}if(pq.length0)break;const[cnt,t,nname]pq.shift();constffiles.get(nname);if(ff.cntcntf.timet){used-f.size;files.delete(nname);}}if(usedsizem){files.set(name,{size,cnt:0,time:curTime});usedsize;push([0,curTime,name]);}}}if(files.size0)returnNONE;constnamesArray.from(files.keys()).sort();returnnames.join(,);}Pythonimportheapqdefcache_system(m,ops):files{}# name - [size, cnt, time]heap[]# (cnt, time, name)used0cur_time0foropinops:partsop.split()cmdparts[0]ifcmdget:nameparts[1]ifnameinfiles:cur_time1files[name][1]1files[name][2]cur_time heapq.heappush(heap,(files[name][1],cur_time,name))else:name,sizeparts[1],int(parts[2])ifnameinfiles:continuecur_time1whileusedsizem:# 懒删除找到堆顶有效的条目whileheap:cnt,t,nnameheap[0]ffiles.get(nname)iffandf[1]cntandf[2]t:breakheapq.heappop(heap)ifnotheap:breakcnt,t,nnameheapq.heappop(heap)ffiles.get(nname)iffandf[1]cntandf[2]t:used-f[0]delfiles[nname]ifusedsizem:files[name][size,0,cur_time]usedsize heapq.heappush(heap,(0,cur_time,name))ifnotfiles:returnNONEreturn,.join(sorted(files.keys()))复杂度分析每次操作最多 push 一个堆元素O(log n)懒删除的 pop 均摊也是O(log n)总时间复杂度O(n * log n)空间复杂度O(n)存文件信息和堆条目总结一下文件缓存系统 带访问频率的 LRU 变体。核心思路用哈希表记录文件实时状态用最小堆维护淘汰顺序用懒删除处理访问次数/时间的更新这道题最容易踩的坑是get 之后旧堆条目没及时清理导致淘汰了不该淘汰的文件。懒删除能完美解决。你写缓存淘汰策略时更喜欢用堆还是链表欢迎在评论区聊聊。