java 解法, 执行用时: 473 ms, 内存消耗: 150.7 MB, 提交时间: 2025-04-07 09:36:45

class Router {
    private Map<Integer, List<int[]>> routerMap = new HashMap<>();
    private List<int[]> routerList = new ArrayList<>();
    int limit;
    Set<String> routerSet = new HashSet<>();

    public Router(int memoryLimit) {
        this.limit = memoryLimit;
    }

    public boolean addPacket(int source, int destination, int timestamp) {
        int[] data = {source, destination, timestamp};
        String hash = hash(data);
        if (routerSet.contains(hash)) {
            return false;
        }
        if (routerList.size() == limit) {
            forwardPacket();
        }
        routerSet.add(hash);
        routerList.add(data);
        routerMap.computeIfAbsent(destination, k -> new ArrayList<>()).add(data);
        return true;
    }

    public int[] forwardPacket() {
        if (routerList.isEmpty()) {
            return new int[]{};
        }
        int[] data = routerList.remove(0);
        routerSet.remove(hash(data));
        List<int[]> mapData = routerMap.get(data[1]);
        mapData.remove(0);
        return data;
    }

    public int getCount(int destination, int startTime, int endTime) {
        List<int[]> dataList = routerMap.get(destination);
        if (startTime > endTime || dataList == null || dataList.isEmpty()) {
            return 0;
        }
        int l = binSearchLeft(dataList, startTime);
        int r = binSearchRight(dataList, endTime);
        if (l == -1 || r == -1) {
            return 0;
        }
        return Math.max(r - l + 1, 0);
    }

    private int binSearchLeft(List<int[]> dataList, int timestamp) {
        int l = 0, r = dataList.size() - 1, res = -1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            int t = dataList.get(mid)[2];
            if (timestamp <= t) {
                res = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return res;
    }

    private int binSearchRight(List<int[]> dataList, int timestamp) {
        int l = 0, r = dataList.size() - 1, res = -1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            int t = dataList.get(mid)[2];
            if (timestamp >= t) {
                res = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return res;
    }

    private String hash(int[] nums) {
        return String.format("%s-%s-%s", nums[0], nums[1], nums[2]);
    }
}

/**
 * Your Router object will be instantiated and called as such:
 * Router obj = new Router(memoryLimit);
 * boolean param_1 = obj.addPacket(source,destination,timestamp);
 * int[] param_2 = obj.forwardPacket();
 * int param_3 = obj.getCount(destination,startTime,endTime);
 */

cpp 解法, 执行用时: 243 ms, 内存消耗: 412.8 MB, 提交时间: 2025-04-07 09:35:26

class Router {
	int mxsize;
	queue<tuple<int, int, int>> q; //进出顺序
	set<tuple<int, int, int>> set; //去重
	unordered_map<int, vector<int> > map; //查询timestamp
public:
	Router(int memoryLimit) :mxsize(memoryLimit) {

	}

	bool addPacket(int source, int destination, int timestamp) {
		tuple<int, int, int> t(source, destination,timestamp);
		if (set.count(t)) {
			return false;
		}
		q.push(t);
		set.insert(t);
		map[destination].emplace_back(timestamp);
		if (q.size() > mxsize) { //大于最大size，直接调用forwardPacket出队一个元素
			forwardPacket();
		}
		return true;
	}
	vector<int> forwardPacket() {
		if (q.empty()) {
			return {};
		}
		auto t = q.front();
		set.erase(set.find(t));
		auto& pairs = map[get<1>(t)];
		auto p = ranges::lower_bound(pairs, get<2>(t));
		pairs.erase(p);
		q.pop();
		return { get<0>(t),get<1>(t), get<2>(t)};
	}
	int getCount(int destination, int startTime, int endTime) {
		auto& pairs = map[destination];

		auto s = ranges::lower_bound(pairs, startTime);
		auto e = ranges::upper_bound(pairs, endTime);
		return e - s;
	}
};

/**
 * Your Router object will be instantiated and called as such:
 * Router* obj = new Router(memoryLimit);
 * bool param_1 = obj->addPacket(source,destination,timestamp);
 * vector<int> param_2 = obj->forwardPacket();
 * int param_3 = obj->getCount(destination,startTime,endTime);
 */

python3 解法, 执行用时: 372 ms, 内存消耗: 105.9 MB, 提交时间: 2025-04-07 09:34:05

from bisect import bisect_left, bisect_right
from collections import deque, defaultdict
from typing import List


class Router:

    def __init__(self, memoryLimit: int):
        self.memoryLimit = memoryLimit
        self.sl = deque()
        self.record_destination = defaultdict(deque)
        self.vis = set()

    def addPacket(self, source: int, destination: int, timestamp: int) -> bool:
        comb = (timestamp, source, destination)
        if comb in self.vis:
            return False
        self.vis.add(comb)
        if len(self.sl) == self.memoryLimit:
            self.forwardPacket()
        self.sl.append(comb)
        self.record_destination[destination].append(timestamp)
        return True

    def forwardPacket(self) -> List[int]:
        if not self.sl:
            return []
        timestamp, source, destination = self.sl.popleft()
        self.record_destination[destination].popleft()
        self.vis.remove((timestamp, source, destination))
        return [source, destination, timestamp]

    def getCount(self, destination: int, startTime: int, endTime: int) -> int:
        nums = self.record_destination[destination]
        left = bisect_left(nums, startTime)  # nums[left] >= startTime
        right = bisect_right(nums, endTime) - 1  # nums[right] <= endTime
        return right - left + 1

# Your Router object will be instantiated and called as such:
# obj = Router(memoryLimit)
# param_1 = obj.addPacket(source,destination,timestamp)
# param_2 = obj.forwardPacket()
# param_3 = obj.getCount(destination,startTime,endTime)
# ©leetcode

python3 解法, 执行用时: 444 ms, 内存消耗: 102.7 MB, 提交时间: 2025-04-07 09:33:34

from sortedcontainers import SortedList
mx = int(1e9)
class Router:

    def __init__(self, memoryLimit: int):
        # 双端队列，FIFO
        self.que = deque()

        # keyw为 destination  的时间有序集合，用于查找时间范围内的包数目
        self.dt = defaultdict(lambda :SortedList())
        self.n = memoryLimit

        self.A = set()

    def addPacket(self, source: int, destination: int, timestamp: int) -> bool:
        key = (source,destination,timestamp)
        if key in self.A:
            return False
        self.que.append(key)
        self.A.add(key)
        self.dt[destination].add((timestamp,source))
        if len(self.que) > self.n:
            a,b,c = self.que.popleft()
            self.A.remove((a,b,c))
            idx = self.dt[b].bisect_left((c,a))
            del self.dt[b][idx]

        return True
            
        

    def forwardPacket(self) -> List[int]:
        if not self.que:
            return []

        res = self.que.popleft()
        source,destination,timestamp = res
        idx = self.dt[destination].bisect_left((timestamp,source))
        
        del self.dt[destination][idx]
        self.A.remove(res)
        return res
        
        

    def getCount(self, destination: int, startTime: int, endTime: int) -> int:
        sl = self.dt[destination]
        return sl.bisect_right((endTime,mx)) - sl.bisect_right((startTime-1,mx))
        


# Your Router object will be instantiated and called as such:
# obj = Router(memoryLimit)
# param_1 = obj.addPacket(source,destination,timestamp)
# param_2 = obj.forwardPacket()
# param_3 = obj.getCount(destination,startTime,endTime)