leetcode1/leetcode 中的 Crawler Log Folder 双解法：用栈与常数空间计数器建模文件系统深度

leetcode1/leetcode 中的 Crawler Log Folder 双解法：用栈与常数空间计数器建模文件系统深度

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode

本篇技术文章基于仓库中的 crawler-log-folder.md，完整讲解 LeetCode 1428 "Crawler in Log"（文件夹中的爬虫）这道题的两类标准解法：栈模拟与深度计数器迭代。读完之后，你不仅能掌握"文件系统路径深度"这类层次化状态的建模方式、两种解法在 9 种语言下的完整可复制实现，还能借助仓库中同构题目的源码，理解"边界钳制"（深度/索引不得越过根节点）这一关键防御性写法。

题目与前置知识

题目的核心设定是：一个文件管理器从主文件夹（main folder）出发，按序执行一组日志操作logs，每条操作有三种形态：

• "../"：移动到上一级父文件夹；
• "./"：停留在当前文件夹（不改变位置）；
• 其他字符串：移动到一个以该字符串命名的子文件夹。

要求返回回到主文件夹所需的最少操作数。原仓库文档列出了动手前应掌握的两项前置能力：

• 栈数据结构（Stack Data Structure）：理解 push/pop 操作，以及栈如何建模嵌套或层次化状态；
• 字符串比较（String Comparison）：通过比较字符串相等性来区分不同的文件夹操作。

需要说明的是，仓库的各语言目录（python/、java/、cpp/等）中并没有 1428 对应的独立解答文件（该仓库的命名规范是"题号-题目标题"，例如 1472-design-browser-history.py 对应 LeetCode 1472），这道题仅由文章系列覆盖，符合 articles/README.md 中"文章需覆盖尽可能多的相关解法并给出时间/空间复杂度"的写作约定。

解法一：栈（Stack）

直觉

文件系统路径可以用栈自然地建模：进入子文件夹就是压栈（push），回到父文件夹就是弹栈（pop），"./"什么都不做。处理完全部日志后，栈的大小恰好表示当前距离主文件夹的深度，也就是回到主文件夹所需的最少操作数——每弹出一个元素对应一次"../"操作。

算法步骤

1. 初始化一个空栈；
2. 对每条日志操作：
   • 若是"../"：栈非空则弹栈（移动到父文件夹）；
   • 若是"./"：不做任何事（停留在当前文件夹）；
   • 否则：将该文件夹名压栈（移动到子文件夹）；
3. 返回栈的大小，即距离主文件夹的深度。

多语言实现

以下实现完整继承自原文档，覆盖 Python、Java、C++、JavaScript、C#、Go、Kotlin、Swift、Rust 九种语言。

Python

class Solution: def minOperations(self, logs: List[str]) -> int: stack = [] for log in logs: if log == "../": if stack: stack.pop() elif log != "./": stack.append(log) return len(stack)

Java

public class Solution { public int minOperations(String[] logs) { Stack<String> stack = new Stack<>(); for (String log : logs) { if (log.equals("../")) { if (!stack.isEmpty()) { stack.pop(); } } else if (!log.equals("./")) { stack.push(log); } } return stack.size(); } }

C++

class Solution { public: int minOperations(vector<string>& logs) { stack<string> st; for (auto& log : logs) { if (log == "../") { if (!st.empty()) { st.pop(); } } else if (log != "./") { st.push(log); } } return st.size(); } };

JavaScript

class Solution { /** * @param {string[]} logs * @return {number} */ minOperations(logs) { let stack = []; for (let log of logs) { if (log === '../') { if (stack.length > 0) { stack.pop(); } } else if (log !== './') { stack.push(log); } } return stack.length; } }

C#

public class Solution { public int MinOperations(string[] logs) { Stack<string> stack = new Stack<string>(); foreach (string log in logs) { if (log == "../") { if (stack.Count > 0) { stack.Pop(); } } else if (log != "./") { stack.Push(log); } } return stack.Count; } }

Go

func minOperations(logs []string) int { stack := []string{} for _, log := range logs { if log == "../" { if len(stack) > 0 { stack = stack[:len(stack)-1] } } else if log != "./" { stack = append(stack, log) } } return len(stack) }

Kotlin

class Solution { fun minOperations(logs: Array<String>): Int { val stack = ArrayDeque<String>() for (log in logs) { if (log == "../") { if (stack.isNotEmpty()) { stack.removeLast() } } else if (log != "./") { stack.addLast(log) } } return stack.size } }

Swift

class Solution { func minOperations(_ logs: [String]) -> Int { var stack = [String]() for log in logs { if log == "../" { if !stack.isEmpty { stack.removeLast() } } else if log != "./" { stack.append(log) } } return stack.count } }

Rust

impl Solution { pub fn min_operations(logs: Vec<String>) -> i32 { let mut stack = Vec::new(); for log in &logs { if log == "../" { if !stack.is_empty() { stack.pop(); } } else if log != "./" { stack.push(log); } } stack.len() as i32 } }

时间与空间复杂度

• 时间复杂度：O(n)，每条日志只做一次 O(1) 的压栈/弹栈；
• 空间复杂度：O(n)，最坏情况下所有操作都是进入子文件夹，栈中保存 n 个元素。

解法二：迭代（深度计数器）

直觉

进一步观察可以发现：我们其实并不需要保存文件夹名，因为最终只关心深度。用一个简单的计数器跟踪当前处于第几层即可——进入子文件夹则计数器加 1，移动到父文件夹则减 1（但不能低于 0，因为不可能越过主文件夹），"./"保持不变。

算法步骤

1. 将深度计数器初始化为0；
2. 对每条日志操作：
   • 若是"./"：跳过（深度不变）；
   • 若是"../"：计数器减 1，但确保不低于0；
   • 否则：计数器加 1（进入子文件夹）；
3. 返回计数器的值，即回到主文件夹的最少操作数。

多语言实现

Python

class Solution: def minOperations(self, logs: List[str]) -> int: res = 0 for log in logs: if log == "./": continue if log == "../": res = max(0, res - 1) else: res += 1 return res

Java

public class Solution { public int minOperations(String[] logs) { int res = 0; for (String log : logs) { if (log.equals("./")) { continue; } if (log.equals("../")) { res = Math.max(0, res - 1); } else { res++; } } return res; } }

C++

class Solution { public: int minOperations(vector<string>& logs) { int res = 0; for (auto& log : logs) { if (log == "./") { continue; } if (log == "../") { res = max(0, res - 1); } else { res++; } } return res; } };

JavaScript

class Solution { /** * @param {string[]} logs * @return {number} */ minOperations(logs) { let res = 0; for (let log of logs) { if (log === './') { continue; } if (log === '../') { res = Math.max(0, res - 1); } else { res++; } } return res; } }

C#

public class Solution { public int MinOperations(string[] logs) { int res = 0; foreach (string log in logs) { if (log == "./") { continue; } if (log == "../") { res = Math.Max(0, res - 1); } else { res++; } } return res; } }

Go

func minOperations(logs []string) int { res := 0 for _, log := range logs { if log == "./" { continue } if log == "../" { if res > 0 { res-- } } else { res++ } } return res }

Kotlin

class Solution { fun minOperations(logs: Array<String>): Int { var res = 0 for (log in logs) { if (log == "./") { continue } if (log == "../") { res = maxOf(0, res - 1) } else { res++ } } return res } }

Swift

class Solution { func minOperations(_ logs: [String]) -> Int { var res = 0 for log in logs { if log == "./" { continue } if log == "../" { res = max(0, res - 1) } else { res += 1 } } return res } }

Rust

impl Solution { pub fn min_operations(logs: Vec<String>) -> i32 { let mut res = 0; for log in &logs { if log == "./" { continue; } if log == "../" { res = 0i32.max(res - 1); } else { res += 1; } } res } }

时间与空间复杂度

• 时间复杂度：O(n)，单次遍历；
• 空间复杂度：O(1)，只使用一个整型计数器，这是该解法相对栈解法的主要优势。

常见陷阱（Common Pitfalls）

原文档专门总结了两个高频错误，这里完整保留并加以展开。

陷阱一：允许深度变为负数

处理"../"时必须保证深度不低于 0。越过主文件夹是不可能的，因此当深度已经为0时再执行减 1 会产生错误结果。

# 错误：深度可能变为负数 if log == "../": depth -= 1 # 正确：钳制在 0 if log == "../": depth = max(0, depth - 1)

栈解法天然免疫这个陷阱——它对"栈是否为空"做了显式判断再弹栈；而计数器解法则必须依赖max(0, ...)（或等价的条件判断，如 Go 版中的if res > 0）来钳制边界。两种写法本质上是同一约束的不同表达。

陷阱二：忘记处理当前目录操作"./"

"./"的语义是"停留在当前文件夹"，不应改变深度。若把它当作普通文件夹名而增加深度，就是典型错误。

# 错误：把 "./" 也当作文件夹处理 if log != "../": depth += 1 # 这会对 "./" 错误地加一 # 正确：显式跳过 "./" if log == "./": continue elif log == "../": depth = max(0, depth - 1) else: depth += 1

仓库佐证：同一个"边界钳制"模式在 Design Browser History 中的复现

从源码结构看，"操作不能越过根节点/首页"这一约束是本仓库中一类反复出现的防御性写法。同仓库的 1472-design-browser-history.py（对应 LeetCode 1472 "Design Browser History"）提供了两种实现，恰好可以和本题对照理解：

• 数组实现：back方法用self.i = max(self.i - steps, 0)把当前索引钳制在 0，保证不会回退到首页之前（见 python/1472-design-browser-history.py#L49-L51）；
• 链表实现：back方法通过while self.cur.prev and steps > 0的循环条件隐式完成同样的边界保护——链表头节点（即首页）的prev为None，自然停止回退（见 python/1472-design-browser-history.py#L18-L22）。

这与本文 Crawler Log Folder 的对应关系非常直接：

可以看出，无论是"栈非空才弹"、"深度钳制在 0"，还是"索引钳制在 0"、"前驱为空即停止"，底层逻辑都是同一条：层次化状态的回退操作必须被根节点截断。掌握这一模式后，面对任何"前进/回退/层级"类题目都能快速写出正确的边界处理。

两种解法的取舍

• 栈解法：语义上更直观，栈内容真实还原了当前路径（如["documents", "snapshot"]），调试与扩展（例如需要输出完整路径）时更有优势，代价是 O(n) 额外空间；
• 计数器解法：在只需要深度数值的本题中更精简，O(1) 空间，是生产代码中"只关心层级数"场景的首选；
• 两者时间复杂度均为 O(n)，实际面试或刷题中推荐先写计数器版本，再说明"若需保留路径则退化为栈"的推广思路。

小结

本文基于 articles/crawler-log-folder.md 完整继承并展开了 Crawler in Log 的两条解题路径：栈模拟（O(n) 空间）与深度计数器（O(1) 空间），保留了 9 种语言的全部可复制实现、复杂度分析与两个常见陷阱的对照代码；并结合仓库中 python/1472-design-browser-history.py 的同构实现，把"回退操作必须被根节点截断"这一通用模式落到具体的源码证据上。相关代码可通过仓库根目录下的语言子目录（如 python/、java/）以及 README.md 中的题解完成度表格继续索引到同系列题目。

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode