LeetCode 面試經典 150_棧_簡化路徑（53_71_C++_中等）

  • 題目描述：
  • 輸入輸出樣例：
  • 題解：
  • 解題思路：
  • 思路一（棧+stringstream）：
  • 思路二（棧）：
  • 代碼實現
  • 代碼實現（思路一（棧+stringstream））：
  • 代碼實現（思路二（棧））：
  • 以思路一為例進行調試

題目描述：

給你一個字符串 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 風格絕對路徑。

題解：

解題思路：

思路一（棧+stringstream）：

1、具體思路如下：

  • ‘.’ 返回當前目錄（不處理）
  • ‘…’ 返回上級目錄 (出棧)
  • ‘/’ , ‘///’ 將其看作分隔符
  • 其他情況 入棧

2、複雜度分析：
① 時間複雜度：O(n)，其中 n 是輸入路徑字符串的長度。使用 getline(ss, tmp, ‘/’) 逐部分讀取路徑，這一操作的時間複雜度為 O(n)
② 空間複雜度：O(n)，主要由棧和路徑部分的臨時存儲佔用空間。

思路二（棧）：

1、 棧+不使用stringstream。for循環逐個字符處理，實現按照’/'進行分割的功能。

2、複雜度分析
① 時間複雜度：O(n)，其中 n 是輸入路徑字符串的長度。遍歷一遍路徑字符串。
② 空間複雜度：O(n)，tmp 的空間複雜度為 O(n)，在每次處理路徑部分時，tmp 最多會存儲一部分路徑，長度最多為 n。

代碼實現

代碼實現（思路一（棧+stringstream））：
class Solution1 {
public:
string simplifyPath(string path) {
// 將輸入路徑字符串轉化為字符串流，以便逐部分讀取路徑
stringstream ss(path);
// 使用棧來存儲路徑部分
stack<string> st;
  // 臨時存儲每一部分路徑
  string tmp;
  // 逐部分讀取路徑字符串，分隔符是 '/'
  while (getline(ss, tmp, '/')) {
  // 如果路徑部分是 ".."，則表示返回上一級目錄
  if (tmp == "..") {
  // 棧不為空時彈出棧頂（表示返回上一級目錄）
  if (!st.empty()) {
  st.pop();
  }
  }
  // 如果路徑部分是有效的（非 "." 和非空），則壓入棧中
  else if (!tmp.empty() && tmp != ".") {
  st.push(tmp);
  }
  }
  // 構造最終的簡化路徑
  string ans;
  // 遍歷棧中的路徑部分，將其重新組合為簡化後的路徑
  while (!st.empty()) {
  // 每次彈出棧頂元素，並將其加到結果路徑的前面
  ans = "/" + st.top() + ans;
  st.pop();
  }
  // 如果最終路徑為空，説明路徑是根目錄，返回 "/"
  return ans == "" ? "/" : ans;
  }
  };
代碼實現（思路二（棧））：
class Solution2 {
public:
string simplifyPath(string path) {
// 使用兩個指針遍歷路徑字符串
int n = path.size();
stack<string> st;
  string tmp;
  for (int i = 0; i < n; ++i) {
  // 跳過多餘的 '/'
  if (path[i] == '/') continue;
  // 處理路徑部分
  tmp.clear();
  while (i < n && path[i] != '/') {
  tmp += path[i++];
  }
  if (tmp == "..") {
  if (!st.empty()) {
  st.pop();  // 彈出棧頂（上一級目錄）
  }
  } else if (tmp != "." && !tmp.empty()) {
  st.push(tmp);  // 如果是有效的目錄，加入棧中
  }
  }
  // 拼接最終路徑
  string ans;
  while (!st.empty()) {
  ans = "/" + st.top() + ans;
  st.pop();
  }
  // 如果路徑為空，則返回根目錄 "/"
  return ans.empty() ? "/" : ans;
  }
  };
以思路一為例進行調試
#include<iostream>
  #include<sstream>
    #include<stack>
      using namespace std;
      class Solution1 {
      public:
      string simplifyPath(string path) {
      // 將輸入路徑字符串轉化為字符串流，以便逐部分讀取路徑
      stringstream ss(path);
      // 使用棧來存儲路徑部分
      stack<string> st;
        // 臨時存儲每一部分路徑
        string tmp;
        // 逐部分讀取路徑字符串，分隔符是 '/'
        while (getline(ss, tmp, '/')) {
        // 如果路徑部分是 ".."，則表示返回上一級目錄
        if (tmp == "..") {
        // 棧不為空時彈出棧頂（表示返回上一級目錄）
        if (!st.empty()) {
        st.pop();
        }
        }
        // 如果路徑部分是有效的（非 "." 和非空），則壓入棧中
        else if (!tmp.empty() && tmp != ".") {
        st.push(tmp);
        }
        }
        // 構造最終的簡化路徑
        string ans;
        // 遍歷棧中的路徑部分，將其重新組合為簡化後的路徑
        while (!st.empty()) {
        // 每次彈出棧頂元素，並將其加到結果路徑的前面
        ans = "/" + st.top() + ans;
        st.pop();
        }
        // 如果最終路徑為空，説明路徑是根目錄，返回 "/"
        return ans == "" ? "/" : ans;
        }
        };
        int main(int argc, char const *argv[])
        {
        string path ="/home/user/Documents/../Pictures";
        Solution1 s;
        cout<<s.simplifyPath(path)<<endl;
        return 0;
        }