1. 題目

假設(shè)我們以下述方式將我們的文件系統(tǒng)抽象成一個(gè)字符串:

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

dirsubdir1subdir2file.ext

目錄 dir 包含一個(gè)空的子目錄 subdir1 和一個(gè)包含一個(gè)文件 file.ext 的子目錄 subdir2 。

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

dirsubdir1file1.extsubsubdir1subdir2subsubdir2file2.ext

目錄 dir 包含兩個(gè)子目錄 subdir1 和 subdir2。
subdir1 包含一個(gè)文件 file1.ext 和一個(gè)空的二級子目錄 subsubdir1。
subdir2 包含一個(gè)二級子目錄 subsubdir2 ，其中包含一個(gè)文件 file2.ext。

我們致力于尋找我們文件系統(tǒng)中文件的最長 (按字符的數(shù)量統(tǒng)計(jì)) 絕對路徑。例如，在上述的第二個(gè)例子中，最長路徑為 "dir/subdir2/subsubdir2/file2.ext"，其長度為 32 (不包含雙引號)。

給定一個(gè)以上述格式表示文件系統(tǒng)的字符串，返回文件系統(tǒng)中文件的最長絕對路徑的長度。 如果系統(tǒng)中沒有文件，返回 0。

說明:
文件名至少存在一個(gè) . 和一個(gè)擴(kuò)展名。
目錄或者子目錄的名字不能包含 .。
要求時(shí)間復(fù)雜度為 O(n) ，其中 n 是輸入字符串的大小。

請注意，如果存在路徑 aaaaaaaaaaaaaaaaaaaaa/sth.png 的話，那么 a/aa/aaa/file1.txt 就不是一個(gè)最長的路徑。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/longest-absolute-file-path
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

2. 解題

• 用一個(gè)數(shù)組記錄到當(dāng)前層的字符個(gè)數(shù)，利用前綴累加
• \t的個(gè)數(shù)表示層數(shù)，注意字符個(gè)數(shù)也包括\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<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;//利用前綴求當(dāng)前長度if(foundfile)//找到文件了{maxlen = max(maxlen, len[lv]+lv);//更新最大長度，lv為\t個(gè)數(shù)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

總結(jié)

以上是生活随笔為你收集整理的LeetCode 388. 文件的最长绝对路径（不用栈，前缀和）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。