力扣面试150 简化路径 栈 模拟，力扣面试题 150，简化路径的栈模拟解决方案

摘要：在力扣面试题"简化路径"中，我们需要使用栈来模拟路径的简化过程。题目要求将给定的路径字符串转换为简化后的路径字符串，其中路径字符串包含斜杠分隔的多个部分。通过使用栈来存储路径中的每个部分，我们可以逆序遍历字符串并模拟路径的简化过程。我们可以得到简化后的路径字符串，其中连续的斜杠被替换为单个斜杠。

问题 71：简化路径，给定一个包含"."和"/"的绝对路径，将其转换为规范的简化路径形式，路径 "/a/./b/c/./d/../e/" 应该转换为 "/a/b/c/e/"，假设路径不包含符号 ".."，简化路径意味着删除不必要的分隔符和子目录，并确保以 "/" 开头。

思路

三叶题解：这个问题可以通过使用栈来解决，遍历给定的路径字符串，将每个目录名存储在栈中，如果遇到 "." 则忽略，如果遇到 ".."，则从栈顶移除一个目录（表示返回到上一级目录），将栈中的剩余目录连接起来并返回结果，时间复杂度为 O(n)，空间复杂度也为 O(n)。

代码实现（Python）

以下是使用 Python 实现简化路径的代码：

from collections import deque
class Solution:
    def simplifyPath(self, path):
        stack = deque()  # 使用双端队列模拟栈操作
        path_list = path.split('/')  # 将路径字符串按 "/" 分割成列表形式
        for item in path_list:  # 遍历每个目录名或子目录名
            if item == '.' or len(stack) == 0:  # 如果是 "." 或在根目录下，则忽略该目录名
                continue
            elif item == '..':  # 如果是 ".."，则返回到上一级目录
                if len(stack) > 0:  # 确保不是根目录时才执行返回上一级操作
                    stack.pop()  # 从栈顶移除一个目录名表示返回到上一级目录
            else:  # 其他情况则将目录名压入栈中
                stack.append(item)  # 将目录名压入栈中，模拟进入下级目录的操作
        return '/' + '/'.join(stack)  # 将栈中的目录连接起来并返回结果，确保以 "/" 开头

时间复杂度和空间复杂度分析

时间复杂度为 O(n)，n 是路径字符串的长度，空间复杂度也为 O(n)，因为最坏情况下需要存储所有目录名在栈中。