本文共 2038 字，大约阅读时间需要 6 分钟。

1. 题目

假设我们以下述方式将我们的文件系统抽象成一个字符串:

字符串 "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext" 表示:

dir    subdir1    subdir2        file.ext

目录 dir 包含一个空的子目录 subdir1 和一个包含一个文件 file.ext 的子目录 subdir2 。

字符串 "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext" 表示:

dir    subdir1        file1.ext        subsubdir1    subdir2        subsubdir2            file2.ext

目录 dir 包含两个子目录 subdir1 和 subdir2。

我们致力于寻找我们文件系统中文件的最长 (按字符的数量统计) 绝对路径。例如，在上述的第二个例子中，最长路径为 "dir/subdir2/subsubdir2/file2.ext"，其长度为 32 (不包含双引号)。

给定一个以上述格式表示文件系统的字符串，返回文件系统中文件的最长绝对路径的长度。 如果系统中没有文件，返回 0。

说明:

请注意，如果存在路径 aaaaaaaaaaaaaaaaaaaaa/sth.png 的话，那么 a/aa/aaa/file1.txt 就不是一个最长的路径。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/longest-absolute-file-path

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

• 用一个数组记录到当前层的字符个数，利用前缀累加
• \t的个数表示层数，注意字符个数也包括\t

测试样例

"dir\n file.txt" "di r\n file.txt" "dir\n        file.txt""a.aaa\n\tfile.txt""dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext""dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext"

class Solution {
   public:    int lengthLongestPath(string input) {
       	int maxlen=0, i, lv = 0, count=0;    	vector
   
     len(50,0);    	bool foundfile = false;    	for(i = 0; i < input.size(); ++i)    	{
       		if(input[i]=='\n')    		{
       			len[lv] = lv>0 ? len[lv-1]+count : count;//利用前缀求当前长度    			if(foundfile)//找到文件了    			{
       				maxlen = max(maxlen, len[lv]+lv);//更新最大长度，lv为\t个数    				foundfile = false;    			}    			lv = 0;    			count = 0;    		}    		else if(input[i]=='\t')    			lv++;    		else    		{
       			if(i>0 && input[i-1]=='.' && (isalpha(input[i])||isdigit(input[i])))    				foundfile = true;    			count++;    		}    	}        len[lv] = lv>0 ? len[lv-1]+count : count;        if(foundfile)            maxlen = max(maxlen, len[lv]+lv);    	return maxlen;    }};
   

0 ms 6.6 MB

转载地址：https://michael.blog.csdn.net/article/details/106210795 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！