題目敘述 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)。
