題目給定一串目錄進出的操作指令,請問所有指令完成後,回到根目錄需要幾個步驟?
../ 代表回到上一層目錄
./ 代表留在目前的目錄
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.指令都符合題目敘述的指令格式
資料夾名稱只會有小寫英文字母和數字
直接根據每一條指令進行模擬
如果遇到../就回到上一層的目錄,深度-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(1)。