What is the optimal approach for the Crawler Log Folder problem?

The optimal approach is to use a stack-based state management system, where we process each log entry and manage the folder depth using push and pop operations.

How does stack-based state management work for this problem?

Stack-based state management works by simulating folder navigation. Each folder is pushed onto the stack, and 'cd ../' pops the last folder. This approach keeps track of the folder depth efficiently.

How can I avoid errors when moving up from the root folder?

To avoid errors, ensure that '../' operations are ignored when the stack is empty (i.e., at the root folder), so the depth remains correct.

What are some edge cases to consider in the Crawler Log Folder problem?

Edge cases include handling operations like multiple '../' when at the root, and ignoring './' operations. These should not affect the stack or depth.

Can this problem be solved in less than O(n) time?

No, due to the need to process each log entry to maintain the correct folder depth, the time complexity must be O(n).

#1598

Easy

auto_awesome栈·状态

LeetCode 题解工作台

文件夹操作日志搜集器

每当用户执行变更文件夹操作时，LeetCode 文件系统都会保存一条日志记录。下面给出对变更操作的说明： "../" ：移动到当前文件夹的父文件夹。如果已经在主文件夹下，则继续停留在当前文件夹。 "./" ：继续停留在当前文件夹。 "x/" ：移动到名为 x 的子文件夹中。题目数据保证总是…

数组字符串栈

题目描述

每当用户执行变更文件夹操作时，LeetCode 文件系统都会保存一条日志记录。

下面给出对变更操作的说明：

"../" ：移动到当前文件夹的父文件夹。如果已经在主文件夹下，则 继续停留在当前文件夹 。
"./" ：继续停留在当前文件夹。
"x/" ：移动到名为 x 的子文件夹中。题目数据 保证总是存在文件夹 x 。

给你一个字符串列表 logs ，其中 logs[i] 是用户在 i^th 步执行的操作。

文件系统启动时位于主文件夹，然后执行 logs 中的操作。

执行完所有变更文件夹操作后，请你找出 返回主文件夹所需的最小步数 。

示例 1：

输入：logs = ["d1/","d2/","../","d21/","./"]
输出：2
解释：执行 "../" 操作变更文件夹 2 次，即可回到主文件夹

示例 2：

输入：logs = ["d1/","d2/","./","d3/","../","d31/"]
输出：3

示例 3：

输入：logs = ["d1/","../","../","../"]
输出：0

提示：

1 <= logs.length <= 10³
2 <= logs[i].length <= 10
logs[i] 包含小写英文字母，数字，'.' 和 '/'
logs[i] 符合语句中描述的格式
文件夹名称由小写英文字母和数字组成

lightbulb

解题思路

方法一：模拟

直接模拟，记录深度的变化即可。

时间复杂度 $O(n)$ ，空间复杂度 $O(1)$ 。其中 $n$ 为 logs 的长度。

1

2

3

4

5

6

7

8

9

10

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

speed

复杂度分析

指标	值
时间	O(n)
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
Candidates may struggle with handling redundant operations like './' and '../'.
question_mark
Watch for efficient stack operations and correct handling of the root folder.
question_mark
Evaluate if the candidate can explain their reasoning for using a stack to manage folder navigation.

warning

常见陷阱

外企场景

error
Failing to handle redundant './' operations.
error
Incorrectly managing folder navigation when attempting to move up from the root folder.
error
Not resetting or updating the stack correctly after each operation.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the problem to support a different folder structure (e.g., nested folders).
arrow_right_alt
Change the operations to include invalid paths and check for error handling.
arrow_right_alt
Add operations that represent folder creation or deletion and track changes accordingly.

help

常见问题

外企场景

继续练习

#2019 解出数学表达式的学生分数 #1604 警告一小时内使用相同员工卡大于等于三次的人 #1614 括号的最大嵌套深度