LEETCODE 588. Design In-Memory File System 解题思路分析

题目大意:

设计内存文件系统

设计一个内存文件系统,模拟以下功能:

ls: 以字符串的格式输入一个路径。如果它是一个文件的路径,那么函数返回一个列表,仅包含这个文件的名字。如果它是一个文件夹的的路径,那么返回该 文件夹内 的所有文件和子文件夹的名字。你的返回结果(包括文件和子文件夹)应该按字典序排列。

mkdir:输入一个当前不存在的 文件夹路径 ,你需要根据路径名创建一个新的文件夹。如果有上层文件夹路径不存在,那么你也应该将它们全部创建。这个函数的返回类型为 void 。

addContentToFile: 输入字符串形式的 文件路径 和 文件内容 。如果文件不存在,你需要创建包含给定文件内容的文件。如果文件已经存在,那么你需要将给定的文件内容 追加 在原本内容的后面。这个函数的返回类型为 void 。

readContentFromFile: 输入 文件路径 ,以字符串形式返回该文件的 内容 。

示例:

输入: 
["FileSystem","ls","mkdir","addContentToFile","ls","readContentFromFile"]
[[],["/"],["/a/b/c"],["/a/b/c/d","hello"],["/"],["/a/b/c/d"]]
输出: [null,[],null,null,["a"],"hello"] 

解释:

注意:

  • 你可以假定所有文件和文件夹的路径都是绝对路径,除非是根目录 / 自身,其他路径都是以 / 开头且 不 以 / 结束。
  • 你可以假定所有操作的参数都是有效的,即用户不会获取不存在文件的内容,或者获取不存在文件夹和文件的列表。
  • 你可以假定所有文件夹名字和文件名字都只包含小写字母,且同一文件夹下不会有相同名字的文件夹或文件。

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=588

解题思路分析:

本题考察的重点在于如何设计数据结构。我们知道文件目录是按照树形结构来设计的,因此我们的数据结构也应该设计为树形结构。

首先定义一个节点类,该类代表了某一级的目录(文件夹)或者是某个文件。类中需要包含以下信息:

  1. 该目录(文件夹)下包含的所有子目录(子文件夹)和文件
  2. 如果当前目录是文件,记录文件内容的字符串

因此,我们可以将该类定义为:

class Node{
    // 该目录下的所有子目录和文件
    // key是子目录或者文件名称,key为子目录或文件的节点对象
    Map<String, Node> fileList = new TreeMap<>();
    // 如果当前目录是文件,记录文件内容
    StringBuilder text= new StringBuilder();
}

定义好Node类之后,建立树形结构就会非常简单,mkdir方法中,将参数path以斜线分割,建立每一层文件夹(如果不存在),同理,addContentToFile方法中,也要先建立相应的文件夹,注意最后一层目录应该是文件类型,因此,将该文件的内容赋值到该节点。另外为了方便ls方法调用,我们将该文件的子节点对象中添加该文件本身。这样做的原因是ls目录时输出的都是它的子目录和文件,而ls文件时,需要输出自身,因此,我们将自身加入到他的子目录列表中会方便使用。

readContentFromFile方法很简单,我们只要逐层找到该文件对应的节点对象,输出它的内容即可。

ls方法也不难,同样逐层找到该层目录节点,返回它的子目录和文件列表即可。另外题目要求按照字典顺序返回列表,我们可以对map中的key进行排序后返回,另外一种做法可以使用TreeMap进行存储,他会自动为key进行排序。

实现代码:

Node root = new Node();
public FileSystem() {
}

public List<String> ls(String path) {
    String[] dirs = path.split("/");
    Node node=root;
    for(String dir : dirs){
        if("".equals(dir)) continue;
        node=node.fileList.get(dir);
    }
    List<String> res = new ArrayList<>(node.fileList.keySet());
    return res;
}

public void mkdir(String path) {
    String[] dirs = path.split("/");
    Node node=root;
    for(String dir : dirs){
        if("".equals(dir)) continue;
        Node child=node.fileList.get(dir);
        if(child==null){
            child=new Node();
            node.fileList.put(dir, child);
        }
        node = child;
    }
}

public void addContentToFile(String filePath, String content) {
    String[] dirs = filePath.split("/");
    Node node=root;
    for(int i=0;i<dirs.length;i++){
        String dir=dirs[i];
        if("".equals(dir)) continue;
        Node child=node.fileList.get(dir);
        if(child==null){
            child=new Node();
            node.fileList.put(dir, child);
        }
        if(i==dirs.length-1){
            child.text.append(content);
            child.fileList.put(dir,null);
        }
        node = child;
    }
}

public String readContentFromFile(String filePath) {
    String[] dirs = filePath.split("/");
    Node node=root;
    for(String dir : dirs){
        if("".equals(dir)) continue;
        node=node.fileList.get(dir);
    }
    return node.text.toString();
}
    
class Node{
    Map<String, Node> fileList = new TreeMap<>();
    StringBuilder text= new StringBuilder();
}

本题解法执行时间为38ms。

Runtime: 38 ms, faster than 82.77% of Java online submissions for Design In-Memory File System.

Memory Usage: 42.7 MB, less than 16.67% of Java online submissions for Design In-Memory File System.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
本文链接: https://leetcode.jp/leetcode-588-design-in-memory-file-system-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , 标签。将固定链接加入收藏夹。

发表评论

电子邮件地址不会被公开。