鏈接	簡化路徑
題序號	71
題型	字符串
解法	棧
難度	中等
熟練度	???

題目

• 給你一個字符串 path ，表示指向某一文件或目錄的 Unix 風格 絕對路徑 （以 ‘/’ 開頭），請你將其轉化為 更加簡潔的規范路徑。

• 在 Unix 風格的文件系統中規則如下：
  一個點 ‘.’ 表示當前目錄本身。
  此外，兩個點 ‘…’ 表示將目錄切換到上一級（指向父目錄）。
  任意多個連續的斜杠（即，‘//’ 或 ‘///’）都被視為單個斜杠 ‘/’。
  任何其他格式的點（例如，‘…’ 或 ‘…’）均被視為有效的文件/目錄名稱。

• 返回的 簡化路徑 必須遵循下述格式：
  始終以斜杠 ‘/’ 開頭。
  兩個目錄名之間必須只有一個斜杠 ‘/’ 。
  最后一個目錄名（如果存在）不能 以 ‘/’ 結尾。
  此外，路徑僅包含從根目錄到目標文件或目錄的路徑上的目錄（即，不含 ‘.’ 或 ‘…’）。
  返回簡化后得到的 規范路徑 。

• 示例 1：
  輸入：path = “/home/”
  輸出：“/home”
  解釋：
  應刪除尾隨斜杠。

• 示例 2：
  輸入：path = “/home//foo/”
  輸出：“/home/foo”
  解釋：
  多個連續的斜杠被單個斜杠替換。

• 示例 3：
  輸入：path = “/home/user/Documents/…/Pictures”
  輸出：“/home/user/Pictures”
  解釋：
  兩個點 “…” 表示上一級目錄（父目錄）。

• 示例 4：
  輸入：path = “/…/”
  輸出：“/”
  解釋：
  不可能從根目錄上升一級目錄。

• 示例 5：
  輸入：path = “/…/a/…/b/c/…/d/./”
  輸出：“/…/b/d”
  解釋：
  “…” 在這個問題中是一個合法的目錄名。

• 提示：
  1 <= path.length <= 3000
  path 由英文字母，數字，‘.’，‘/’ 或 ‘_’ 組成。
  path 是一個有效的 Unix 風格絕對路徑。

題型

1. 核心思想：該題使用棧（Stack）這種數據結構來模擬路徑的遍歷和回退過程。
2. 復雜度：時間復雜度是 O(n)，其中 n 是路徑字符串的長度，因為我們需要遍歷整個字符串。空間復雜度也是 O(n)，因為我們需要存儲路徑的有效部分。
3. c++ 實現算法：

class Solution {
public:std::string simplifyPath(std::string path) {std::vector<std::string> stack;//定義一個棧//創建了一個 std::stringstream 對象 ss，并將字符串 path 作為其初始內容。//這樣做的目的是為了方便地對路徑字符串進行分割和讀取操作。std::stringstream ss(path);//dir 用于存儲從 stringstream 中讀取的每個目錄std::string dir;//使用 getline 函數從 stringstream 中按 / 分割讀取路徑的每個部分，直到沒有更多內容可讀。while (getline(ss, dir, '/')) {//如果目錄為空字符串或為 "."，表示當前目錄，不做任何操作，繼續下一次循環。if (dir.empty() || dir == ".") {continue;}//如果目錄為 ".."，表示返回上一級目錄。如果棧不為空，則彈出棧頂元素（即移除上一級目錄）。else if (dir == "..") {if (!stack.empty()) {stack.pop_back();}}//否則，將該目錄壓入棧中。 else {stack.push_back(dir);}}//初始化一個空字符串 simplified，用于存儲簡化后的路徑。然后遍歷棧中的每個目錄，//將其添加到 simplified 字符串中，并在每個目錄前加上 /。std::string simplified;for (const std::string& d : stack) {simplified += "/" + d;}//simplified 為空字符串，說明路徑簡化后是一個根目錄，返回 /。否則，返回 simplified。return simplified.empty() ? "/" : simplified;}
};

4. 算法推演：

• 初始化
  stack：[]
  ss：/a/./b/…/…/c/

• 遍歷路徑

  • 讀取第一個部分：“”
    空字符串，忽略。
    stack：[]

  • 讀取第二個部分：“a”
    將 “a” 壓入棧。
    stack：[“a”]

  • 讀取第三個部分：“.”
    當前目錄，忽略。
    stack：[“a”]

  • 讀取第四個部分：“b”
    將 “b” 壓入棧。
    stack：[“a”, “b”]

  • 讀取第五個部分：“…”
    返回上一級目錄，彈出棧頂元素 “b”。
    stack：[“a”]

  • 讀取第六個部分：“…”
    返回上一級目錄，彈出棧頂元素 “a”。
    stack：[]

  • 讀取第七個部分：“c”
    將 “c” 壓入棧。
    stack：[“c”]

• 構建簡化后的路徑
  初始化 simplified：“”
  遍歷棧中的每個目錄，將其添加到 simplified 字符串中，并在每個目錄前加上 /。
  simplified：“/c”

• 返回結果
  simplified 不為空，返回 “/c”

• 最終結果
  簡化后的路徑為：“/c”

5. c++ 完整demo：

#include <iostream>
#include <vector>
#include <string>
#include <sstream>class Solution {
public:std::string simplifyPath(std::string path) {std::vector<std::string> stack;//定義一個棧//創建了一個 std::stringstream 對象 ss，并將字符串 path 作為其初始內容。//這樣做的目的是為了方便地對路徑字符串進行分割和讀取操作。std::stringstream ss(path);//dir 用于存儲從 stringstream 中讀取的每個目錄std::string dir;//使用 getline 函數從 stringstream 中按 / 分割讀取路徑的每個部分，直到沒有更多內容可讀。while (getline(ss, dir, '/')) {//如果目錄為空字符串或為 "."，表示當前目錄，不做任何操作，繼續下一次循環。if (dir.empty() || dir == ".") {continue;}//如果目錄為 ".."，表示返回上一級目錄。如果棧不為空，則彈出棧頂元素（即移除上一級目錄）。else if (dir == "..") {if (!stack.empty()) {stack.pop_back();}}//否則，將該目錄壓入棧中。 else {stack.push_back(dir);}}//初始化一個空字符串 simplified，用于存儲簡化后的路徑。然后遍歷棧中的每個目錄，//將其添加到 simplified 字符串中，并在每個目錄前加上 /。std::string simplified;for (const std::string& d : stack) {simplified += "/" + d;}//simplified 為空字符串，說明路徑簡化后是一個根目錄，返回 /。否則，返回 simplified。return simplified.empty() ? "/" : simplified;}
};int main() {Solution solution;std::string path = "/home//foo/";std::string simplifiedPath = solution.simplifyPath(path);std::cout << "Simplified Path: " << simplifiedPath << std::endl;return 0;
}