LeetCode Contest 444

欢迎大家加QQ群：623375442。这次第二题就挺难的，后面2题又是hard。勉强AK

100631. Implement Router

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

• 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 的递增顺序进行。

测试样例：

输入：["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。

解答：维护一个哈希集合判断重复包，一个双端队列实现 FIFO，一个 TreeMap<Packet,Integer> 记录每个 destination 的前缀计数，支持区间计数查询。当队列超出内存时，移除最旧包并同步更新映射。

// 定义 Router 类，用于管理路由器中的数据包
class Router {
    // 用于判断数据包是否重复
    private HashSet<Package> set;
    // 针对每个 destination 保存一个 TreeMap，用于按顺序统计数据包数量
    private HashMap<Integer, TreeMap<Package, Integer>> destMap;
    // 记录每个 destination 当前数据包数量
    private HashMap<Integer, Integer> destCount;
    // 队列保存数据包，实现 FIFO 转发
    private Queue<Package> queue;
    // 内存限制：当前能存储的数据包数量上限
    private int memoryLimit;
    // offset 用于为每个数据包生成一个唯一偏移量，保证顺序性
    private int offset;
    // 空数组，方便在无数据包时返回
    private static final int[] empty = {};

    // 构造函数：初始化各个数据结构
    public Router(int memoryLimit) {
        this.memoryLimit = memoryLimit;
        this.offset = 0;
        queue = new LinkedList<>();
        set = new HashSet<>();
        destMap = new HashMap<>();
        destCount = new HashMap<>();
    }

    // 添加数据包，返回 true 表示添加成功；若是重复数据包则返回 false
    public boolean addPacket(int source, int destination, int timestamp) {
        // 构造数据包对象，并赋予当前 offset 后自增
        Package pac = new Package(source, destination, timestamp, offset++);
        // 如果数据包不存在，才进行添加
        if (!set.contains(pac)) {
            set.add(pac);
            queue.add(pac);

            // 更新目标地址 destination 对应的数量统计
            destCount.put(destination, destCount.getOrDefault(destination, 0) + 1);
            // 如果该 destination 不存在，则创建一个新的 TreeMap
            if (!destMap.containsKey(destination)) {
                destMap.put(destination, new TreeMap<>());
            }
            // 将数据包及其当前累计数量存入 TreeMap
            destMap.get(destination).put(pac, destCount.get(destination));

            // 如果队列大小超过内存限制，则移除最旧的数据包
            if (queue.size() > memoryLimit) {
                poll();
            }
            return true;
        } else {
            return false;
        }
    }

    // 按 FIFO 顺序转发数据包
    public int[] forwardPacket() {
        // 如果队列为空，返回空数组
        if (queue.isEmpty()) {
            return empty;
        } else {
            // 移除最旧的数据包
            Package pac = poll();
            // 同时从 HashSet 中移除该数据包
            set.remove(pac);
            // 返回数据包的属性数组
            return new int[]{pac.source, pac.destination, pac.timestamp};
        }
    }

    // 查询当前存储中满足 destination 和 [startTime, endTime] 时间范围的数据包数量
    public int getCount(int destination, int startTime, int endTime) {
        if (destMap.containsKey(destination)) {
            // 获取目标 destination 的 TreeMap
            TreeMap<Package, Integer> tmp = destMap.get(destination);
            // 构造左右边界数据包对象（注意 offset 的取值保证边界条件）
            Package left = new Package(-1, -1, startTime, 0);
            Package right = new Package(-1, -1, endTime, Integer.MAX_VALUE);
            // 找到左边界之前的最后一个数据包的计数
            Map.Entry<Package, Integer> lg = tmp.lowerEntry(left);
            // 找到右边界之前的最后一个数据包的计数
            Map.Entry<Package, Integer> rg = tmp.lowerEntry(right);
            // 如果没有找到满足右边界的 entry，则返回 0
            if (rg == null) {
                return 0;
            } else if (lg == null) {
                // 如果左边界之前没有 entry，则返回从第一个数据包到右边界的数量
                return rg.getValue() - tmp.firstEntry().getValue() + 1;
            } else {
                // 否则返回右边界计数减去左边界计数
                return rg.getValue() - lg.getValue();
            }
        }
        return 0;
    }

    // 辅助方法：移除最旧的数据包
    private Package poll() {
        Package pac = queue.poll();
        // 同时从 HashSet 中移除，确保一致性
        set.remove(pac);
        // 从对应 destination 的 TreeMap 中移除最旧数据包记录
        destMap.get(pac.destination).pollFirstEntry();
        return pac;
    }
}

// 定义数据包 Package 类，实现 Comparable 接口，用于排序
class Package implements Comparable<Package>  {
    int source, destination, timestamp, offset;

    // 构造函数
    public Package(int _source, int _destination, int _timestamp, int _offset) {
        source = _source;
        destination = _destination;
        timestamp = _timestamp;
        offset = _offset;
    }

    // 重写 equals 方法，判断两个数据包是否具有相同的 source、destination 和 timestamp
    @Override
    public boolean equals(Object o) {
        if (o.getClass() != Package.class) return false;
        Package tmp = (Package) o;
        return tmp.source == this.source && tmp.destination == this.destination && tmp.timestamp == this.timestamp;
    }

    // 重写 hashCode 方法，与 equals 方法对应
    @Override
    public int hashCode() {
        int res = source;
        res = res * 31 + destination;
        res = res * 31 + timestamp;
        return res;
    }

    // 重写 compareTo 方法，先比较 timestamp，若相同则比较 offset 保证顺序唯一性
    @Override
    public int compareTo(Package o) {
        if (timestamp != o.timestamp) {
            return Integer.compare(timestamp, o.timestamp);
        } else {
            return Integer.compare(offset, o.offset);
        }
    }

    @Override
    public String toString() {
        return source + "|" + destination + "|" + "|" + timestamp + "|" + offset;
    }
}

100588. Maximum Product of Subsequences With an Alternating Sum Equal to K

给你一个整数数组 nums 和两个整数 k 与 limit，你的任务是找到一个非空的 子序列，满足以下条件：

• 它的 交错和 等于 k。
• 在乘积 不超过 limit 的前提下，最大化 其所有数字的乘积。

返回满足条件的子序列的 乘积 。如果不存在这样的子序列，则返回 -1。

子序列 是指可以通过删除原数组中的某些（或不删除）元素并保持剩余元素顺序得到的新数组。

交错和 是指一个 从下标 0 开始 的数组中，偶数下标 的元素之和减去 奇数下标 的元素之和。

测试样例：

输入：nums = [1,2,3], k = 2, limit = 10

输出：6

解释: 交错和为 2 的子序列有：

• [1, 2, 3]
  • 交错和：1 - 2 + 3 = 2
  • 乘积：1 2 3 = 6
• [2]
  • 交错和：2
  • 乘积：2

解答：动态维护两组映射 maps[0] 和 maps[1]，分别表示下一个元素将处于奇数或偶数索引时的所有“交错和→乘积”可能性集合。遍历 nums，不断从一组转移到另一组，并剪枝超出 limit 的乘积。

class Solution {
    // 当乘积超过 limit 时，用一个大数标记，避免爆炸
    private static final int maxMul = 1_000_000;

    public int maxProduct(int[] nums, int k, int limit) {
        int res = -1;
        // maps[0]: 下一个元素作为奇数索引前的 (交错和 -> 乘积 集合)
        // maps[1]: 下一个元素作为偶数索引前的 (交错和 -> 乘积 集合)
        HashMap<Integer, HashSet<Integer>>[] maps = new HashMap[2];
        maps[0] = new HashMap<>();
        maps[1] = new HashMap<>();

        for (int n : nums) {
            // 本轮新加入 maps[0] 的结果，防止同轮重复
            HashMap<Integer, HashSet<Integer>> newMap0 = new HashMap<>();
            // 从 maps[1] 转移到 maps[0]（当前元素视为偶数索引）
            for (Map.Entry<Integer, HashSet<Integer>> entry : maps[1].entrySet()) {
                int sum = entry.getKey() + n;
                for (int prod : entry.getValue()) {
                    long tmp = 1L * prod * n;
                    if (tmp > limit) tmp = maxMul;
                    int p = (int) tmp;
                    if (!contains(maps[0], sum, p)) {
                        add(newMap0, sum, p);
                        add(maps[0], sum, p);
                        if (sum == k && p <= limit) {
                            res = Math.max(res, p);
                        }
                    }
                }
            }
            // 以当前元素单独成序列（偶数索引）
            {
                long tmp = n;
                if (tmp > limit) tmp = maxMul;
                int p = (int) tmp;
                if (!contains(maps[0], n, p)) {
                    add(newMap0, n, p);
                    add(maps[0], n, p);
                    if (n == k && p <= limit) {
                        res = Math.max(res, p);
                    }
                }
            }
            // 从 maps[0] 转移到 maps[1]（当前元素视为奇数索引）
            for (Map.Entry<Integer, HashSet<Integer>> entry : maps[0].entrySet()) {
                int sum = entry.getKey() - n;
                for (int prod : entry.getValue()) {
                    // 跳过本轮已处理的
                    if (newMap0.containsKey(entry.getKey()) && newMap0.get(entry.getKey()).contains(prod)) {
                        continue;
                    }
                    long tmp = 1L * prod * n;
                    if (tmp > limit) tmp = maxMul;
                    int p = (int) tmp;
                    if (!contains(maps[1], sum, p)) {
                        add(maps[1], sum, p);
                        if (sum == k && p <= limit) {
                            res = Math.max(res, p);
                        }
                    }
                }
            }
        }
        return res;
    }

    // 判断 map 中是否已有 key->val
    private boolean contains(HashMap<Integer, HashSet<Integer>> map, int key, int val) {
        return map.containsKey(key) && map.get(key).contains(val);
    }

    // 向 map 中添加 key->val
    private void add(HashMap<Integer, HashSet<Integer>> map, int key, int val) {
        map.computeIfAbsent(key, x -> new HashSet<>()).add(val);
    }
}

100583. Minimum Pair Removal to Sort Array II

给你一个数组 nums，你可以执行以下操作任意次数：

• 选择 相邻 元素对中 和最小 的一对。如果存在多个这样的对，选择最左边的一个。
• 用它们的和替换这对元素。

返回将数组变为 非递减 所需的 最小操作次数 。

如果一个数组中每个元素都大于或等于它前一个元素（如果存在的话），则称该数组为非递减。

测试样例：

输入：nums = [5,2,3,1]

输出：2

解释: 交错和为 2 的子序列有：

• 元素对 (3,1) 的和最小，为 4。替换后 nums = [5,2,4]。
• 元素对 (2,4) 的和为 6。替换后 nums = [5,6]。

解答：使用 TreeMap<Integer,Long> 按位置存储当前数组值，用 TreeSet 存储所有相邻对并按“对的和、左端位置”排序。每次取出最小和对进行合并，更新左右邻居违例计数与集合，直到无违例。

class Solution {
    public int minimumPairRemoval(int[] nums) {
        // existPos: 按索引有序存储当前位置的值
        TreeMap<Integer, Long> existPos = new TreeMap<>();
        // sort: 存储所有相邻对，按 (n0+n1, pos0) 排序
        TreeSet<Node> sort = new TreeSet<>();
        // 初始违例数：前后两元素若递减则算一例
        int violations = 0;
        // 初始化 existPos、sort 及违例计数
        for (int i = 0; i < nums.length; ++i) {
            existPos.put(i, (long) nums[i]);
            if (i > 0 && nums[i-1] > nums[i]) {
                violations++;
            }
            if (i + 1 < nums.length) {
                sort.add(new Node(i, i+1, nums[i], nums[i+1]));
            }
        }
        int count = 0;
        // 不断合并最小和的相邻对，直到无违例
        while (violations > 0) {
            Node node = sort.pollFirst(); // 取出最小和对
            // 处理左邻居
            Map.Entry<Integer, Long> left = existPos.lowerEntry(node.pos0);
            if (left != null) {
                if (left.getValue() > node.n0) violations--;
                sort.remove(new Node(left.getKey(), node.pos0, left.getValue(), node.n0));
            }
            // 处理右邻居
            Map.Entry<Integer, Long> right = existPos.higherEntry(node.pos1);
            if (right != null) {
                if (node.n1 > right.getValue()) violations--;
                sort.remove(new Node(node.pos1, right.getKey(), node.n1, right.getValue()));
            }
            // 处理当前对的违例
            if (node.n0 > node.n1) {
                violations--;
            }
            // 合并操作：移除右端点，更新左端点值
            existPos.remove(node.pos1);
            existPos.put(node.pos0, node.n0 + node.n1);
            // 插入新左对
            if (left != null) {
                if (left.getValue() > node.n0 + node.n1) violations++;
                sort.add(new Node(left.getKey(), node.pos0, left.getValue(), node.n0 + node.n1));
            }
            // 插入新右对
            if (right != null) {
                if (node.n0 + node.n1 > right.getValue()) violations++;
                sort.add(new Node(node.pos0, right.getKey(), node.n0 + node.n1, right.getValue()));
            }
            count++;
        }
        return count;
    }
}

// 辅助类，表示一对相邻元素的信息
class Node implements Comparable<Node> {
    int pos0, pos1;   // 左右索引
    long n0, n1;      // 左右值

    public Node(int p0, int p1, long v0, long v1) {
        pos0 = p0; pos1 = p1; n0 = v0; n1 = v1;
    }

    @Override
    public int compareTo(Node other) {
        long s1 = this.n0 + this.n1, s2 = other.n0 + other.n1;
        if (s1 != s2) {
            return Long.compare(s1, s2);      // 按和升序
        }
        return Integer.compare(this.pos0, other.pos0); // 和相同时按左索引升序
    }

    @Override
    public boolean equals(Object o) {
        if (!(o instanceof Node)) return false;
        Node that = (Node)o;
        return this.pos0==that.pos0 && this.pos1==that.pos1
            && this.n0==that.n0 && this.n1==that.n1;
    }

    @Override
    public int hashCode() {
        return Objects.hash(pos0, pos1, n0, n1);
    }
}