Easy

题目描述

Leetcode 文件系统会在每次用户执行变更文件夹操作时保持日志记录。

操作说明如下：

  • "../" : 移动到当前文件夹的父文件夹。（如果已经在主文件夹中，则继续留在当前文件夹）
  • "./" : 继续留在当前文件夹
  • "x/" : 移动到名为 x 的子文件夹（该文件夹保证总是存在）

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

文件系统从主文件夹开始，然后执行 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] 遵循语句中描述的格式
  • 文件夹名称由小写英文字母和数字组成

提示：

  • 模拟这个过程，但不要将指针移动到主文件夹之外

解题思路

这道题的核心是模拟文件系统的目录操作过程。我们需要跟踪当前相对于主文件夹的深度。

解题思路：

  1. 计数器方法（推荐）：用一个整数变量记录当前目录深度

    • 遇到 "../" 时，深度减1（但不能小于0，因为不能超出主文件夹）
    • 遇到 "./" 时，深度保持不变
    • 遇到其他操作（进入子文件夹）时，深度加1

  2. 栈模拟方法：用栈来模拟目录结构

    • "../" 对应出栈操作（如果栈非空）
    • "./" 不进行任何操作
    • 其他操作对应入栈

计数器方法更简洁高效，因为我们只关心深度而不需要记录具体的路径信息。算法的时间复杂度为 O(n)，空间复杂度为 O(1)。

最终返回的深度值就是回到主文件夹需要执行的 "../" 操作次数。

代码实现

class Solution {
public:
    int minOperations(vector<string>& logs) {
        int depth = 0;
        
        for (const string& log : logs) {
            if (log == "../") {
                if (depth > 0) {
                    depth--;
                }
            } else if (log == "./") {
                // 保持在当前文件夹，不做任何操作
            } else {
                // 进入子文件夹
                depth++;
            }
        }
        
        return depth;
    }
};

class Solution:
    def minOperations(self, logs: List[str]) -> int:
        depth = 0
        
        for log in logs:
            if log == "../":
                if depth > 0:
                    depth -= 1
            elif log == "./":
                # 保持在当前文件夹，不做任何操作
                pass
            else:
                # 进入子文件夹
                depth += 1
        
        return depth

public class Solution {
    public int MinOperations(string[] logs) {
        int depth = 0;
        
        foreach (string log in logs) {
            if (log == "../") {
                if (depth > 0) {
                    depth--;
                }
            } else if (log == "./") {
                // 保持在当前文件夹，不做任何操作
            } else {
                // 进入子文件夹
                depth++;
            }
        }
        
        return depth;
    }
}

var minOperations = function(logs) {
    let depth = 0;
    
    for (let log of logs) {
        if (log === "../") {
            depth = Math.max(0, depth - 1);
        } else if (log !== "./") {
            depth++;
        }
    }
    
    return depth;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型数值说明
时间复杂度O(n)需要遍历所有日志操作，n 为 logs 数组长度
空间复杂度O(1)只使用常数额外空间存储深度变量

相关题目