1598. 文件夹操作日志搜集器

🟢   🔖  栈 数组 字符串  🔗 力扣 LeetCode

题目

The Leetcode file system keeps a log each time some user performs a change folder operation.

The operations are described below:

• "../" : Move to the parent folder of the current folder. (If you are already in the main folder, remain in the same folder).
• "./" : Remain in the same folder.
• "x/" : Move to the child folder named x (This folder is guaranteed to always exist).

You are given a list of strings logs where logs[i] is the operation performed by the user at the ith step.

The file system starts in the main folder, then the operations in logs are performed.

Return the minimum number of operations needed to go back to the main folder after the change folder operations.

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
• 2 <= logs[i].length <= 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.

题目大意

每当用户执行变更文件夹操作时，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 <= 10^3
• 2 <= logs[i].length <= 10
• logs[i] 包含小写英文字母，数字，'.' 和 '/'
• logs[i] 符合语句中描述的格式
• 文件夹名称由小写英文字母和数字组成

解题思路

本道题不需要显示地维护一个栈，而是可以通过一个数字变量 stack 模拟当前目录深度，根据不同的操作对其进行增减：

• 遇到 "../"：深度减 1，但不能小于 0。
• 遇到 "./"：当前深度保持不变。
• 遇到其他目录：深度加 1。

1. 初始化变量 stack = 0，表示当前深度。

2. 遍历数组 logs，对每个操作进行判断：

   • 如果是 "../"，则减少深度，但使用 Math.max(0, stack - 1) 确保深度不变为负数。
   • 如果是 "./"，跳过，不对深度进行修改。
   • 如果是其他字符串，则增加深度 stack++。

3. 遍历结束后，stack 的值即为最终目录深度。

复杂度分析

• 时间复杂度：O(n)，其中 n 是 logs 的长度，只需要遍历一次 logs。
• 空间复杂度：O(1)，仅使用了一个变量 stack。

代码

/**
 * @param {string[]} logs
 * @return {number}
 */
var minOperations = function (logs) {
	let stack = 0;
	for (let log of logs) {
		if (log === '../') {
			stack = Math.max(0, stack - 1); // 确保目录不会上升到负数
		} else if (log !== './') {
			stack++; // 有效的文件夹操作
		}
	}
	return stack;
};

相关题目

题号	标题	题解	标签	难度	力扣
682	棒球比赛	[✓]	栈 数组 模拟	🟢	🀄️ 🔗
844	比较含退格的字符串	[✓]	栈 双指针 字符串 1+	🟢	🀄️ 🔗