2024-07-10|閱讀時間 ‧ 約 24 分鐘

情境模擬: 資料夾深度 Crawler Log Folder_Leetcode #1598

題目敘述 Crawler Log Folder

題目給定一串目錄進出的操作指令,請問所有指令完成後,回到根目錄需要幾個步驟?

../ 代表回到上一層目錄
./ 代表留在目前的目錄
x/ 代表前往名稱為x的子目錄

測試範例

Example 1:


Input: logs = ["d1/","d2/","../","d21/","./"]
Output: 2
Explanation: Use this change folder operation "../" 2 times and go back to the main folder.


Example 2:


Input: logs = ["d1/","d2/","./","d3/","../","d31/"]
Output: 3


Example 3:

Input: logs = ["d1/","../","../","../"]
Output: 0

約束條件

Constraints:

  • 1 <= logs.length <= 10^3

指令的數量介於1~1000個

  • 2 <= logs[i].length <= 10

每個指令的長度介於2~10之間

  • logs[i] contains lowercase English letters, digits, '.', and '/'.

指令只會有小寫英文字母、數字、.、斜線

  • logs[i] follows the format described in the statement.

指令都符合題目敘述的指令格式

  • Folder names consist of lowercase English letters and digits.

資料夾名稱只會有小寫英文字母和數字


演算法 模擬法

直接根據每一條指令進行模擬

如果遇到../就回到上一層的目錄,深度-1。

如果遇到./就留在目前目錄,深度不改變。

如果遇到x/就進入到下一層名子為x的子目錄,深度+1。


最後,模擬結束時,深度就是回到根目錄所需要的操作次數。


程式碼 模擬法

class Solution:
def minOperations(self, logs: List[str]) -> int:

level = 0

for command in logs:

if command == "../":

# go backward, up to root(0) at most
level = max(level-1, 0)
elif command != "./":

# go forward
level += 1

return level

複雜度分析

時間複雜度: O(n)

線性掃描每個指令,所需時間為O(n)。

空間複查度: O(1)

所用到的都是固定尺寸的臨時變數,為常數級別O(1)。


Reference

[1] Crawler Log Folder - LeetCode

分享至
成為作者繼續創作的動力吧!
© 2024 vocus All rights reserved.