★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
?微信公眾號：山青詠芝（shanqingyongzhi）
?博客園地址：山青詠芝（https://www.cnblogs.com/strengthen/）
?GitHub地址：https://github.com/strengthen/LeetCode
?原文地址：https://www.cnblogs.com/strengthen/p/9778434.html?
?如果鏈接不是山青詠芝的博客園地址，則可能是爬取作者的文章。
?原文已修改更新！強(qiáng)烈建議點(diǎn)擊原文地址閱讀！支持作者！支持原創(chuàng)！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

Suppose we abstract our file system by a string in the following manner:

The string?"dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext"?represents:

dirsubdir1subdir2file.ext

The directory?dir?contains an empty sub-directory?subdir1?and a sub-directory?subdir2?containing a file?file.ext.

The string?"dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext"represents:

dirsubdir1file1.extsubsubdir1subdir2subsubdir2file2.ext

The directory?dir?contains two sub-directories?subdir1?and?subdir2.?subdir1?contains a file?file1.ext?and an empty second-level sub-directory?subsubdir1.?subdir2?contains a second-level sub-directory?subsubdir2containing a file?file2.ext.

We are interested in finding the longest (number of characters) absolute path to a file within our file system. For example, in the second example above, the longest absolute path is?"dir/subdir2/subsubdir2/file2.ext", and its length is?32?(not including the double quotes).

Given a string representing the file system in the above format, return the length of the longest absolute path to file in the abstracted file system. If there is no file in the system, return?0.

Note:

• The name of a file contains at least a?.?and an extension.
• The name of a directory or sub-directory will not contain a?..

?

Time complexity required:?O(n)?where?n?is the size of the input string.

Notice that?a/aa/aaa/file1.txt?is not the longest file path, if there is another path?aaaaaaaaaaaaaaaaaaaaa/sth.png.

---

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

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

dirsubdir1subdir2file.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"?表示:

dirsubdir1file1.extsubsubdir1subdir2subsubdir2file2.ext

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

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

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

說明:

• 文件名至少存在一個?.?和一個擴(kuò)展名。
• 目錄或者子目錄的名字不能包含?.。

要求時間復(fù)雜度為?O(n)?，其中?n?是輸入字符串的大小。

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

---

?16ms

1 class Solution { 2 func lengthLongestPath(_ input: String) -> Int { 3 guard input != nil || input.count != 0 else 4 { 5 return 0 6 } 7 //創(chuàng)建整形堆棧，存放各級文件長度 8 var stackOfLen = Stack<Int>() 9 var strArray = input.characters.split{$0 == "\n"}.map(String.init) 10 var longesLen:Int = 0 11 for i in 0..<strArray.count 12 { 13 let item:String = strArray[i] 14 ////計算當(dāng)前文件的層級 15 var level = LastIndexOf(item) 16 //返回到上一個同級文件的位置,注意使用count(),而非count 17 //例如：示例中遇到 \tsubdir2 時返回到與它同級的 \tsubdir1 位置 18 while(stackOfLen.count() > level) 19 { 20 stackOfLen.pop() 21 } 22 let tempLen:Int = item.count - level 23 if stackOfLen.count() == 0 24 { 25 stackOfLen.push(tempLen) 26 } 27 else 28 { 29 ////加1 是返回的結(jié)果帶有 / 分割 30 let num:Int = tempLen + stackOfLen.GetLastElement() + 1 31 stackOfLen.push(num) 32 } 33 if item.contains(".") 34 { 35 longesLen = max(longesLen,stackOfLen.GetLastElement()) 36 } 37 } 38 return longesLen 39 } 40 //獲取最后一個"\t"的索引整數(shù)位置 41 func LastIndexOf(_ item:String) -> Int 42 { 43 var num:Int = 0 44 var itemReversed:ReversedCollection<String> = item.reversed() 45 for i in 0..<itemReversed.count 46 { 47 var char:Character = itemReversed[itemReversed.index(itemReversed.startIndex, offsetBy: i)] 48 if char == "\t" 49 { 50 //注意索引也要反轉(zhuǎn)，返回的為索引位置+1 51 num = item.count - i 52 break 53 } 54 } 55 return num 56 } 57 58 //堆棧的泛型通用版本 59 struct Stack<Element> { 60 var items = [Element]() 61 //入棧 62 //mutating 關(guān)鍵字修飾方法是為了能在該方法中修改 struct 或是 enum 的變量 63 mutating func push(_ item: Element) { 64 items.append(item) 65 } 66 //出棧 67 mutating func pop() -> Element { 68 return items.removeLast() 69 } 70 //返回堆棧中的元素個數(shù) 71 mutating func count() -> Int 72 { 73 return items.count 74 } 75 //獲取最后一個元素 76 mutating func GetLastElement()->Element 77 { 78 return items[items.count-1] 79 } 80 } 81 }

---

8ms

1 class Solution { 2 3 func lengthLongestPath(_ input: String) -> Int { 4 guard !input.isEmpty else { return 0 } 5 6 let lines = input.split(separator: "\n").map{ String($0) } 7 var sum = [Int](repeating: 0, count: input.count + 1) 8 var result = 0 9 10 for line in lines { 11 var count = 0 12 while line.charAt(count) == "\t" { 13 count += 1 14 } 15 let level = count + 1 16 let len = line.count - (level - 1) 17 if line.contains(".") { 18 result = max(result, sum[level - 1] + len + level - 1) 19 } else { 20 sum[level] = sum[level - 1] + len 21 } 22 } 23 24 return result 25 } 26 } 27 28 extension String { 29 30 func charAt(_ i: Int) -> Character { 31 let index = self.index(self.startIndex, offsetBy: i) 32 return self[index] 33 } 34 }

---

12ms

1 class Solution { 2 func lengthLongestPath(_ input: String) -> Int { 3 var dirPathLengths = [Int]() 4 var maxLength = 0 5 for pathComponent in input.split(separator: "\n") { 6 var dirLength = 0 7 let isFile = pathComponent.contains(".") 8 for (depth, dirLevel) in pathComponent.split(separator: "\t", omittingEmptySubsequences: false).enumerated() { 9 let isPathComponentFile = dirLevel.contains(".") 10 if depth < dirPathLengths.count { 11 if !dirLevel.isEmpty && !isFile { 12 dirPathLengths[depth] = dirLevel.count 13 } 14 } else { 15 if !dirLevel.isEmpty && !isFile { 16 dirPathLengths.append(dirLevel.count) 17 } 18 } 19 if isFile { 20 dirLength += (isPathComponentFile ? pathComponent.count : dirPathLengths[depth]) 21 } 22 } 23 maxLength = max(maxLength, dirLength) 24 } 25 return maxLength 26 } 27 }

---

16ms

1 class Solution { 2 3 func lengthLongestPath(_ input: String) -> Int { 4 guard !input.isEmpty else { return 0 } 5 6 let lines = input.split(separator: "\n").map{ String($0) } 7 var sum = [Int](repeating: 0, count: input.count + 1) 8 var result = 0 9 10 for line in lines { 11 var count = 0 12 while line.charAt(count) == "\t" { 13 count += 1 14 } 15 let level = count + 1 16 let len = line.count - (level - 1) 17 if line.contains(".") { 18 result = max(result, sum[level - 1] + len + level - 1) // Plus "/" 19 } else { 20 sum[level] = sum[level - 1] + len 21 } 22 } 23 24 return result 25 } 26 } 27 28 extension String { 29 30 func charAt(_ i: Int) -> Character { 31 let index = self.index(self.startIndex, offsetBy: i) 32 return self[index] 33 } 34 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/strengthen/p/9778434.html

總結(jié)

以上是生活随笔為你收集整理的[Swift]LeetCode388. 文件的最长绝对路径 | Longest Absolute File Path的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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