dw做网站环境配置网站建设前端工程师岗位职责

dw做网站环境配置,网站建设前端工程师岗位职责,怎么用h5网站做动效,简单网站建设价格文章目录摘要描述题解答案题解代码分析节点需要存什么信息#xff1f;为什么要用「频次 → 双向链表」#xff1f;LFUCache 的核心结构get 操作怎么做#xff1f;put 操作的关键点更新频次是整个设计的核心示例测试及结果与实际场景结合时间复杂度空间复杂度总结摘要 LFU 缓…文章目录摘要描述题解答案题解代码分析节点需要存什么信息为什么要用「频次 → 双向链表」LFUCache 的核心结构get 操作怎么做put 操作的关键点更新频次是整个设计的核心示例测试及结果与实际场景结合时间复杂度空间复杂度总结摘要LFU 缓存是缓存算法里的“进阶关卡”。LRU 大家都很熟但 LFU 往往是很多人刷 LeetCode 时第一次真正感受到“原来 O(1) 的设计不是写得快而是数据结构选得对。”这道题不只是让你写一个缓存而是在逼你回答三个工程级问题怎么在 O(1) 内找到最少使用的 key使用次数相同时怎么再按 LRU 淘汰get / put 都要是 O(1)不能靠排序、遍历硬撑。描述题目要求你实现一个 LFUCache支持get(key)存在返回 value并且使用次数 1不存在返回 -1put(key, value)key 已存在更新 value并且使用次数 1key 不存在如果缓存没满直接插如果缓存满了先淘汰使用次数最少如果次数相同淘汰最久没用的并且有一个非常重要的硬指标get和put的平均时间复杂度必须是O(1)这直接排除了所有“排序 / 每次扫描一遍”的方案。题解答案真正能跑通并满足 O(1) 的解法核心是三层结构key → Node 映射freq → 双向链表 映射一个全局的minFreq一句话总结用 HashMap 快速定位节点用「频次分桶 LRU 链表」来控制淘汰顺序。题解代码分析节点需要存什么信息每一个缓存项至少要知道keyvalue当前使用频率 freq在链表里的前后指针为了 O(1) 删除classNode{letkey:Intvarvalue:Intvarfreq:Int1varprev:Node?varnext:Node?init(_key:Int,_value:Int){self.keykeyself.valuevalue}}为什么要用「频次 → 双向链表」因为 LFU 有一个隐藏条件同一个频次下要按 LRU 淘汰所以每个频次桶本质上是一个LRU 链表。classDoublyLinkedList{letheadNode(0,0)lettailNode(0,0)varsize0init(){head.nexttail tail.prevhead}funcaddToHead(_node:Node){node.nexthead.next node.prevhead head.next?.prevnode head.nextnode size1}funcremove(_node:Node){node.prev?.nextnode.next node.next?.prevnode.prev size-1}funcremoveLast()-Node?{guardsize0,letlasttail.prev,last!headelse{returnnil}remove(last)returnlast}}LFUCache 的核心结构classLFUCache{privateletcapacity:IntprivatevarminFreq0privatevarkeyToNode[Int:Node]()privatevarfreqToList[Int:DoublyLinkedList]()keyToNodeO(1) 找节点freqToListO(1) 找某个频次的 LRU 链表minFreqO(1) 知道该淘汰谁get 操作怎么做核心逻辑只有三步查 key 是否存在从旧 freq 链表中移除freq 1放进新链表funcget(_key:Int)-Int{guardletnodekeyToNode[key]else{return-1}updateFreq(node)returnnode.value}put 操作的关键点capacity 为 0直接返回key 已存在更新 value 更新 freqkey 不存在如果满了从minFreq对应的链表里删最久未使用插入新节点freq 1funcput(_key:Int,_value:Int){ifcapacity0{return}ifletnodekeyToNode[key]{node.valuevalueupdateFreq(node)return}ifkeyToNode.countcapacity{ifletlistfreqToList[minFreq],letremovedlist.removeLast(){keyToNode.removeValue(forKey:removed.key)}}letnewNodeNode(key,value)keyToNode[key]newNodeletlistfreqToList[1]??DoublyLinkedList()list.addToHead(newNode)freqToList[1]list minFreq1}更新频次是整个设计的核心privatefuncupdateFreq(_node:Node){letfreqnode.freqifletlistfreqToList[freq]{list.remove(node)iffreqminFreqlist.size0{minFreq1}}node.freq1letnewListfreqToList[node.freq]??DoublyLinkedList()newList.addToHead(node)freqToList[node.freq]newList}这里做了三件事从旧频次链表移除如果刚好是 minFreq 且链表空了更新 minFreq插入新频次链表头部示例测试及结果letlfuLFUCache(2)lfu.put(1,1)lfu.put(2,2)print(lfu.get(1))// 1lfu.put(3,3)print(lfu.get(2))// -1print(lfu.get(3))// 3lfu.put(4,4)print(lfu.get(1))// -1print(lfu.get(3))// 3print(lfu.get(4))// 4输出结果1 -1 3 -1 3 4和题目示例完全一致。与实际场景结合LFU 在真实项目里比你想象中常见比如CDN 本地缓存App 内图片 / 数据缓存后端热点数据保护推荐系统中的候选集缓存相比 LRULFU 更适合“长期高频访问的数据不能因为短期冷却就被干掉”比如用户主页、配置数据、热门商品列表。时间复杂度getO(1)putO(1)这是通过HashMap 双向链表 minFreq联合保证的。空间复杂度O(capacity)所有节点、链表总数都和缓存容量线性相关。总结LFU 这道题真正难的不是代码多而是你能不能拆清楚“频次”和“时间”这两个维度你能不能在 O(1) 下把这两个维度同时维护住如果你能完整写出这道题其实已经具备了设计复杂缓存系统的能力面试中讲清楚“为什么这样设计”的底气把算法真正落地成工程代码的经验