思路:
使用链表结构模拟
代码:
let obj = {}; // 仿链表结构 let res = {}; // map结果 let cnt = 0; // 标记键值对个数 let pre = undefined; // 标记上一个 let head = undefined; // 标记链表头部节点 let tail = undefined; // 标记链表最后一个节点 function LRUCache(capacity) { function updateKeyVal(key) { if(head === obj[key]) { // 当前节点为头部 head = obj[key].nextt || obj[key]; head.pre = null; obj[key].pre = tail; tail = obj[key]; obj[key].nextt = null; if(head.nextt === null) { head.nextt = tail; } } else if(tail !== obj[key]) { // 当前节点不能为尾部 尾部无需改变节点位置 obj[key].pre.nextt = obj[key].nextt; obj[key].pre = tail; tail = obj[key]; obj[key].nextt = null; } } this.set = function (key, val) { if(obj[key]){ // 更新 updateKeyVal(key); obj[key] = { val: val, }; } else { // 插入 cnt++; if(cnt <= capacity) { // 有容量 直接在尾部插入新节点 obj[key] = { val: val, key: key, pre: null, nextt: null, } if(pre === undefined) { pre = obj[key]; head = obj[key]; tail = obj[key]; } else { pre.nextt = obj[key]; obj[key].pre = pre; pre = obj[key]; tail = obj[key]; } } else { // 容量已满 删除头部节点 并在尾部插入新节点 cnt--; delete obj[head.key]; delete res[head.key]; head = head.nextt; head.pre = null; obj[key] = { val: val, key: key, pre: tail, nextt: null, } tail = obj[key]; if(head.nextt === null) { head.nextt = tail; } } } res[key] = val; // console.log(res, "====set====="); let result = head; let str = "{" + result.key + "=" +result.val; while (result.nextt) { result = result.nextt; str += ", " + result.key + "=" +result.val; } str += "}"; console.log(str); } this.get = function (key) { if (obj[key]) { updateKeyVal(key); console.log(obj[key].val); return obj[key].val; } else { console.log(-1); return -1; } } } const cache = new LRUCache(2); cache.set(1, 1); // 缓存是 {1=1} cache.set(2, 2); // 缓存是 {1=1, 2=2} cache.get(1); // 返回 1 cache.set(3, 3); // 该操作会使得关键字 2 作废,缓存是 {1=1, 3=3} cache.get(2); // 返回 -1 (未找到) cache.set(4, 4); // 该操作会使得关键字 1 作废,缓存是 {4=4, 3=3} cache.get(1); // 返回 -1 (未找到) cache.get(3); // 返回 3 cache.get(4); // 返回 4