"A goal is a dream with a deadline." - Napoleon Hill

1. 題目描述

2. ?題目分析與解析

2.1 思路一

這個題目開始看起來并不太容易知道該怎么寫代碼，所以不知道什么思路那就先模擬人的行為，比如對于如下測試用例：

首先 /代表根目錄，然后向后走，發現 a/，滿足規則，繼續向后走，發現 ./，其實就是表示當前路徑，那說明可以省略，就刪除該部分。

繼續向后，發現 b/，滿足規則，繼續向后走，發現 ../，表示當前路徑的上一級目錄。根據前面走過的步驟，可以知道當前路徑為：/a/b，一次回到上一級目錄就是 /a。

繼續向后走，發現還有一個 ../，又需要回到上一級目錄，也就是 /。

最后發現 c/，說明最終的結果是 /c。

而對于如下測試用例：

我們可以發現對于雙 /需要特殊處理。

根據以上描述，我們可以粗略的描述一下代碼思路：

1. 定義結果字符串，用一個字符數組最好（方便后續按照塊刪除）

2. 遍歷path

3. 截取下一個 /之前的字符

   • 如果發現截取出的是 .，就刪除這一小段

   • 如果發現截取出的是 ..，就刪除上一個小塊的文件地址，比如對于當前路徑為 /asad/qwej，如果發現此時截取了 ..，就刪除塊 /qwej

   • 如果發現是空（對應 // 的情況），就跳過

   • 如果發現是其它字符串，那就在當前塊前面加一個 / 然后直接拼接上。（比如當前為/asad/qwej，此時發現對應字符串為 poi，那么就將 "/" + "poi"，拼接在/asad/qwej后面形成/asad/qwej/poi

3.2 思路二

既然我們要處理的特殊情況就那么幾種：

1. 出現 .

2. 出現 ..

3. 多余的

4. 正常出現文件路徑

那么我們是不是可以

1. 將1視為什么都不做？

2. 將2視為減少一個路徑

3. 將3跳過

4. 將4視為增加一個路徑

又因為我們要增加或者減少的哪個路徑總是在我們剛剛遍歷過的地方，也就是之前的路徑我不需要管，相當于先進，后來的內容我要進行判斷，相當于后出，那么是不是就可以使用棧來解決？（其實思路和思路一沒什么區別，就是把數組換成棧了）

所以根據以上內容我們可以寫出如下代碼思路：

1. 定義一個棧

2. 遍歷path

3. 發現出現 .，對棧保持不動

4. 發現出現 ..，就彈棧，直到彈出一個 /

5. 如果發現是空（對應 // 的情況），就跳過

6. 如果發現是其它字符串，那就在當前塊前面加一個 / 然后入棧

3. 代碼實現

3.1 思路一

3.2 思路二

4. 相關復雜度分析

思路一：

• 時間復雜度：O(n)，其中 n 是路徑字符串的長度。在遍歷路徑字符串的過程中，執行了一些常數時間的操作，例如字符串拼接、字符串比較等。

• 空間復雜度：O(n)，使用了一個 ArrayList 和一個 StringBuilder。ArrayList 的空間取決于路徑中塊的數量，而 StringBuilder 的空間取決于路徑中每個塊的長度。

思路二：

• 時間復雜度：O(n)，其中 n 是路徑字符串的長度。首先，通過 split() 方法將路徑字符串分割成一個字符串數組，時間復雜度為 O(n)。然后，對字符串數組進行遍歷，執行了一些常數時間的操作，例如棧的入棧和出棧操作。

• 空間復雜度：O(n)，使用了一個棧和一個字符串數組。棧的空間取決于路徑中塊的數量，而字符串數組的空間取決于路徑中塊的數量以及每個塊的平均長度。

綜上所述，思路一和思路二的時間復雜度都是線性的，但在空間復雜度上稍有不同。思路一的空間復雜度主要取決于路徑中每個塊的長度，而思路二的空間復雜度主要取決于路徑中塊的數量。通常情況下，思路二的空間復雜度略低于思路一。