🔗 🟢 1598. Crawler Log Folder 1297

tags: `Week Contest 208` `陣列(Array)` `字串(String)` `堆疊(Stack)`

題意

有一個檔案系統會在每次使用者執行「切換資料夾」操作時保存一個記錄檔。

操作的說明如下：

"../"：移動到目前資料夾的上一層資料夾。（如果已經在主資料夾，則停留在同一個資料夾。）
"./"：保持在同一個資料夾。
"x/"：移動到名為 x 的子資料夾。（這個資料夾保證存在。）

給定一個字串列表 $\text{logs}$ ，其中 $\text{logs}[i]$ 表示使用者在第 $i$ 步執行的操作。

檔案系統從主資料夾開始，然後執行 $\text{logs}$ 中的操作。

返回執行完所有切換資料夾的操作後，回到主資料夾最少所需要執行的操作次數。

思路：維護當前資料夾深度

根據題意，我們只在意最終資料夾的深度，而不需要真正模擬整個切換資料夾的過程。因此，我們可以維護一個變數 $\textit{ans}$ 來記錄當前資料夾的深度，並根據每個操作更新它。

如果操作是 "./"，表示保持在同一個資料夾，不需要做任何操作，因此 $\textit{ans}$ 不變。
如果操作是 "../"，表示移動到上一層資料夾，此時需要將 $\textit{ans}$ 減 1。但如果此時 $\textit{ans}$ 已經是 0，表示已經在主資料夾了，所以 $\textit{ans}$ 保持不變。
如果操作是 "x/"，表示移動到子資料夾 x，此時需要將 $\textit{ans}$ 增加 1。

最終的 $\textit{ans}$ 即為執行完所有操作後，回到主資料夾最少所需要執行的操作次數。

複雜度分析

時間複雜度: $\mathcal{O}(n)$ ，其中 $n$ 是 $\text{logs}$ 的長度。
空間複雜度: $\mathcal{O}(1)$ 。

class Solution:
    def minOperations(self, logs: List[str]) -> int:
        ans = 0
        for log in logs:
            if log == "./":
                continue
            elif log == "../":
                ans = max(ans - 1, 0)
            else:
                ans += 1
        return ans

class Solution {
public:
    int minOperations(vector<string>& logs) {
        int ans = 0;
        for (auto& log : logs) {
            if (log == "./") continue;
            if (log == "../") ans = max(ans - 1, 0);
            else ans++;
        }
        return ans;
    }
};