LeetCode 388. 文件的最长绝对路径（不用栈，前缀和）数据结构与算法Michael是个半路程序员-

1. 题目

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

字符串 "dirntsubdir1ntsubdir2nttfile.ext" 表示:

dir     subdir1     subdir2         file.ext 

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

字符串 "dirntsubdir1nttfile1.extnttsubsubdir1ntsubdir2nttsubsubdir2ntttfile2.ext" 表示:

dir     subdir1         file1.ext         subsubdir1     subdir2         subsubdir2             file2.ext 

目录 dir 包含两个子目录 subdir1 和 subdir2。
subdir1 包含一个文件 file1.ext 和一个空的二级子目录 subsubdir1。
subdir2 包含一个二级子目录 subsubdir2 ，其中包含一个文件 file2.ext。

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

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

说明:
文件名至少存在一个 . 和一个扩展名。
目录或者子目录的名字不能包含 .。
要求时间复杂度为 O(n) ，其中 n 是输入字符串的大小。

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-absolute-file-path
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

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

测试样例

"dirn file.txt" "di rn file.txt" "dirn        file.txt" "a.aaantfile.txt" "dirntsubdir1ntsubdir2nttfile.ext" "dirntsubdir1nttfile1.extnttsubsubdir1ntsubdir2nttsubsubdir2ntttfile2.ext" 

class Solution { public: int lengthLongestPath(string input) { int maxlen=0, i, lv = 0, count=0;      vector<int> 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