作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
欢迎加入社区：码上找工作
作者专栏每日更新：
备注说明：方便大家阅读，统一使用python，带必要注释，公众号 数据分析螺丝钉 一起打怪升级
题目描述
给你一个字符串 path，表示一个 Unix 风格的绝对路径，请你简化它并返回。
Unix 风格的绝对路径中，.. 表示返回上一级目录，. 表示当前目录。简化路径必须始终以斜杠 / 开头，并且两个目录名之间必须只有一个斜杠 /。最后一个目录名（如果存在）不能以 / 结尾。此外，简化的路径必须是表示绝对路径的最短字符串。
输入格式
- path：一个字符串，表示 Unix 风格的路径。
输出格式
- 返回一个字符串，表示简化后的路径。
示例
示例 1
输入: path = "/home/" 输出: "/home" 解释: "/home" 和 "/." 本质上是一样的，前者是简化的路径。
示例 2
输入: path = "/../" 输出: "/" 解释: "/../" 将会移到根目录。
方法一：使用栈
解题步骤
- 分割路径：使用
/将路径分割成部分。 - 处理每部分：使用栈来处理每一部分。
- 如果是
..，则弹出栈（如果栈不为空）。 - 如果是有效的路径名（非空且不是
.），则压入栈。
- 构建最终路径：从栈中弹出所有元素来构建最终的路径。
完整的规范代码
def simplifyPath(path): """ 使用栈简化 Unix 风格的绝对路径 :param path: str, 输入的 Unix 风格路径 :return: str, 简化后的路径 """ stack = [] parts = path.split('/') for part in parts: if part == '..': if stack: stack.pop() elif part and part != '.': stack.append(part) return '/' + '/'.join(stack) # 示例调用 print(simplifyPath("/home/")) # 输出: "/home" print(simplifyPath("/../")) # 输出: "/"
算法分析
- 时间复杂度：(O(n))，其中
n是路径的长度。 - 空间复杂度：(O(n))，使用了栈来存储路径的各个部分。
方法二：直接解析
解题步骤
- 遍历和解析：直接在遍历过程中处理路径。
- 应用路径规则：同方法一，直接处理和压栈。
完整的规范代码
def simplifyPath(path): """ 直接解析路径以简化 Unix 风格的绝对路径 :param path: str, 输入的 Unix 风格路径 :return: str, 简化后的路径 """ parts = path.split('/') stack = [] for part in parts: if part == '..': if stack: stack.pop() elif part and part != '.': stack.append(part) return '/' + '/'.join(stack) # 示例调用 print(simplifyPath("/home/")) # 输出: "/home" print(simplifyPath("/../")) # 输出: "/"
方法三：递归
解题步骤
- 定义递归函数：递归地处理路径，将路径分解为头部和尾部。
- 递归简化：根据头部处理剩余的路径。
完整的规范代码
def simplifyPath(path): """ 使用递归简化 Unix 风格的绝对路径 :param path: str, 输入的 Unix 风格路径 :return: str, 简化后的路径 """ def recursive(parts): if not parts: return [] part = parts.pop(0) if part == '..': return recursive(parts) elif part == '.' or not part: return recursive(parts) else: return [part] + recursive(parts) parts = path.split('/') result = recursive(parts) return '/' + '/'.join(result) # 示例调用 print(simplifyPath("/home/")) # 输出: "/home" print(simplifyPath("/../")) # 输出: "/"
方法四：正则表达式
解题步骤
- 正则匹配：使用正则表达式来提取所有有效的路径部分。
- 重建路径：根据提取的路径部分重建整个路径。
完整的规范代码
import re def simplifyPath(path): """ 使用正则表达式简化 Unix 风格的绝对路径 :param path: str, 输入的 Unix 风格路径 :return: str, 简化后的路径 """ parts = re.findall(r'[^/]+', path) stack = [] for part in parts: if part == '..': if stack: stack.pop() elif part != '.': stack.append(part) return '/' + '/'.join(stack) # 示例调用 print(simplifyPath("/home/")) # 输出: "/home" print(simplifyPath("/../")) # 输出: "/"
方法五：解析并反向处理
解题步骤
- 反向解析：从路径末尾开始解析，使用栈处理逻辑。
- 重建路径：根据处理结果重建路径。
完整的规范代码
def simplifyPath(path): """ 反向解析 Unix 风格的绝对路径 :param path: str, 输入的 Unix 风格路径 :return: str, 简化后的路径 """ parts = path.split('/') stack = [] for part in reversed(parts): if part == '..': stack.append(part) elif part and part != '.': if stack and stack[-1] == '..': stack.pop() else: stack.append(part) stack.reverse() return '/' + '/'.join(filter(lambda x: x != '..', stack)) # 示例调用 print(simplifyPath("/home/")) # 输出: "/home" print(simplifyPath("/../")) # 输出: "/"
不同算法的优劣势对比
| 特征 | 方法一：使用栈 | 方法二：直接解析 | 方法三：递归 | 方法四：正则表达式 | 方法五：解析并反向处理 |
| 时间复杂度 | (O(n)) | (O(n)) | (O(n)) | (O(n)) | (O(n)) |
| 空间复杂度 | (O(n)) | (O(n)) | (O(n)) | (O(n)) | (O(n)) |
| 优势 | 明确易懂，逻辑简单 | 同上，代码更简洁 | 递归思想，简洁 | 正则清晰，易维护 | 可处理复杂情况，灵活 |
| 劣势 | 需要额外空间 | 需要处理特殊情况 | 可能栈溢出 | 可能慢于其他方法 | 实现稍复杂 |
应用示例
文件系统工具：在开发文件系统工具（如文件浏览器或命令行工具）时，路径的解析和简化是一个常见需求。例如，在实现 cd 命令或显示当前路径时，需要将用户输入的路径转换为标准化的绝对路径。
Web服务器：在处理静态文件请求时，需要从 URL 中解析出相对路径，并将其转换为服务器上的绝对路径。使用这些方法可以防止路径遍历攻击，确保服务器的安全。
通过选择适合的路径解析算法，可以提高软件的性能和安全性，同时提供更好的用户体验。
欢迎关注微信公众号 数据分析螺丝钉
