企业官网建设流程全解析

1.思路：需要在LRU（最近最少使用）的基础上继续实现。

（1）在定义双向链表节点Node的时候，给Node增加过期时间戳字段expireTime（表示该节点的过期时间是多少）和检查节点是否过期的成员方法（实例方法）boolean isExpired()（如果当前时间的毫秒数System.currentTimeMillis() > expireTime，那么就return true，表示该节点已经过期）。

后续更新

附代码：

class TimeoutLRUCache { // 双向链表节点，增加过期时间戳字段 private static class Node { int key, value; long expireTime; // 过期时间戳（毫秒） Node prev, next; Node(int key, int value, long expireTime) { this.key = key; this.value = value; this.expireTime = expireTime; this.prev = null; this.next = null; } // 检查节点是否已过期 boolean isExpired() { return System.currentTimeMillis() > expireTime; } } private final int capacity; private final long defaultTtl; // 默认过期时间（毫秒） private final Node sentinel = new Node(0, 0, Long.MAX_VALUE); private final Map<Integer, Node> keyToNode = new HashMap<>(); // 构造函数：只指定容量，使用默认过期时间（5分钟） public TimeoutLRUCache(int capacity) { this(capacity, 300000); // 默认5分钟 } // 构造函数：指定容量和默认过期时间（毫秒） public TimeoutLRUCache(int capacity, long defaultTtl) { this.capacity = capacity; this.defaultTtl = defaultTtl; sentinel.prev = sentinel; sentinel.next = sentinel; } // 获取值，如果已过期则返回 -1 public int get(int key) { Node node = getNode(key); if (node == null || node.isExpired()) { if (node != null) { // 过期节点从缓存中移除 remove(node); keyToNode.remove(key); } return -1; } return node.value; } // 放入缓存，使用默认过期时间 public void put(int key, int value) { put(key, value, defaultTtl); } // 放入缓存，指定过期时间（毫秒） public void put(int key, int value, long ttlMillis) { Node node = getNode(key); if (node != null) { // 更新存在的节点 node.value = value; node.expireTime = System.currentTimeMillis() + ttlMillis; return; } // 创建新节点 long expireTime = System.currentTimeMillis() + ttlMillis; node = new Node(key, value, expireTime); keyToNode.put(key, node); pushFront(node); // 清理过期节点 + 容量控制 cleanExpiredNodes(); if (keyToNode.size() > capacity) { Node backNode = sentinel.prev; // 从后往前清理，优先清理过期节点 while (backNode != sentinel && keyToNode.size() > capacity) { if (backNode.isExpired()) { Node toRemove = backNode; backNode = backNode.prev; keyToNode.remove(toRemove.key); remove(toRemove); } else if (keyToNode.size() > capacity) { // 容量超限，移除最久未使用的节点 keyToNode.remove(backNode.key); remove(backNode); backNode = sentinel.prev; } } } } // 获取节点并移到头部 private Node getNode(int key) { if (!keyToNode.containsKey(key)) { return null; } Node node = keyToNode.get(key); // 如果节点已过期，返回null（让调用方处理） if (node.isExpired()) { return null; } remove(node); pushFront(node); return node; } // 清理所有过期节点 private void cleanExpiredNodes() { Node current = sentinel.prev; while (current != sentinel) { Node next = current.prev; if (current.isExpired()) { keyToNode.remove(current.key); remove(current); } current = next; } } // 从链表中移除节点 private void remove(Node x) { x.prev.next = x.next; x.next.prev = x.prev; } // 将节点插入链表头部 private void pushFront(Node x) { x.prev = sentinel; x.next = sentinel.next; x.prev.next = x; x.next.prev = x; } // 获取当前缓存大小（包含未过期节点） public int size() { cleanExpiredNodes(); return keyToNode.size(); } // 检查缓存是否包含某个key（未过期） public boolean containsKey(int key) { Node node = keyToNode.get(key); return node != null && !node.isExpired(); } }

ACM模式：

import java.util.*; class TimeoutLRUCache { // 双向链表节点，增加过期时间戳字段 private static class Node { int key, value; long expireTime; // 过期时间戳（毫秒） Node prev, next; Node(int key, int value, long expireTime) { this.key = key; this.value = value; this.expireTime = expireTime; this.prev = null; this.next = null; } // 检查节点是否已过期 boolean isExpired() { return System.currentTimeMillis() > expireTime; } } private final int capacity; private final long defaultTtl; // 默认过期时间（毫秒） private final Node sentinel = new Node(0, 0, Long.MAX_VALUE); private final Map<Integer, Node> keyToNode = new HashMap<>(); // 构造函数：只指定容量，使用默认过期时间（5分钟） public TimeoutLRUCache(int capacity) { this(capacity, 300000); // 默认5分钟 } // 构造函数：指定容量和默认过期时间（毫秒） public TimeoutLRUCache(int capacity, long defaultTtl) { this.capacity = capacity; this.defaultTtl = defaultTtl; sentinel.prev = sentinel; sentinel.next = sentinel; } // 获取值，如果已过期则返回 -1 public int get(int key) { Node node = getNode(key); if (node == null || node.isExpired()) { if (node != null) { // 过期节点从缓存中移除 remove(node); keyToNode.remove(key); } return -1; } return node.value; } // 放入缓存，使用默认过期时间 public void put(int key, int value) { put(key, value, defaultTtl); } // 放入缓存，指定过期时间（毫秒） public void put(int key, int value, long ttlMillis) { Node node = getNode(key); if (node != null) { // 更新存在的节点 node.value = value; node.expireTime = System.currentTimeMillis() + ttlMillis; return; } // 创建新节点 long expireTime = System.currentTimeMillis() + ttlMillis; node = new Node(key, value, expireTime); keyToNode.put(key, node); pushFront(node); // 清理过期节点 + 容量控制 cleanExpiredNodes(); if (keyToNode.size() > capacity) { Node backNode = sentinel.prev; // 从后往前清理，优先清理过期节点 while (backNode != sentinel && keyToNode.size() > capacity) { if (backNode.isExpired()) { Node toRemove = backNode; backNode = backNode.prev; keyToNode.remove(toRemove.key); remove(toRemove); } else if (keyToNode.size() > capacity) { // 容量超限，移除最久未使用的节点 keyToNode.remove(backNode.key); remove(backNode); backNode = sentinel.prev; } } } } // 获取节点并移到头部 private Node getNode(int key) { if (!keyToNode.containsKey(key)) { return null; } Node node = keyToNode.get(key); // 如果节点已过期，返回null（让调用方处理） if (node.isExpired()) { return null; } remove(node); pushFront(node); return node; } // 清理所有过期节点 private void cleanExpiredNodes() { Node current = sentinel.prev; while (current != sentinel) { Node next = current.prev; if (current.isExpired()) { keyToNode.remove(current.key); remove(current); } current = next; } } // 从链表中移除节点 private void remove(Node x) { x.prev.next = x.next; x.next.prev = x.prev; } // 将节点插入链表头部 private void pushFront(Node x) { x.prev = sentinel; x.next = sentinel.next; x.prev.next = x; x.next.prev = x; } // 获取当前缓存大小（包含未过期节点） public int size() { cleanExpiredNodes(); return keyToNode.size(); } // 检查缓存是否包含某个key（未过期） public boolean containsKey(int key) { Node node = keyToNode.get(key); return node != null && !node.isExpired(); } } public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); TimeoutLRUCache cache = null; List<String> output = new ArrayList<>(); for (int i = 0; i < n; i++) { String op = scanner.next(); switch (op) { case "TimeoutLRUCache": int capacity = scanner.nextInt(); cache = new TimeoutLRUCache(capacity); output.add("null"); break; case "put": int key = scanner.nextInt(); int value = scanner.nextInt(); // 可选：读取过期时间，如果没有则使用默认值 long ttl = -1; if (scanner.hasNextInt()) { ttl = scanner.nextInt(); } if (ttl > 0) { cache.put(key, value, ttl); } else { cache.put(key, value); } output.add("null"); break; case "putWithTtl": int k = scanner.nextInt(); int v = scanner.nextInt(); long ttlMillis = scanner.nextLong(); cache.put(k, v, ttlMillis); output.add("null"); break; case "get": int getKey = scanner.nextInt(); int result = cache.get(getKey); output.add(String.valueOf(result)); break; case "size": output.add(String.valueOf(cache.size())); break; case "contains": int checkKey = scanner.nextInt(); output.add(String.valueOf(cache.containsKey(checkKey))); break; default: output.add("unknown"); } } // 输出结果 for (int i = 0; i < output.size(); i++) { System.out.print(output.get(i)); if (i < output.size() - 1) { System.out.print(" "); } } scanner.close(); } }