3508. Implement Router

Leetcode link

题目简介

本题要求我们实现一个基于 FIFO 的网络路由，并实现一下功能

• Route：构造函数，接受一个 memoryLimit 参数来表示能够缓存的网络包，如果超过会把最先缓存的包丢弃
• addPacket：添加缓存包，接受 source, destination, timestamp 三个参数，分别代表数据来源、数据目的地、到达路由的时间戳；如果当前添加的缓存包数量超过了 memoryLimit，需要把最先进入路由的包丢弃；如果到达的包与当前缓存的包一致（冗余），需要丢弃到达的包并返回 false，否则返回 true
• forwardPacket：转发包，将最先进入路由的包转发出去，如果当前缓存为空，则返回空数组
• getCount：接受 destination, startTime, endTime 三个参数，表示从当前缓存中寻找目的地为 destination 且到达时间戳在 [startTime, endTime] 的包数量

解题思路

本题主要考察的是二分搜索，难点在于要如何快速的从同样的 destination 中找出符合时间范围的包数量

为了满足题意，我们需要以下数据结构：

• packets：缓存队列，满足 FIFO 诉求
• destToTime：由目的地到所有该目的地的数据包到达时间戳的映射（destination => [time1, time2, time3, ...]）
• packetKeySet：标识当前数据包的唯一标识符，用 "source#destination#timestamp" 构成

Javascript

/**
 * @param {number} memoryLimit
 */
var Router = function (memoryLimit) {
    this.sizeLimit = memoryLimit
    this.packets = []
    // map destination to timeStamp array
    this.destToTime = new Map()
    // use "source#destination#timestamp" as key
    this.packetKeySet = new Set()
};

/** 
 * @param {number} source 
 * @param {number} destination 
 * @param {number} timestamp
 * @return {boolean}
 */
Router.prototype.addPacket = function (source, destination, timestamp) {
    const key = makeKey(source, destination, timestamp)
    if (this.packetKeySet.has(key)) {
        return false
    }
    this.packetKeySet.add(key)

    if (this.packets.length >= this.sizeLimit) {
        this.forwardPacket()
    }
    this.packets.push([source, destination, timestamp])

    if (!this.destToTime.has(destination)) {
        this.destToTime.set(destination, [])
    }
    this.destToTime.get(destination).push(timestamp)

    return true
};

/**
 * @return {number[]}
 */
Router.prototype.forwardPacket = function () {
    if (this.packets.length === 0) {
        return []
    }
    const [source, destination, timestamp] = this.packets.shift()
    const key = makeKey(source, destination, timestamp)
    this.packetKeySet.delete(key)
    this.destToTime.get(destination).shift()
    return [source, destination, timestamp]
};

/** 
 * @param {number} destination 
 * @param {number} startTime 
 * @param {number} endTime
 * @return {number}
 */
Router.prototype.getCount = function (destination, startTime, endTime) {
    if (!this.destToTime.has(destination)) {
        return 0
    }
    const timeArr = this.destToTime.get(destination)
    const upperIdx = upperBound(timeArr, endTime)
    const lowerIdx = lowerBound(timeArr, startTime)

    return upperIdx - lowerIdx - 1
};

const makeKey = (source, destination, timestamp) => {
    return `${source}#${destination}#${timestamp}`
}

const upperBound = (arr, target) => {
    let left = 0
    let right = arr.length - 1
    let bound = arr.length

    while (left <= right) {
        let mid = Math.floor((left + right) / 2)
        if (arr[mid] <= target) {
            left = mid + 1
        } else {
            bound = mid
            right = mid - 1
        }
    }
    return bound
}

const lowerBound = (arr, target) => {
    let left = 0
    let right = arr.length - 1
    let bound = -1
    while (left <= right) {
        let mid = Math.floor((left + right) / 2)
        if (arr[mid] < target) {
            bound = mid
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return bound
}