leetcode
leetcode 1351 ~ 1400
设计文件分享系统

设计文件分享系统

难度:

标签:

题目描述

代码结果

运行时间: 192 ms, 内存: 23.5 MB


// Solution for Leetcode Problem 1500: Design a File Sharing System using Java Streams
// Similar to the standard Java solution, but leveraging Java Streams for operations.

import java.util.*;
import java.util.stream.Collectors;

class FileSharingStream {
    private Map<Integer, Set<Integer>> fileToUsers;
    private Map<Integer, Set<Integer>> userToFiles;
    private int fileIdCounter;

    public FileSharingStream() {
        fileToUsers = new HashMap<>();
        userToFiles = new HashMap<>();
        fileIdCounter = 0;
    }

    public int uploadFile() {
        int fileId = ++fileIdCounter;
        fileToUsers.put(fileId, new HashSet<>());
        return fileId;
    }

    public void downloadFile(int userId, int fileId) {
        fileToUsers.computeIfAbsent(fileId, k -> new HashSet<>()).add(userId);
        userToFiles.computeIfAbsent(userId, k -> new HashSet<>()).add(fileId);
    }

    public void shareFile(int fromUserId, int toUserId, int fileId) {
        if (userToFiles.getOrDefault(fromUserId, Collections.emptySet()).contains(fileId)) {
            downloadFile(toUserId, fileId);
        }
    }

    public Set<Integer> listUserFiles(int userId) {
        return userToFiles.getOrDefault(userId, Collections.emptySet());
    }

    public Set<Integer> listFileUsers(int fileId) {
        return fileToUsers.getOrDefault(fileId, Collections.emptySet());
    }

    public List<Integer> getAllFileIds() {
        return fileToUsers.keySet().stream().collect(Collectors.toList());
    }
}

解释

方法:

这个题解使用哈希表 user_chunks 来记录每个用户拥有的文件块编号。当用户加入时,如果有之前离开的用户,则复用其 ID,否则分配一个新的 ID。当用户离开时,将其 ID 加入重用 ID 的小顶堆 reused 中。当用户请求一个文件块时,遍历所有用户,找到拥有该文件块的用户 ID,返回其有序列表,并将该文件块编号加入请求用户的拥有列表中。

时间复杂度:

O(n + k log k)

空间复杂度:

O(n * m)

代码细节讲解

🦆
在`join`方法中,如果存在多个重用的用户 ID,选择哪一个重用的 ID 是基于什么标准?为什么选择使用小顶堆来管理这些 ID?
在`join`方法中,如果存在多个可重用的用户 ID,选择的 ID 是基于最小值标准,即小顶堆的顶部元素,这是因为小顶堆能够保证每次都能快速获取最小的元素。使用小顶堆的主要原因是其能够高效地支持常数时间的最小元素查找,以及对堆的插入和删除操作的对数时间复杂度,这使得用户 ID 的管理更为高效和有序。
🦆
在`leave`方法中,当用户离开时你选择立即删除该用户的文件块记录。这种设计是否会影响到正在进行的`request`操作?如果是,如何避免这种情况?
在`leave`方法中,立即删除用户的文件块记录可能会影响到同时进行的`request`操作,特别是在多线程或并发环境中。如果`request`操作正在访问被删除的用户数据,则可能导致数据访问错误或不一致。为避免这种情况,可以实施锁机制或使用事务内存等并发控制技术来同步对`user_chunks`字典的访问,确保在修改数据时不会被其他操作干扰。
🦆
对于`request`方法,如果一个用户请求一个他已经拥有的文件块,这样的设计是否会导致不必要的重复记录?是否有方法可以优化这一点?
当前的设计中,即使用户已经拥有所请求的文件块,`request`方法仍会将该文件块添加到用户的拥有列表中,这可能导致重复记录。为优化这一点,可以在添加文件块之前检查用户是否已经拥有该文件块。如果已经拥有,则无需再次添加,这样可以避免不必要的重复记录,提高系统的效率和准确性。
🦆
在实例化FileSharing类时,初始参数m代表文件块总数。这个参数在后续操作中有何具体作用?是否有机制确保不会请求超出总数的文件块?
在实例化FileSharing类时,参数`m`指定了文件块的总数。这个参数的主要作用是在`request`方法中进行边界检查,确保用户请求的文件块编号在有效范围内(即1到m之间)。通过在`request`方法开始处检查文件块编号是否有效,从而确保不会请求不存在的文件块,这是防止请求超出总数文件块的机制。

相关问题