LeetCode – 19 – 设计路由器 – 20 -设计电影租借系统 – 21 – 最大频率元素计数 – 22 – 比较版本号

作者：

在

你好(握手)，你好(握手)，你好你好你好(握手)

——TCP(并非

25 – 09 – 19 (补于 25 – 09 – 25)

今日份题面

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

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

叽里咕噜说什么呢

依然考虑 OO 那么我们可以设计出如下类：

class Package implements Comparable<Package> {
    private int source;
    private int destination;
    private int timestamp;

    public Package() {
        this.source = -1;
        this.destination = -1;
        this.timestamp = -1;
    }

    public Package(int source, int destination, int timestamp) {
        this.source = source;
        this.destination = destination;
        this.timestamp = timestamp;
    }

    // Getter方法，便于访问字段
    public int getSource() {
        return source;
    }

    public int getDestination() {
        return destination;
    }

    public int getTimestamp() {
        return timestamp;
    }

    @Override
    public int compareTo(Package other) {
        return this.timestamp - other.timestamp;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        Package other = (Package) obj;
        return source == other.source && 
               destination == other.destination && 
               timestamp == other.timestamp;
    }

    @Override
    public int hashCode() {
        return Objects.hash(source, destination, timestamp);
    }
}

然后对于路由器 Router 类，我们考虑使用队列处理任务，HashMap速查以及一个内存限制

    private ArrayDeque<Package> packagesPool; // 使用ArrayDeque作为FIFO队列
    private HashSet<Package> curPackages;     // 用于快速重复检查
    private int packagesPoolSize;             // 内存限制

剩下的按需求实现就行

    public Router(int memoryLimit) {
        this.packagesPoolSize = memoryLimit;
        this.packagesPool = new ArrayDeque<>();
        this.curPackages = new HashSet<>();
    }

    public boolean addPacket(int source, int destination, int timestamp) {
        Package curPackage = new Package(source, destination, timestamp);
        
        // 检查重复包
        if (curPackages.contains(curPackage)) {
            return false;
        }
        
        // 如果包池已满，移除最旧的数据包（队列头部）
        if (packagesPool.size() >= packagesPoolSize) {
            Package oldestPackage = packagesPool.poll();
            curPackages.remove(oldestPackage);
        }
        
        // 添加新包到队列和集合中
        packagesPool.add(curPackage);
        curPackages.add(curPackage);
        return true;
    }

    public int[] forwardPacket() {
        if (packagesPool.isEmpty()) {
            return new int[] {};
        }
        Package curPackage = packagesPool.poll();
        curPackages.remove(curPackage);
        return new int[] {curPackage.getSource(), curPackage.getDestination(), curPackage.getTimestamp()};
    }

    public int getCount(int destination, int startTime, int endTime) {
        int count = 0;
        // 遍历包池，由于包按时间戳递增顺序存储，可以提前终止
        Iterator<Package> iterator = packagesPool.iterator();
        while (iterator.hasNext()) {
            Package pkg = iterator.next();
            if (pkg.getTimestamp() < startTime) {
                continue; // 时间戳太小，跳过
            }
            if (pkg.getTimestamp() > endTime) {
                break; // 时间戳超过范围，由于时间戳递增，后续包都更大，所以终止
            }
            if (pkg.getDestination() == destination) {
                count++;
            }
        }
        return count;
    }

好的，那么提交一下这题就 AC… 等等

好的又双叒叕双爆了…

实际上查找过于浪费时间，因此考虑二分加速

class Router {
    private record Packet(int source, int destination, int timestamp) {
    }

    private record Pair(List<Integer> timestamps, int head) {
    }

    private final int memoryLimit;
    private final Queue<Packet> packetQ = new ArrayDeque<>(); // Packet 队列
    private final Set<Packet> packetSet = new HashSet<>(); // Packet 集合
    private final Map<Integer, Pair> destToTimestamps = new HashMap<>(); // destination -> ([timestamp], head)

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

    public boolean addPacket(int source, int destination, int timestamp) {
        Packet packet = new Packet(source, destination, timestamp);
        if (!packetSet.add(packet)) { // packet 在 packetSet 中
            return false;
        }
        if (packetQ.size() == memoryLimit) { // 太多了
            forwardPacket();
        }
        packetQ.add(packet); // 入队
        destToTimestamps.computeIfAbsent(destination, k -> new Pair(new ArrayList<>(), 0)).timestamps.add(timestamp);
        return true;
    }

    public int[] forwardPacket() {
        if (packetQ.isEmpty()) {
            return new int[]{};
        }
        Packet packet = packetQ.poll(); // 出队
        packetSet.remove(packet);
        destToTimestamps.compute(packet.destination, (k, p) -> new Pair(p.timestamps, p.head + 1)); // 队首下标加一，模拟出队
        return new int[]{packet.source, packet.destination, packet.timestamp};
    }

    public int getCount(int destination, int startTime, int endTime) {
        Pair p = destToTimestamps.get(destination);
        if (p == null) {
            return 0;
        }
        int left = lowerBound(p.timestamps, startTime, p.head - 1);
        int right = lowerBound(p.timestamps, endTime + 1, p.head - 1);
        return right - left;
    }

    private int lowerBound(List<Integer> nums, int target, int left) {
        int right = nums.size();
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (nums.get(mid) >= target) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return right;
    }
}

这样就能过了

那么以上

25 – 09 – 20 (补于 25 – 09 – 26)

黎明前的黑暗(

今日份题面

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

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

系统需要支持以下操作：

Search：找到拥有指定电影且 未借出 的商店中 最便宜的 5 个 。商店需要按照价格升序排序，如果价格相同，则 shop_i 较小的商店排在前面。如果查询结果少于 5 个商店，则将它们全部返回。如果查询结果没有任何商店，则返回空列表。

Rent：从指定商店借出指定电影，题目保证指定电影在指定商店 未借出 。

Drop：在指定商店返还 之前已借出 的指定电影。

Report：返回 最便宜的 5 部已借出电影 （可能有重复的电影 ID），将结果用二维列表 res 返回，其中 res[j] = [shop_j, movie_j] 表示第 j 便宜的已借出电影是从商店 shop_j 借出的电影 movie_j 。res 中的电影需要按价格升序排序；如果价格相同，则 shop_j 较小的排在前面；如果仍然相同，则 movie_j 较小的排在前面。如果当前借出的电影小于 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 操作指定的商店 之前已借出 指定电影。

叽里咕噜又是一大堆，但稍微梳理一下我们可以根据数据操作进行对应的数据结构的选择：

首先为了根据商店ID和电影ID快速获取Movie对象,肯定是需要使用一个 HashMap 嵌套进行映射的；
同时 Search 操作需要找到拥有指定电影且 未借出 的商店中 最便宜的 5 个 ，那么显然可以是一个值为 TreeSet 类型的 HashMap
最后 Report 操作需要返回 最便宜的 5 部已借出电影那么显然也是一个有序数组类型
注意，借出与返还操作我们不必单独维护，可以在类中设置一个 Boolean 属性变量 LazyTag 处理即可(当然即时处理也行)

那么思路很清晰了，首先实现 OO：

/**
 * 电影类，包含商店ID、电影ID、价格和借出状态
 */
class Movie implements Comparable<Movie> {
    private int shopId;     // 商店ID
    private int movieId;    // 电影ID
    private int price;      // 租借价格
    private boolean rented; // 是否借出

    public Movie(int shopId, int movieId, int price) {
        this.shopId = shopId;
        this.movieId = movieId;
        this.price = price;
        this.rented = false;
    }

    // Getter和Setter方法
    public int getShopId() {
        return shopId;
    }

    public void setShopId(int shopId) {
        this.shopId = shopId;
    }

    public int getMovieId() {
        return movieId;
    }

    public void setMovieId(int movieId) {
        this.movieId = movieId;
    }

    public int getPrice() {
        return price;
    }

    public void setPrice(int price) {
        this.price = price;
    }

    public boolean isRented() {
        return rented;
    }

    public void setRented(boolean rented) {
        this.rented = rented;
    }

    /**
     * 比较方法：用于排序
     * 按价格升序，然后商店ID升序，然后电影ID升序
     */
    @Override
    public int compareTo(Movie other) {
        if (this.price != other.price) {
            return this.price - other.price;
        }
        if (this.shopId != other.shopId) {
            return this.shopId - other.shopId;
        }
        return this.movieId - other.movieId;
    }

    /**
     * 相等性比较：基于商店ID和电影ID，忽略价格和借出状态
     */
    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (!(obj instanceof Movie)) return false;
        Movie other = (Movie) obj;
        return this.shopId == other.shopId && this.movieId == other.movieId;
    }

    /**
     * 哈希码计算：基于商店ID和电影ID
     */
    @Override
    public int hashCode() {
        return Objects.hash(shopId, movieId);
    }
}

接下来基于 Movie 我们考虑租借系统的成员变量：

class MovieRentingSystem {
    // 通过商店ID和电影ID快速获取Movie对象
    private Map<Integer, Map<Integer, Movie>> shopMovieMap;
    // 按电影ID分组，存储所有Movie对象的TreeSet（用于search操作）
    private Map<Integer, TreeSet<Movie>> searchMap;
    // 存储所有已借出Movie对象的TreeSet（用于report操作）
    private TreeSet<Movie> reportedSet;
}

以及初始化：

public MovieRentingSystem(int n, int[][] entries) {
        shopMovieMap = new HashMap<>();
        searchMap = new HashMap<>();
        reportedSet = new TreeSet<>();

        for (int[] entry : entries) {
            int shopId = entry[0];
            int movieId = entry[1];
            int price = entry[2];
            Movie movie = new Movie(shopId, movieId, price);

            // 存入shopMovieMap
            shopMovieMap.putIfAbsent(shopId, new HashMap<>());
            shopMovieMap.get(shopId).put(movieId, movie);

            // 存入searchMap
            searchMap.putIfAbsent(movieId, new TreeSet<>());
            searchMap.get(movieId).add(movie);
        }
    }

接下来就是方法的实现了：

    public List<Integer> search(int movie) {
        List<Integer> result = new ArrayList<>();
        if (!searchMap.containsKey(movie)) {
            return result;
        }

        TreeSet<Movie> movieSet = searchMap.get(movie);
        int count = 0;
        for (Movie m : movieSet) {
            if (count >= 5) {
                break;
            }
            if (!m.isRented()) {
                result.add(m.getShopId());
                count++;
            }
        }
        return result;
    }

    public void rent(int shop, int movie) {
        Movie m = shopMovieMap.get(shop).get(movie);
        m.setRented(true);
        reportedSet.add(m);
    }

    public void drop(int shop, int movie) {
        Movie m = shopMovieMap.get(shop).get(movie);
        m.setRented(false);
        reportedSet.remove(m);
    }

    public List<List<Integer>> report() {
        List<List<Integer>> result = new ArrayList<>();
        int count = 0;
        for (Movie m : reportedSet) {
            if (count >= 5) {
                break;
            }
            List<Integer> pair = new ArrayList<>();
            pair.add(m.getShopId());
            pair.add(m.getMovieId());
            result.add(pair);
            count++;
        }
        return result;
    }

整体而言，这一周的题做下来还是比较有水平(压力)的，实际上， Java 成熟的库系统让我在设计时只需要考虑用什么数据结构就行而不是从头开始造轮子，这其实有利也有弊，是时候重刷一下 DS 相关课设了，马上要考CCF 了(

以上

25 – 09 – 21 (补于 25 – 09 – 27)

今日份体面

给你一个由 正整数 组成的数组 nums 。

返回数组 nums 中所有具有最大频率的元素的 总频率 。

元素的频率是指该元素在数组中出现的次数。

设计模式结束了突然有点不适应(

这题实现起来还是挺简单的，开个 HashMap 扫过去更新，然后累加就行，当然也可以计数最后一起相乘，效果是一样的

class Solution {
    public int maxFrequencyElements(int[] nums) {
        Map<Integer, Integer> cnt = new HashMap<>();
        int maxCnt = 0;
        int ans = 0;
        for (int x : nums) {
            int c = cnt.merge(x, 1, Integer::sum); 
            if (c > maxCnt) {
                ans = maxCnt = c;
            } else if (c == maxCnt) {
                ans += c;
            }
        }
        return ans;
    }
}

以上

25 – 09 – 22 (补于 25 – 09 – 28)

今日份题面

给你两个 版本号字符串 version1 和 version2 ，请你比较它们。版本号由被点 '.' 分开的修订号组成。修订号的值 是它 转换为整数 并忽略前导零。

比较版本号时，请按 从左到右的顺序 依次比较它们的修订号。如果其中一个版本字符串的修订号较少，则将缺失的修订号视为 0。

怎么说捏… 哐哐调库题

核心思路很简单，字符串分割之后同下标比较，都存在的部分相等就往下比，不相等就返回结果。

较长版本号剩余的部分同样挨个考虑，为 0 则继续下一个，不为零直接根据比较的是谁返回结果

class Solution {
    public int compareVersion(String version1, String version2) {
        String [] v1sp = version1.split("\\.");
        String [] v2sp = version2.split("\\.");
        int i = 0;
        for(; i < Math.min(v1sp.length, v2sp.length); ++i){
            int n1 = Integer.parseInt(v1sp[i]);
            int n2 = Integer.parseInt(v2sp[i]);
            if(n1 == n2) continue;
            return n1 > n2 ? 1 : -1; // 直接返回
        }
        boolean which = v1sp.length > v2sp.length; // 考虑是谁
        String [] temp = which ? v1sp : v2sp;
        while(i < temp.length){
            int num = Integer.parseInt(temp[i++]);
                if(num != 0){ 
                    if(which){
                        return 1;
                    }else{
                        return -1;
                    }
            }
        }
        return 0;
    }
}

以上

分类导航

LeetCode – 19 – 设计路由器 – 20 -设计电影租借系统 – 21 – 最大频率元素计数 – 22 – 比较版本号

评论

发表回复取消回复

更多文章

CLIP – Learning Transferable Visual Models From Natural Language Supervision

LeetCode 30 ~ ? 水题(并非)

EFV++ – Retain, Blend, and Exchange

TSCF – Temporal Shift CNN – Transformer

LeetCode – 19 – 设计路由器 – 20 -设计电影租借系统 – 21 – 最大频率元素计数 – 22 – 比较版本号

评论

发表回复 取消回复

更多文章

CLIP – Learning Transferable Visual Models From Natural Language Supervision

LeetCode 30 ~ ? 水题(并非)

EFV++ – Retain, Blend, and Exchange

TSCF – Temporal Shift CNN – Transformer

发表回复取消回复