思路

本题的原题是力扣460题。

本题的目标是实现一个具有LFU（最近不常使用）策略的缓存系统。为此，我们设计了一个名为Node的数据结构，以及结合哈希表和红黑树（通过std::set）的复合数据结构来支持缓存操作。

数据结构定义

• Node 结构：每个Node包含以下字段：

  • cnt：表示节点被访问的次数。
  • time：表示节点最近一次被访问的时间。
  • key：节点的键，用于标识缓存项。
  • value：节点的值，即缓存项的数据内容。

  这个结构既用于哈希表中的值，也用于红黑树中的元素。

• 哈希表：使用std::unordered_map存储键和指向节点的指针，以实现快速查找。

• 平衡二叉树：使用std::set来维护一个按(cnt, time)排序的节点集合，确保可以快速访问和删除最少使用的缓存项。

核心操作

• 读取（Read）操作：

  • 检查键是否存在于哈希表中。
  • 如果存在，则更新节点的cnt和time，重新插入到红黑树中以保持排序。
  • 返回节点的值。

• 写入（Write）操作：

  • 如果键存在，更新其值及访问的元数据（cnt和time），并更新红黑树。
  • 如果键不存在，创建一个新的节点，加入哈希表和红黑树。
  • 如果缓存已满（即达到预设的最大容量），则先从红黑树中移除最少使用的缓存项，然后移除对应的哈希表条目。

• 查询（Query）操作：

  • 直接通过哈希表检查键是否存在，并返回相应的值或-1（不存在的标志）。

在这个实现中，我们通过组合哈希表和红黑树来维护LRU缓存，这不仅确保了操作的效率，也简化了最少使用元素的管理。这种策略适用于需要频繁读写且对性能要求较高的场景。

代码

Python

import collections
import time

# 定义一个名为 Node 的类，类似于C++中的结构体
class Node:
    def __init__(self, cnt, tim, key, value):
        self.cnt = cnt  # 计数器，用于记录某个键的访问次数
        self.tim = tim  # 时间戳，用于记录某个键最后一次被访问的时间
        self.key = key  # 键
        self.value = value  # 键对应的值

    # 定义小于操作符，用于比较两个 Node 对象
    def __lt__(self, other):
        # 如果计数器相同，按时间戳排序；否则按计数器排序
        if self.cnt == other.cnt:
            return self.tim < other.tim
        return self.cnt < other.cnt

# 定义全局变量
n = 0  # 缓存的容量
tim = 0  # 全局时间戳
mapp = {}  # 存储键和值的映射
S = set()  # 用于存储所有的 Node 对象

# 获取某个键对应的值
def get(key):
    global tim
    if n == 0 or key not in mapp:  # 如果缓存容量为0或键不在映射中，返回-1
        return -1
    cache = mapp[key]  # 获取对应的缓存节点
    S.remove(cache)  # 从集合中删除旧节点
    cache.cnt += 1  # 增加访问计数器
    tim += 1  # 更新全局时间戳
    cache.tim = tim  # 更新节点的时间戳
    S.add(cache)  # 将更新后的节点重新插入集合
    mapp[key] = cache  # 更新映射中的节点
    return cache.value  # 返回节点的值

# 插入或更新某个键值对
def put(key, value):
    global tim
    if n == 0:  # 如果缓存容量为0，直接返回
        return
    if key not in mapp:  # 如果键不在映射中
        if len(mapp) == n:  # 如果映射中的元素数量等于缓存容量
            oldest = min(S)  # 获取集合中最小的节点（即要被替换的节点）
            S.remove(oldest)  # 从集合中删除该节点
            del mapp[oldest.key]  # 从映射中删除该节点
        tim += 1  # 更新全局时间戳
        cache = Node(1, tim, key, value)  # 创建一个新的节点
        mapp[key] = cache  # 将节点插入映射
        S.add(cache)  # 将节点插入集合
    else:  # 如果键已经在映射中
        cache = mapp[key]  # 获取对应的缓存节点
        S.remove(cache)  # 从集合中删除旧节点
        cache.cnt += 1  # 增加访问计数器
        tim += 1  # 更新全局时间戳
        cache.tim = tim  # 更新节点的时间戳
        cache.value = value  # 更新节点的值
        S.add(cache)  # 将更新后的节点重新插入集合
        mapp[key] = cache  # 更新映射中的节点

# 主函数
if __name__ == "__main__":
    s = input()  # 读取操作类型
    n = int(input())  # 读取缓存容量
    while True:
        try:
            s = input()  # 读取操作类型
            if s[0] == 'w':  # 如果操作是写入
                m = int(input())  # 读取写入操作的数量
                for _ in range(m):  # 逐个读取并写入键值对
                    a, b = map(int, input().split())
                    put(a, b)
            elif s[0] == 'r':  # 如果操作是读取
                x = int(input())  # 读取要查询的键
                get(x)
            else:  # 如果操作是查询当前缓存的值
                x = int(input())  # 读取要查询的键
                if x in mapp:  # 如果键在映射中
                    print(mapp[x].value)  # 打印对应的值
                else:
                    print(-1)  # 如果键不在映射中，打印-1
        except EOFError:
            break  # 读取结束后，退出循环

C++

#include <bits/stdc++.h>

using namespace std;

struct Node {
    int cnt, tim, key, value;
    Node() {}
    Node(int a, int b, int c, int d):cnt(a), tim(b), key(c), value(d){}
    bool operator < (const Node& nod) const {
        return cnt == nod.cnt ? tim < nod.tim : cnt < nod.cnt;
    }
};
int n, tim;
unordered_map<int, Node> mapp;
set<Node> S;
int get(int key) {
    if (n == 0 || mapp.find(key) == mapp.end()) {
        return -1;
    }
    Node cache = mapp[key];
    S.erase(cache);
    cache.cnt += 1;
    cache.tim = ++tim;
    S.insert(cache);
    mapp[key] = cache;
    return cache.value;
}

void put(int key, int value) {
    if (n == 0) return;
    auto it = mapp.find(key);
    if (it == mapp.end()) {
        if (mapp.size() == n) {
            mapp.erase(S.begin()->key);
            S.erase(S.begin());
        }
        Node cache = Node(1, ++tim, key, value);
        mapp[key] = cache;
        S.insert(cache);
    } else {
        Node cache = it->second;
        S.erase(cache);
        cache.cnt += 1;
        cache.tim = ++tim;
        cache.value = value;
        S.insert(cache);
        it->second = cache;
    }
}

int main() {
    string s;cin >> s;
    cin >> n;
    int x;
    while (cin >> s) {
        if (s[0] == 'w') {
            int m;
            cin >> m;
            while (m --) {
                int a, b;
                cin >> a >> b;
                put(a, b);
            }
        } else if(s[0] == 'r') {
        	cin >> x;
            get(x);
        } else while (cin >> x) {
            if (mapp.count(x)) cout << mapp[x].value << endl;
            else cout << -1 << endl;
        }
    }
}

Java

import java.util.*;

class Node implements Comparable<Node> {
    int cnt, tim, key, value;

    Node(int cnt, int tim, int key, int value) {
        this.cnt = cnt;
        this.tim = tim;
        this.key = key;
        this.value = value;
    }

    @Override
    public int compareTo(Node nod) {
        return this.cnt == nod.cnt ? this.tim - nod.tim : this.cnt - nod.cnt;
    }
}

public class Main {
    static int n, tim;
    static Map<Integer, Node> mapp = new HashMap<>();
    static TreeSet<Node> S = new TreeSet<>();

    // 获取缓存值
    static int get(int key) {
        if (n == 0 || !mapp.containsKey(key)) {
            return -1;
        }
        Node cache = mapp.get(key);
        S.remove(cache);
        cache.cnt += 1;
        cache.tim = ++tim;
        S.add(cache);
        mapp.put(key, cache);
        return cache.value;
    }

    // 插入缓存值
    static void put(int key, int value) {
        if (n == 0) return;
        if (!mapp.containsKey(key)) {
            if (mapp.size() == n) {
                Node firstNode = S.first();
                mapp.remove(firstNode.key);
                S.remove(firstNode);
            }
            Node cache = new Node(1, ++tim, key, value);
            mapp.put(key, cache);
            S.add(cache);
        } else {
            Node cache = mapp.get(key);
            S.remove(cache);
            cache.cnt += 1;
            cache.tim = ++tim;
            cache.value = value;
            S.add(cache);
            mapp.put(key, cache);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.next();
        n = scanner.nextInt();

        while (scanner.hasNext()) {
            s = scanner.next();
            if (s.charAt(0) == 'w') {
                int m = scanner.nextInt();
                for (int i = 0; i < m; i++) {
                    int a = scanner.nextInt();
                    int b = scanner.nextInt();
                    put(a, b);
                }
            } else if (s.charAt(0) == 'r') {
                int x = scanner.nextInt();
                get(x);
            } else {
                while (scanner.hasNextInt()) {
                    int x = scanner.nextInt();
                    System.out.println(mapp.containsKey(x) ? mapp.get(x).value : -1);
                }
            }
        }
        scanner.close();
    }
}

javaScript

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

// LRU 缓存类
class LRUCache {
    constructor(capacity) {
        this.n = capacity;
        this.tim = 0;
        this.mapp = new Map();
        this.set = new Set();
    }

    // 获取缓存值
    get(key) {
        if (this.n === 0 || !this.mapp.has(key)) {
            return -1;
        }
        let cache = this.mapp.get(key);
        this.set.delete(cache);
        cache.cnt += 1;
        cache.tim = ++this.tim;
        this.set.add(cache);
        return cache.value;
    }

    // 插入缓存值
    put(key, value) {
        if (this.n === 0) return;
        if (!this.mapp.has(key)) {
            if (this.mapp.size === this.n) {
                let firstNode = [...this.set].sort((a, b) => a.cnt === b.cnt ? a.tim - b.tim : a.cnt - b.cnt)[0];
                this.mapp.delete(firstNode.key);
                this.set.delete(firstNode);
            }
            let cache = { cnt: 1, tim: ++this.tim, key, value };
            this.mapp.set(key, cache);
            this.set.add(cache);
        } else {
            let cache = this.mapp.get(key);
            this.set.delete(cache);
            cache.cnt += 1;
            cache.tim = ++this.tim;
            cache.value = value;
            this.set.add(cache);
            this.mapp.set(key, cache);
        }
    }
}

// 处理输入
(async function () {
    let cache;
    while (line = await readline()) {

        let parts = line.split(":");
        let command = parts[0].trim();

        if (command === "capacity") {
            cache = new LRUCache(parseInt(await readline()));
        } else if (command === "write") {
            let count = parseInt(await readline());
            for (let i = 0; i < count; i++) {
                let [key, value] = (await readline()).split(" ").map(Number);
                cache.put(key, value);
            }
        } else if (command === "read") {
            let key = parseInt(await readline());
            cache.get(key); // 这里仅用于更新 LRU 访问顺序
        } else if (command === "query") {
            let key = parseInt(await readline());
            console.log(cache.get(key));
        }
        else{
            break;
        }
    }

    rl.close();
})();

题目描述

$\qquad$这学期的小明的计网老师教学水平真是一言难尽，还要用ensp来做一些繁琐的模拟实验，但是计网实验跟写代码有什么关系呢？来不及为赶不完的DDL哀悼了，有一个实验描述如下：

$\qquad$无线通信移动性需要在基站上配置邻区(本端基站的小区LocalCell与周边邻基站的小区NeighborCelI映射)关系，为了能够加速无线算法的计算效率，设计一个邻区关系缓存表，用于快速的通过本小区LocalCell查询到邻小区NeighborCell。但是缓存表有一定的规格限制，因此到达规格并且需要插入新的数据时，需要删除邻区数据，选择删除邻区数据对象的策略为：

$\qquad$（1）使用次数最少的；

$\qquad$（2）如果（1）返回有多个对象,则选择最久未使用的。

$\qquad$请设计并实现一个满足以上要求的数据结构和算法实现。

$\qquad$注:假设每个LocalCell至多只有一个NeighborCell。

输入描述

$\qquad$ 1、首行以字符"capacity:"标识设置一个整数容量;

$\qquad$ 2、以"write:"标识开始进行若干组[LocalCell,NeighborCell]邻区数据的输入,每组数据为一行;如果"write:"已经存在的LocalCell数据,更新其对 应的NeighborCell,并刷新使用时间和次数加1;如果某邻区数据被删除,缓存表不再保留其记录;

$\qquad$ 3、以"read:"标识进行一次读取LocalCell的使用操作,刷新使用时间和次数加1;

$\qquad$ 4、最后以"query:"标识查询输出操作，输入正整数LocalCell，查询NeighborCell；

$\qquad$注:

$\qquad$$\qquad$（1）写入和读取都表示对LocalcelI的使用操作;

$\qquad$$\qquad$（2）capacity、LocalCellI和NeighborCelI都是正整数，范围在[1,10000];

$\qquad$$\qquad$（3）输入的总行数不超过30000行。

输出描述

$\qquad$每个查询输入正整数LocalCell对应NeighborCell，表示在邻区关系缓存表中的记录。

$\qquad$ 1、找到，则返回NeighborCell； $\qquad$ 2、没有找到，则返回-1;

样例一

输入

capacity:
3
write:
3
1 2
4 3
2 3
read:
2
write:
1
3 1
query:
1

输出

-1

解释

$\qquad$ 1、设定容量capacity为3

$\qquad$ 2、write输入3组数据，

$\qquad$ 3、read读取2使用,刷新该邻区对使用时间和次数;

$\qquad$ 4、再write输入1组数据,因为已经超了容量3,所以把最早输入且未使用的数据”12”剔除;

$\qquad$ 5、最后进行query查询1因为已经被剔除了,所以返回-1;

Limitation

1s, 1024KiB for each test case.