LeetCode刷题实战588设计内存文件系统

　　算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！
　　今天和大家聊的问题叫做 设计内存文件系统，我们先来看题面：
　　https://leetcode-cn.com/problems/design-in-memory-file-system/
　　Design an in-memory file system to simulate the following functions:
　　ls: Given a path in string format. If it is a file path, return a list that only contains this file＂s name. If it is a directory path, return the list of file and directory names in this directory. Your output (file and directory names together) should in lexicographic order.
　　mkdir: Given a directory path that does not exist, you should make a new directory according to the path. If the middle directories in the path don＂t exist either, you should create them as well. This function has void return type.
　　addContentToFile: Given a file path and file content in string format. If the file doesn＂t exist, you need to create that file containing given content. If the file already exists, you need to append given content to original content. This function has void return type.
　　readContentFromFile: Given a file path, return its content in string format.
　　设计一个内存文件系统，模拟以下功能：
　　ls：以字符串的格式输入一个路径。如果它是一个文件的路径，那么函数返回一个列表，仅包含这个文件的名字。如果它是一个文件夹的的路径，那么返回该 文件夹内 的所有文件和子文件夹的名字。你的返回结果（包括文件和子文件夹）应该按字典序排列。
　　mkdir：输入一个当前不存在的 文件夹路径 ，你需要根据路径名创建一个新的文件夹。如果有上层文件夹路径不存在，那么你也应该将它们全部创建。这个函数的返回类型为 void 。
　　addContentToFile：输入字符串形式的 文件路径 和 文件内容 。如果文件不存在，你需要创建包含给定文件内容的文件。如果文件已经存在，那么你需要将给定的文件内容 追加 在原本内容的后面。这个函数的返回类型为 void 。
　　readContentFromFile：输入 文件路径 ，以字符串形式返回该文件的 内容 。示例输入:
　　[＂FileSystem＂,＂ls＂,＂mkdir＂,＂addContentToFile＂,＂ls＂,＂readContentFromFile＂]
　　[[],[＂/＂],[＂/a/b/c＂],[＂/a/b/c/d＂,＂hello＂],[＂/＂],[＂/a/b/c/d＂]]
　　输出:
　　[,[],,,[＂a＂],＂hello＂]解题
　　https://www.cnblogs.com/grandyang/p/6944331.html
　　这道题让我们设计一个内存文件系统，实现显示当前文件，创建文件，添加内容到文件，读取文件内容等功能，感觉像是模拟一个terminal的一些命令。这道题比较tricky的地方是ls这个命令，题目中的例子其实不能很好的展示出ls的要求，其对文件和文件夹的处理方式是不同的。由于这里面的文件没有后缀，所以最后一个字符串有可能是文件，也有可能是文件夹。比如a/b/c，那么最后的c有可能是文件夹，也有可能好是文件，如果c是文件夹的话，ls命令要输出文件夹c中的所有文件和文件夹，而当c是文件的话，只需要输出文件c即可。另外需要注意的是在创建文件夹的时候，路径上没有的文件夹都要创建出来，还有就是在给文件添加内容时，路径中没有的文件夹都要创建出来。论坛上这道题的高票解法都新建了一个自定义类，但是博主一般不喜欢用自定义类来解题，而且感觉那些使用了自定义类的解法并没有更简洁易懂，所以这里博主就不创建自定义类了，而是使用两个哈希表来做，其中dirs建立了路径和其对应的包含所有文件和文件夹的集合之间的映射，files建立了文件的路径跟其内容之间的映射。
　　最开始时将根目录＂/＂放入dirs中，然后看ls的实现方法，如果该路径存在于files中，说明最后一个字符串是文件，那么我们将文件名取出来返回即可，如果不存在，说明最后一个字符串是文件夹，那么我们到dirs中取出该文件夹内所有的东西返回即可。再来看mkdir函数，我们的处理方法就是根据＂/＂来分隔分隔字符串，如果是Java，那么直接用String自带的split函数就好了，但是C++没有Java那么多自带函数，所以只能借助字符串流类来处理，处理方法就是将每一层的路径分离出来，然后将该层的文件或者文件夹加入对应的集合中，注意的地方就是处理根目录时，要先加上＂/＂，其他情况都是后加。下面来看addContentToFile函数，首先分离出路径和文件名，如果路径为空，说明是根目录，需要加上＂/＂，然后看这个路径是否已经在dirs中存在，如果不存在，调用mkdir来创建该路径，然后把文件加入该路径对应的集合中，再把内容加入该文件路径的映射中。最后的读取文件内容就相当简单了，直接在files中返回即可，参见代码如下：class FileSystem {
　　public:
　　FileSystem {
　　dirs[＂/＂];
　　}
　　vector ls(string path) {
　　if (files.count(path)) {
　　int idx = path.find_last_of(＂/＂);
　　return {path.substr(idx + 1)};
　　}
　　auto t = dirs[path];
　　return vector(t.begin, t.end);
　　}
　　void mkdir(string path) {
　　istringstream is(path);
　　string t = ＂＂, dir = ＂＂;
　　while (getline(is, t, ＂/＂)) {
　　if (t.empty) continue;
　　if (dir.empty) dir += ＂/＂;
　　dirs[dir].insert(t);
　　if (dir.size > 1) dir += ＂/＂;
　　dir += t;
　　}
　　}
　　void addContentToFile(string filePath, string content) {
　　int idx = filePath.find_last_of(＂/＂);
　　string dir = filePath.substr(0, idx);
　　string file = filePath.substr(idx + 1);
　　if (dir.empty) dir = ＂/＂;
　　if (!dirs.count(dir)) mkdir(dir);
　　dirs[dir].insert(file);
　　files[filePath].append(content);
　　}
　　string readContentFromFile(string filePath) {
　　return files[filePath];
　　}
　　private:
　　unordered_map dirs;
　　unordered_map files;
　　};
　　在看或者转发吧，你们的支持是我最大的动力 。
　　上期推文：
　　LeetCode1-580题汇总，希望对你有点帮助！
　　LeetCode刷题实战581：最短无序连续子数组
　　LeetCode刷题实战582：杀掉进程
　　LeetCode刷题实战583：两个字符串的删除操作
　　LeetCode刷题实战584：寻找用户推荐人
　　LeetCode刷题实战585：2016年的投资
　　LeetCode刷题实战586：订单最多的客户
　　LeetCode刷题实战587：安装栅栏