文件夹操作日志搜集器

标签: 栈 数组 字符串

难度: Easy

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

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

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

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

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

Submission

运行时间: 25 ms

内存: 16.2 MB

class Solution:
    def minOperations(self, logs: List[str]) -> int:
        # num = 0
        # for i in logs:
        #     if i == '../':
        #         if num != 0:
        #             num -= 1
        #     elif i == './':
        #         continue
        #     else:
        #         num += 1
        # return num

        depth = 0
        for log in logs:
            if log == "./":
                continue
            if log != "../":
                depth += 1
            elif depth:
                depth -= 1
        return depth

Explain

题解的思路是模拟用户的文件夹访问过程。使用一个变量depth表示当前用户在文件夹结构中的深度，初始时深度为0，即在主文件夹。遍历logs中的每一个操作，根据操作的类型更新depth的值。如果操作是'./'，则用户保持在当前文件夹，不改变depth。如果操作是'../'，且depth大于0，表示用户可以向上返回父文件夹，此时depth减1。如果操作是某个文件夹如'x/'，则depth加1，表示用户进入了一个新的子文件夹。最终，depth的值表示用户需要进行的最小返回步数，以回到主文件夹。

时间复杂度: O(n)

空间复杂度: O(1)

# 类定义

class Solution:
    def minOperations(self, logs: List[str]) -> int:
        depth = 0  # 当前深度，0表示在主文件夹
        for log in logs:
            if log == "./":  # 当前文件夹操作，无需改变深度
                continue
            if log == "../":  # 返回上级文件夹
                if depth > 0:  # 只有当不在根目录时可以返回
                    depth -= 1
            else:  # 进入一个新的文件夹
                depth += 1
        return depth  # 返回需要返回到主文件夹的最小步数

Explore

在当前的题解实现中，并没有显示地验证命令格式的正确性或检查文件夹路径是否存在。题目假设了所有的输入都是有效的。在实际应用中，如果需要处理不确定的输入，可以在处理日志之前增加对每个操作的验证，例如检查操作是否符合已定义的模式（如 './', '../', 或 '<folder>/'），并且可以使用异常处理来处理任何不符合预期的操作。

在题解中，当操作为'../'且当前深度（depth）为0时，代码确实保持depth不变。这符合现实世界的文件系统逻辑，其中用户无法从根目录再向上一级，因此在这种情况下尝试退回上一级目录是无效的操作。

在文件系统中，用户不能从根目录（主文件夹）再向上移动到更上一级的目录，因为根目录是最顶层的目录。在这个模拟中，将depth设为0表示用户在根目录。因此，只有当用户已经在子目录中（即depth大于0）时，使用'../'操作才会使用户返回到上一级目录。这种处理方式防止了用户在文件系统中进行无效的目录切换，符合实际的文件系统行为。

在当前的实现中，该算法的时间复杂度是O(n)，其中n是logs数组的长度。这意味着算法的性能与输入的大小成线性关系，这对于大多数用例来说是可接受的。然而，如果输入极其庞大，我们可以考虑一些优化策略，例如并行处理日志条目，或者使用更高效的数据结构来存储和访问日志。不过，这些优化可能需要更复杂的程序设计，并且可能并不总是必要的，取决于具体的应用场景和性能要求。