题目大意

这道题目要求我们模拟一个DNS本地缓存系统

思路

1.缓存容量：缓存最多能存储N条记录。

2.URL请求处理： 每秒处理一个URL请求。 如果请求的URL已经存在于缓存中，直接返回from_cache（输出0）。 如果请求的URL不在缓存中，返回from_internet（输出1），并将该URL加入缓存。

3.TTL管理： 每个URL在缓存中都有一个TTL（Time To Live）值，表示其在缓存中的存活时间。 每秒钟，缓存中所有URL的TTL值减1。当TTL值减为0时，该URL从缓存中移除。 如果加入缓存的新URL没有指定TTL，默认TTL值为5秒。 如果有指定TTL，则使用指定的TTL值。

4.缓存替换策略： 当缓存已满且需要加入新的URL时，移除TTL值最小的URL。 如果有多个URL的TTL值相同，则按照先进先出的原则移除最早加入的URL。

类似题目推荐

LeetCode

1.239. 滑动窗口最大值 - 优先队列入门

2.264. 丑数 II

3.621. 任务调度器

4.857. 雇佣 K 名工人的最低成本

CodeFun2000

1.P1211 塔子大厂真题模拟赛-第一题-魔法石(Ⅰ)

2.P1057 华为od 2022.11.17-分奖金

3.P1052 华东师范大学保研机试-2022-乘法

代码

CPP

#include <bits/stdc++.h>
using namespace std;
const int N = 65536;
struct Node		//维护一个URL的信息
{
	int edt, stt, id;		//edt代表生存周期结束时间，stt代表开始时间
	bool operator<(const Node& b) const		//为了使用优先队列存储要重载运算符<
	{	//优先队列应该要将待删除的数放在队列顶，而优先队列默认为大堆顶，所以要将优先删除的 TTL最小的，即结束时间最小的定为最"大"的值，相等时按先进先出原则，按开始时间排序。
		if(edt == b.edt) return stt > b.stt;
		return edt > b.edt;
	}
};
priority_queue<Node> que;	//优先队列定义
int n, x, y;
int q[N];			//询问数组
int ttls[N];		//每个URL的ttl
bool f[N];			//记录当前队列中有没有某个URL
int main()
{
	cin >> n >> x;
	for(int i = 1 ; i <= x ; i ++) {		//输入待处理的YLRL
		cin >> q[i];
	}
	for(int &t:ttls) {	//将所有的ttl初始化为5
		t = 5;
	}
	cin >> y;
	while(y--) {		//循环y次
		int url, ttl;
		cin >> url >> ttl;
		ttls[url] = ttl;		//更新这些URL的ttl
	}
	for(int i = 1 ; i <= x ; i++) {
		while(que.size() && que.top().edt <= i) {		//删除所有结束时间在i之前的本地缓存
			f[que.top().id] = 0;
			que.pop();
		}
		if(f[q[i]]) {		//如果本地缓存中有输出0
			cout << 0 << " \n"[i==x];
		} else {
			cout << 1 << " \n"[i==x];	//没有则输出1，然后添加到本地缓存中
			if(que.size() == n) {		//如果满了删除队列顶一个元素
				f[que.top().id] = 0;
				que.pop();
			}
			f[q[i]] = 1;
			que.push({i+ttls[q[i]], i, q[i]});//将当前的URL放入队列
		}
	}
}

python

import copy
from queue import PriorityQueue

N, X = map(int, input().strip().split()) # 输入 DNS 缓存上限和 TTL 上限
askurls = list(map(int, input().strip().split())) # 多次 DNS 查询的 URL 序列 
urltmap = {} 
Y = int(input().strip())
for i in range(Y):
    url, ttl = map(int, input().strip().split()) # 输入 DNS 地址以及相应的生存周期 TTL
    urltmap[url] = ttl # 将 URL 和 TTL 存储在字典 urltmap 中
ans = ""
fn = [False] * 65536 # 初始化布尔数组 fn，用于判断某个 URL 是否已经被缓存
pq = PriorityQueue() # 初始化优先队列 pq，用于维护本地 DNS 缓存
for i in range(len(askurls)):
    while not pq.empty() and pq.queue[0][0] <= i:
        # 找到优先队列中已过期的生存周期的 URL，进行删除处理
        cur = pq.get() 
        fn[cur[2]] = False 
    # 如果当前 URL 已经被缓存，则将结果字符串连接 "0 "
    if fn[askurls[i]]: 
        ans += "0 "
    else: # 否则当前 URL 还未被缓存，则将结果字符串连接 "1 "
        ans += "1 "
        if len(pq.queue) >= N: # 如果已缓存的 URL 数量达到 DNS 缓存上限 N，则进行删除处理
            cur = pq.get() # 取出优先级最高的 URL，进行删除处理
            fn[cur[2]] = False # 将被删除的 URL 对应的缓存状态设置为 False
        pq.put((i+urltmap.get(askurls[i], 5), i, askurls[i])) # 将当前 URL 存储在优先队列中，并根据 TTL 计算其生存周期结束时间
        fn[askurls[i]] = True # 将当前 URL 对应的缓存状态设置为 True，表示已被缓存
print(ans[:-1]) # 输出结果字符串

Java

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int n= scanner.nextInt(),x= scanner.nextInt();
        int[] url=new int[x];
        int max=0;
        for (int i = 0; i < x; i++) {
            url[i]= scanner.nextInt();
        }
        int y= scanner.nextInt();
        Map<Integer,Integer> map=new HashMap<>();
        for(int i=0;i<y;i++){
            map.put(scanner.nextInt(),scanner.nextInt());
        }
        PriorityQueue<int[]> pq=new PriorityQueue<>((o1, o2) -> o1[1]==o2[1]?o1[0]-o2[0]:o1[1]-o2[1]);
        Map<Integer,int[]> cache=new HashMap<>();
        int[] ans=new int[x];
        for(int i=0;i<x;i++){
            //先删除持续时间结束的
            while(pq.size()>0&&pq.peek()[1]<=i){
                    int[] rem=pq.poll();
                    cache.remove(rem[2]);
                }
            if(cache.containsKey(url[i])){
                ans[i]=0;
            }else {
                ans[i]=1;
                //如果优先队列的第一个元素的结束时间小于当前时间
                if(pq.size()==n){
                    int[] rem=pq.poll();
                    cache.remove(rem[2]);
                }
                //开始时间 结束时间 url
                int[] add=new int[]{i,i+map.getOrDefault(url[i],5),url[i]};
                pq.offer(add);
                cache.put(url[i],add);
            }
        }
        for(int i=0;i<x;i++){
            System.out.print(ans[i]+" ");
        }
    }
}
// by 月与海

Go

package main

import (
	"fmt"
)

const N = 70000

var n, x, y, idx int
var urls, tls map[int]int //urls: key url,value ttl
var q, ans, seq []int     //seq记录url进入的时机

func getMin() int {
	//选择缓存中ttl最小的删除
	var res int = -1
	minTtl := N
	for url, ttl := range urls {
		if ttl < minTtl {
			minTtl = ttl
			res = url
		} else if ttl == minTtl {
			if seq[url] < seq[res] {
				res = url
			}
		}
	}
	return res
}

func main() {
	//初始化所有slice和map
	q = make([]int, N)
	ans = make([]int, N)
	seq = make([]int, N)
	urls, tls = make(map[int]int), make(map[int]int)
	fmt.Scan(&n, &x)
	for i := 0; i < x; i++ {
		fmt.Scan(&q[i])
	}
	fmt.Scan(&y)
	for i := 0; i < y; i++ {
		//初始化urls序列
		var url, ttl int
		fmt.Scan(&url, &ttl)
		tls[url] = ttl
	}
	//每1秒输入一个URL地址 那么x有个暗含的意思就是处理时间
	for i := 0; i < x; i++ {
		//先从本地DNS上查找，如果本地缓存中能查到就直接返回from_cache -> 0
		if _, ok := urls[q[i]]; ok {
			ans[i] = 0
		} else {
			//本地缓存中查不到 -> from_internet 1
			ans[i] = 1
			//将这条url加入 urls中 先判断有没有装满 如果装满了就ttl最小的移除 如果ttl一样 就将入队时间早的移除
			if len(urls) == n {
				delete(urls, getMin())
			}
			//将url 放入urls 从URL的属性列表tls上，读取该URL的TTL 并将URL存入缓存系统中;如果在ts上未能读到该URL的TTL,设置默认TTL为5s;
			if _, ok := tls[q[i]]; ok {
				urls[q[i]] = tls[q[i]]
			} else {
				urls[q[i]] = 5
			}
			seq[q[i]] = idx
			idx++
		}
		//一秒结束了 URL地址的TTL每秒减1，当TTL=0时，将该URL地址从缓存系统中移除;
		for url := range urls {
			urls[url]--
			if urls[url] == 0 {
				delete(urls, url)
			}
		}
	}
	for i := 0; i < x; i++ {
		fmt.Printf("%d", ans[i])
		if i != x-1 {
			fmt.Printf(" ")
		}
	}
}
// by xchen

Js

// 设置 stdin 接收输入数据
process.stdin.resume();
process.stdin.setEncoding('utf-8');
let input = '';
process.stdin.on('data', (data) => {
  input += data;
  return;
});

process.stdin.on('end', () => {
  // input 数组以字符串形式存储了所有输入内容。input[i] 存储第i行的所有内容.
  input = input.split('\n');

  // 获取输入参数
  const param0 = input[0].split(' ')
  const N = Number(param0[0]) // 缓存容量
  const X = Number(param0[1]) // 请求个数

  const urlList = new Array() // url 请求列表
  const param1 = input[1].split(' ')
  for (let m = 0; m < X; m++) {
    urlList.push(Number(param1[m]))
  }

  const Y = Number(input[2]) 
  const tls = new Map() 
  for (let i = 0; i < Y; i++) {
    let tmp = input[3+i].split(' ')
    tls.set(Number(tmp[0]), Number(tmp[1]))
  }

  const cache = new Array() // 缓存
  const set = new Set() // 缓存中 url 集合

  // 添加 url 到缓存
  function add(url){
    if(cache.length < N){
      cache.push([url, tls.get(url) || 5])
      set.add(url)
    } else {
      if(set.has(url)){
        // 当前 url 已经存在于缓存中，不需要进行任何操作
      } else {
        // 缓存已满，删除缓存中生命周期最短的 url ，并将新的 url 添加到缓存中
        cache.sort((a, b) => a[1]-b[1])
        set.delete(cache[0][0])
        cache.shift()
        cache.push([url, tls.get(url) || 5])
        set.add(url)
      }
    }
  }

  // 更新缓存中 url 的 TTL
  function TTL() {
    for(let i = 0; i < cache.length; i++){
      cache[i][1] -= 1
      let urlTTL = cache[i][1]
      if(urlTTL === 0){
        set.delete(cache[i][0])
        cache.splice(i,1)
        i--
      }
    }
  }

  let result = new Array()
  for (let i = 0; i < X; i++) {
    // 更新缓存中 url 的 TTL
    TTL()
    if(set.has(urlList[i])){
      // url 存在于缓存中
      result.push('0')
    }else{
      // url 不存在于缓存中，将其添加至缓存中
      result.push('1')
      add(urlList[i])
    }
  }

  let ans = ''
  for(let i = 0; i < result.length - 1; i++){
    ans += result[i] + ' '
  }
  ans += result[result.length-1]
  console.log(ans)
})