标签： 设计

1912.设计电影租借系统

目标

你有一个电影租借公司和 n 个电影商店。你想要实现一个电影租借系统，它支持查询、预订和返还电影的操作。同时系统还能生成一份当前被借出电影的报告。

所有电影用二维整数数组 entries 表示，其中 entries[i] = [shopi, moviei, pricei] 表示商店 shopi 有一份电影 moviei 的拷贝，租借价格为 pricei 。每个商店有 至多一份 编号为 moviei 的电影拷贝。

系统需要支持以下操作：

  • Search：找到拥有指定电影且 未借出 的商店中 最便宜的 5 个 。商店需要按照 价格 升序排序，如果价格相同，则 shopi 较小 的商店排在前面。如果查询结果少于 5 个商店，则将它们全部返回。如果查询结果没有任何商店，则返回空列表。
  • Rent：从指定商店借出指定电影，题目保证指定电影在指定商店 未借出 。
  • Drop：在指定商店返还 之前已借出 的指定电影。
  • Report：返回 最便宜的 5 部已借出电影 （可能有重复的电影 ID），将结果用二维列表 res 返回，其中 res[j] = [shopj, moviej] 表示第 j 便宜的已借出电影是从商店 shopj 借出的电影 moviej 。res 中的电影需要按 价格 升序排序；如果价格相同，则 shopj 较小 的排在前面；如果仍然相同，则 moviej 较小 的排在前面。如果当前借出的电影小于 5 部，则将它们全部返回。如果当前没有借出电影，则返回一个空的列表。

请你实现 MovieRentingSystem 类：

  • MovieRentingSystem(int n, int[][] entries) 将 MovieRentingSystem 对象用 n 个商店和 entries 表示的电影列表初始化。
  • List<Integer> search(int movie) 如上所述，返回 未借出 指定 movie 的商店列表。
  • void rent(int shop, int movie) 从指定商店 shop 借出指定电影 movie 。
  • void drop(int shop, int movie) 在指定商店 shop 返还之前借出的电影 movie 。
  • List<List<Integer>> report() 如上所述，返回最便宜的 已借出 电影列表。

注意：测试数据保证 rent 操作中指定商店拥有 未借出 的指定电影，且 drop 操作指定的商店 之前已借出 指定电影。

示例 1：

输入：
["MovieRentingSystem", "search", "rent", "rent", "report", "drop", "search"]
[[3, [[0, 1, 5], [0, 2, 6], [0, 3, 7], [1, 1, 4], [1, 2, 7], [2, 1, 5]]], [1], [0, 1], [1, 2], [], [1, 2], [2]]
输出：
[null, [1, 0, 2], null, null, [[0, 1], [1, 2]], null, [0, 1]]

解释：
MovieRentingSystem movieRentingSystem = new MovieRentingSystem(3, [[0, 1, 5], [0, 2, 6], [0, 3, 7], [1, 1, 4], [1, 2, 7], [2, 1, 5]]);
movieRentingSystem.search(1);  // 返回 [1, 0, 2] ，商店 1，0 和 2 有未借出的 ID 为 1 的电影。商店 1 最便宜，商店 0 和 2 价格相同，所以按商店编号排序。
movieRentingSystem.rent(0, 1); // 从商店 0 借出电影 1 。现在商店 0 未借出电影编号为 [2,3] 。
movieRentingSystem.rent(1, 2); // 从商店 1 借出电影 2 。现在商店 1 未借出的电影编号为 [1] 。
movieRentingSystem.report();   // 返回 [[0, 1], [1, 2]] 。商店 0 借出的电影 1 最便宜，然后是商店 1 借出的电影 2 。
movieRentingSystem.drop(1, 2); // 在商店 1 返还电影 2 。现在商店 1 未借出的电影编号为 [1,2] 。
movieRentingSystem.search(2);  // 返回 [0, 1] 。商店 0 和 1 有未借出的 ID 为 2 的电影。商店 0 最便宜，然后是商店 1 。

说明：

  • 1 <= n <= 3 * 10^5
  • 1 <= entries.length <= 10^5
  • 0 <= shopi < n
  • 1 <= moviei, pricei <= 10^4
  • 每个商店 至多 有一份电影 moviei 的拷贝。
  • search，rent，drop 和 report 的调用 总共 不超过 10^5 次。

思路

代码

性能

3508.设计路由器

目标

请你设计一个数据结构来高效管理网络路由器中的数据包。每个数据包包含以下属性：

  • source：生成该数据包的机器的唯一标识符。
  • destination：目标机器的唯一标识符。
  • timestamp：该数据包到达路由器的时间戳。

实现 Router 类：

Router(int memoryLimit)：初始化路由器对象，并设置固定的内存限制。

  • memoryLimit 是路由器在任意时间点可以存储的 最大 数据包数量。
  • 如果添加一个新数据包会超过这个限制，则必须移除 最旧的 数据包以腾出空间。

bool addPacket(int source, int destination, int timestamp)：将具有给定属性的数据包添加到路由器。

  • 如果路由器中已经存在一个具有相同 source、destination 和 timestamp 的数据包，则视为重复数据包。
  • 如果数据包成功添加（即不是重复数据包），返回 true；否则返回 false。

int[] forwardPacket()：以 FIFO（先进先出）顺序转发下一个数据包。

  • 从存储中移除该数据包。
  • 以数组 [source, destination, timestamp] 的形式返回该数据包。
  • 如果没有数据包可以转发，则返回空数组。

int getCount(int destination, int startTime, int endTime)：

  • 返回当前存储在路由器中（即尚未转发）的，且目标地址为指定 destination 且时间戳在范围 [startTime, endTime]（包括两端）内的数据包数量。

注意：对于 addPacket 的查询会按照 timestamp 的递增顺序进行。

示例 1：

输入：
["Router", "addPacket", "addPacket", "addPacket", "addPacket", "addPacket", "forwardPacket", "addPacket", "getCount"]
[[3], [1, 4, 90], [2, 5, 90], [1, 4, 90], [3, 5, 95], [4, 5, 105], [], [5, 2, 110], [5, 100, 110]]
输出：
[null, true, true, false, true, true, [2, 5, 90], true, 1]
解释：
Router router = new Router(3); // 初始化路由器，内存限制为 3。
router.addPacket(1, 4, 90); // 数据包被添加，返回 True。
router.addPacket(2, 5, 90); // 数据包被添加，返回 True。
router.addPacket(1, 4, 90); // 这是一个重复数据包，返回 False。
router.addPacket(3, 5, 95); // 数据包被添加，返回 True。
router.addPacket(4, 5, 105); // 数据包被添加，[1, 4, 90] 被移除，因为数据包数量超过限制，返回 True。
router.forwardPacket(); // 转发数据包 [2, 5, 90] 并将其从路由器中移除。
router.addPacket(5, 2, 110); // 数据包被添加，返回 True。
router.getCount(5, 100, 110); // 唯一目标地址为 5 且时间在 [100, 110] 范围内的数据包是 [4, 5, 105]，返回 1。

示例 2：

输入：
["Router", "addPacket", "forwardPacket", "forwardPacket"]
[[2], [7, 4, 90], [], []]
输出：
[null, true, [7, 4, 90], []]
解释：
Router router = new Router(2); // 初始化路由器，内存限制为 2。
router.addPacket(7, 4, 90); // 返回 True。
router.forwardPacket(); // 返回 [7, 4, 90]。
router.forwardPacket(); // 没有数据包可以转发，返回 []。

说明：

  • 2 <= memoryLimit <= 10^5
  • 1 <= source, destination <= 2 * 10^5
  • 1 <= timestamp <= 10^9
  • 1 <= startTime <= endTime <= 10^9
  • addPacket、forwardPacket 和 getCount 方法的总调用次数最多为 10^5。
  • 对于 addPacket 的查询，timestamp 按递增顺序给出。

思路

//todo

代码

性能

1865.找出和为指定值的下标对

目标

给你两个整数数组 nums1 和 nums2 ，请你实现一个支持下述两类查询的数据结构：

  1. 累加 ，将一个正整数加到 nums2 中指定下标对应元素上。
  2. 计数 ，统计满足 nums1[i] + nums2[j] 等于指定值的下标对 (i, j) 数目（0 <= i < nums1.length 且 0 <= j < nums2.length）。

实现 FindSumPairs 类：

  • FindSumPairs(int[] nums1, int[] nums2) 使用整数数组 nums1 和 nums2 初始化 FindSumPairs 对象。
  • void add(int index, int val) 将 val 加到 nums2[index] 上，即，执行 nums2[index] += val 。
  • int count(int tot) 返回满足 nums1[i] + nums2[j] == tot 的下标对 (i, j) 数目。

示例：

输入：
["FindSumPairs", "count", "add", "count", "count", "add", "add", "count"]
[[[1, 1, 2, 2, 2, 3], [1, 4, 5, 2, 5, 4]], [7], [3, 2], [8], [4], [0, 1], [1, 1], [7]]
输出：
[null, 8, null, 2, 1, null, null, 11]
解释：
FindSumPairs findSumPairs = new FindSumPairs([1, 1, 2, 2, 2, 3], [1, 4, 5, 2, 5, 4]);
findSumPairs.count(7);  // 返回 8 ; 下标对 (2,2), (3,2), (4,2), (2,4), (3,4), (4,4) 满足 2 + 5 = 7 ，下标对 (5,1), (5,5) 满足 3 + 4 = 7
findSumPairs.add(3, 2); // 此时 nums2 = [1,4,5,4,5,4]
findSumPairs.count(8);  // 返回 2 ；下标对 (5,2), (5,4) 满足 3 + 5 = 8
findSumPairs.count(4);  // 返回 1 ；下标对 (5,0) 满足 3 + 1 = 4
findSumPairs.add(0, 1); // 此时 nums2 = [2,4,5,4,5,4]
findSumPairs.add(1, 1); // 此时 nums2 = [2,5,5,4,5,4]
findSumPairs.count(7);  // 返回 11 ；下标对 (2,1), (2,2), (2,4), (3,1), (3,2), (3,4), (4,1), (4,2), (4,4) 满足 2 + 5 = 7 ，下标对 (5,3), (5,5) 满足 3 + 4 = 7

说明：

  • 1 <= nums1.length <= 1000
  • 1 <= nums2.length <= 10^5
  • 1 <= nums1[i] <= 10^9
  • 1 <= nums2[i] <= 10^5
  • 0 <= index < nums2.length
  • 1 <= val <= 10^5
  • 1 <= tot <= 10^9
  • 最多调用 add 和 count 函数各 1000 次

思路

统计元素出现次数，针对每一个 count 操作，遍历 cnt1，累加 cnt1.get(x) * cnt2.get(tot - x) 即可。

代码


/**
 * @date 2025-07-06 16:48
 */
public class FindSumPairs1865 {

    class FindSumPairs {

        int[] nums1;
        int[] nums2;
        Map<Integer, Integer> cnt1 = new HashMap<>();
        Map<Integer, Integer> cnt2 = new HashMap<>();

        public FindSumPairs(int[] nums1, int[] nums2) {
            this.nums1 = nums1;
            this.nums2 = nums2;
            for (int num : nums1) {
                cnt1.merge(num, 1, Integer::sum);
            }
            for (int num : nums2) {
                cnt2.merge(num, 1, Integer::sum);

            }
        }

        public void add(int index, int val) {
            int key = nums2[index];
            cnt2.merge(key, -1, Integer::sum);
            if (cnt2.get(key) <= 0) {
                cnt2.remove(key);
            }
            nums2[index] += val;
            cnt2.merge(key + val, 1, Integer::sum);
        }

        public int count(int tot) {
            int res = 0;
            for (Map.Entry<Integer, Integer> entry : cnt1.entrySet()) {
                int key = entry.getKey();
                int value = entry.getValue();
                res += value * cnt2.getOrDefault(tot - key, 0);
            }
            return res;
        }
    }
}

性能