题目大意：
设计内存文件系统
设计一个内存文件系统，模拟以下功能：
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
解题思路分析：
本题考察的重点在于如何设计数据结构。我们知道文件目录是按照树形结构来设计的，因此我们的数据结构也应该设计为树形结构。
首先定义一个节点类，该类代表了某一级的目录（文件夹）或者是某个文件。类中需要包含以下信息：
- 该目录（文件夹）下包含的所有子目录（子文件夹）和文件
- 如果当前目录是文件，记录文件内容的字符串
因此，我们可以将该类定义为：
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-解题思路分析/