本文主要是介绍掌握Unix路径简化:五种有效算法比较【python力扣71题】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目描述
给你一个字符串 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 redef 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 中解析出相对路径,并将其转换为服务器上的绝对路径。使用这些方法可以防止路径遍历攻击,确保服务器的安全。
通过选择适合的路径解析算法,可以提高软件的性能和安全性,同时提供更好的用户体验。
这篇关于掌握Unix路径简化:五种有效算法比较【python力扣71题】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!