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

　　算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！
　　今天和大家聊的问题叫做设计内存文件系统，我们先来看题面：
　　https：leetcodecn。comproblemsdesigninmemoryfilesystem
　　Designaninmemoryfilesystemtosimulatethefollowingfunctions：
　　ls：Givenapathinstringformat。Ifitisafilepath，returnalistthatonlycontainsthisfilesname。Ifitisadirectorypath，returnthelistoffileanddirectorynamesinthisdirectory。Youroutput（fileanddirectorynamestogether）shouldinlexicographicorder。
　　mkdir：Givenadirectorypaththatdoesnotexist，youshouldmakeanewdirectoryaccordingtothepath。Ifthemiddledirectoriesinthepathdontexisteither，youshouldcreatethemaswell。Thisfunctionhasvoidreturntype。
　　addContentToFile：Givenafilepathandfilecontentinstringformat。Ifthefiledoesntexist，youneedtocreatethatfilecontaininggivencontent。Ifthefilealreadyexists，youneedtoappendgivencontenttooriginalcontent。Thisfunctionhasvoidreturntype。
　　readContentFromFile：Givenafilepath，returnitscontentinstringformat。
　　设计一个内存文件系统，模拟以下功能：
　　ls：以字符串的格式输入一个路径。如果它是一个文件的路径，那么函数返回一个列表，仅包含这个文件的名字。如果它是一个文件夹的的路径，那么返回该文件夹内的所有文件和子文件夹的名字。你的返回结果（包括文件和子文件夹）应该按字典序排列。
　　mkdir：输入一个当前不存在的文件夹路径，你需要根据路径名创建一个新的文件夹。如果有上层文件夹路径不存在，那么你也应该将它们全部创建。这个函数的返回类型为void。
　　addContentToFile：输入字符串形式的文件路径和文件内容。如果文件不存在，你需要创建包含给定文件内容的文件。如果文件已经存在，那么你需要将给定的文件内容追加在原本内容的后面。这个函数的返回类型为void。
　　readContentFromFile：输入文件路径，以字符串形式返回该文件的内容。示例输入：
　　〔FileSystem，ls，mkdir，addContentToFile，ls，readContentFromFile〕
　　〔〔〕，〔〕，〔abc〕，〔abcd，hello〕，〔〕，〔abcd〕〕
　　输出：
　　〔，〔〕，，，〔a〕，hello〕解题
　　https：www。cnblogs。comgrandyangp6944331。html
　　这道题让我们设计一个内存文件系统，实现显示当前文件，创建文件，添加内容到文件，读取文件内容等功能，感觉像是模拟一个terminal的一些命令。这道题比较tricky的地方是ls这个命令，题目中的例子其实不能很好的展示出ls的要求，其对文件和文件夹的处理方式是不同的。由于这里面的文件没有后缀，所以最后一个字符串有可能是文件，也有可能是文件夹。比如abc，那么最后的c有可能是文件夹，也有可能好是文件，如果c是文件夹的话，ls命令要输出文件夹c中的所有文件和文件夹，而当c是文件的话，只需要输出文件c即可。另外需要注意的是在创建文件夹的时候，路径上没有的文件夹都要创建出来，还有就是在给文件添加内容时，路径中没有的文件夹都要创建出来。论坛上这道题的高票解法都新建了一个自定义类，但是博主一般不喜欢用自定义类来解题，而且感觉那些使用了自定义类的解法并没有更简洁易懂，所以这里博主就不创建自定义类了，而是使用两个哈希表来做，其中dirs建立了路径和其对应的包含所有文件和文件夹的集合之间的映射，files建立了文件的路径跟其内容之间的映射。
　　最开始时将根目录放入dirs中，然后看ls的实现方法，如果该路径存在于files中，说明最后一个字符串是文件，那么我们将文件名取出来返回即可，如果不存在，说明最后一个字符串是文件夹，那么我们到dirs中取出该文件夹内所有的东西返回即可。再来看mkdir函数，我们的处理方法就是根据来分隔分隔字符串，如果是Java，那么直接用String自带的split函数就好了，但是C没有Java那么多自带函数，所以只能借助字符串流类来处理，处理方法就是将每一层的路径分离出来，然后将该层的文件或者文件夹加入对应的集合中，注意的地方就是处理根目录时，要先加上，其他情况都是后加。下面来看addContentToFile函数，首先分离出路径和文件名，如果路径为空，说明是根目录，需要加上，然后看这个路径是否已经在dirs中存在，如果不存在，调用mkdir来创建该路径，然后把文件加入该路径对应的集合中，再把内容加入该文件路径的映射中。最后的读取文件内容就相当简单了，直接在files中返回即可，参见代码如下：classFileSystem｛
　　public：
　　FileSystem｛
　　dirs〔〕；
　　｝
　　vectorls（stringpath）｛
　　if（files。count（path））｛
　　intidxpath。findlastof（）；
　　return｛path。substr（idx1）｝；
　　｝
　　autotdirs〔path〕；
　　returnvector（t。begin，t。end）；
　　｝
　　voidmkdir（stringpath）｛
　　istringstreamis（path）；
　　stringt，dir；
　　while（getline（is，t，））｛
　　if（t。empty）continue；
　　if（dir。empty）dir；
　　dirs〔dir〕。insert（t）；
　　if（dir。size1）dir；
　　dirt；
　　｝
　　｝
　　voidaddContentToFile（stringfilePath，stringcontent）｛
　　intidxfilePath。findlastof（）；
　　stringdirfilePath。substr（0，idx）；
　　stringfilefilePath。substr（idx1）；
　　if（dir。empty）dir；
　　if（！dirs。count（dir））mkdir（dir）；
　　dirs〔dir〕。insert（file）；
　　files〔filePath〕。append（content）；
　　｝
　　stringreadContentFromFile（stringfilePath）｛
　　returnfiles〔filePath〕；
　　｝
　　private：
　　unorderedmapstring，setdirs；
　　unorderedmapstring，stringfiles；
　　｝；
　　在看或者转发吧，你们的支持是我最大的动力。
　　上期推文：
　　LeetCode1580题汇总，希望对你有点帮助！
　　LeetCode刷题实战581：最短无序连续子数组
　　LeetCode刷题实战582：杀掉进程
　　LeetCode刷题实战583：两个字符串的删除操作
　　LeetCode刷题实战584：寻找用户推荐人
　　LeetCode刷题实战585：2016年的投资
　　LeetCode刷题实战586：订单最多的客户
　　LeetCode刷题实战587：安装栅栏