掌握Unix路径简化:五种有效算法比较【python力扣71题】

本文涉及的产品
全局流量管理 GTM,标准版 1个月
云解析 DNS,旗舰版 1个月
公共DNS(含HTTPDNS解析),每月1000万次HTTP解析
简介: 掌握Unix路径简化:五种有效算法比较【python力扣71题】

作者介绍:10年大厂数据\经营分析经验,现任大厂数据部门负责人。

会一些的技术:数据分析、算法、SQL、大数据相关、python

欢迎加入社区:码上找工作

作者专栏每日更新:

LeetCode解锁1000题: 打怪升级之旅

python数据分析可视化:企业实战案例

备注说明:方便大家阅读,统一使用python,带必要注释,公众号 数据分析螺丝钉 一起打怪升级

题目描述

给你一个字符串 path,表示一个 Unix 风格的绝对路径,请你简化它并返回。

Unix 风格的绝对路径中,.. 表示返回上一级目录,. 表示当前目录。简化路径必须始终以斜杠 / 开头,并且两个目录名之间必须只有一个斜杠 /。最后一个目录名(如果存在)不能以 / 结尾。此外,简化的路径必须是表示绝对路径的最短字符串。

输入格式
  • path:一个字符串,表示 Unix 风格的路径。
输出格式
  • 返回一个字符串,表示简化后的路径。

示例

示例 1
输入: path = "/home/"
输出: "/home"
解释: "/home" 和 "/." 本质上是一样的,前者是简化的路径。
示例 2
输入: path = "/../"
输出: "/"
解释: "/../" 将会移到根目录。

方法一:使用栈

解题步骤
  1. 分割路径:使用 / 将路径分割成部分。
  2. 处理每部分:使用栈来处理每一部分。
  • 如果是 ..,则弹出栈(如果栈不为空)。
  • 如果是有效的路径名(非空且不是 .),则压入栈。
  1. 构建最终路径:从栈中弹出所有元素来构建最终的路径。
完整的规范代码
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)),使用了栈来存储路径的各个部分。

方法二:直接解析

解题步骤
  1. 遍历和解析:直接在遍历过程中处理路径。
  2. 应用路径规则:同方法一,直接处理和压栈。
完整的规范代码
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("/../"))    # 输出: "/"

方法三:递归

解题步骤
  1. 定义递归函数:递归地处理路径,将路径分解为头部和尾部。
  2. 递归简化:根据头部处理剩余的路径。
完整的规范代码
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("/../"))    # 输出: "/"

方法四:正则表达式

解题步骤
  1. 正则匹配:使用正则表达式来提取所有有效的路径部分。
  2. 重建路径:根据提取的路径部分重建整个路径。
完整的规范代码
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("/../"))    # 输出: "/"

方法五:解析并反向处理

解题步骤
  1. 反向解析:从路径末尾开始解析,使用栈处理逻辑。
  2. 重建路径:根据处理结果重建路径。
完整的规范代码
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 中解析出相对路径,并将其转换为服务器上的绝对路径。使用这些方法可以防止路径遍历攻击,确保服务器的安全。

通过选择适合的路径解析算法,可以提高软件的性能和安全性,同时提供更好的用户体验。

欢迎关注微信公众号 数据分析螺丝钉

相关文章
|
1月前
|
机器学习/深度学习 人工智能 算法
基于Python深度学习的眼疾识别系统实现~人工智能+卷积网络算法
眼疾识别系统,本系统使用Python作为主要开发语言,基于TensorFlow搭建卷积神经网络算法,并收集了4种常见的眼疾图像数据集(白内障、糖尿病性视网膜病变、青光眼和正常眼睛) 再使用通过搭建的算法模型对数据集进行训练得到一个识别精度较高的模型,然后保存为为本地h5格式文件。最后使用Django框架搭建了一个Web网页平台可视化操作界面,实现用户上传一张眼疾图片识别其名称。
125 5
基于Python深度学习的眼疾识别系统实现~人工智能+卷积网络算法
|
2月前
|
机器学习/深度学习 人工智能 算法
猫狗宠物识别系统Python+TensorFlow+人工智能+深度学习+卷积网络算法
宠物识别系统使用Python和TensorFlow搭建卷积神经网络,基于37种常见猫狗数据集训练高精度模型,并保存为h5格式。通过Django框架搭建Web平台,用户上传宠物图片即可识别其名称,提供便捷的宠物识别服务。
345 55
|
2月前
|
存储 缓存 监控
局域网屏幕监控系统中的Python数据结构与算法实现
局域网屏幕监控系统用于实时捕获和监控局域网内多台设备的屏幕内容。本文介绍了一种基于Python双端队列(Deque)实现的滑动窗口数据缓存机制,以处理连续的屏幕帧数据流。通过固定长度的窗口,高效增删数据,确保低延迟显示和存储。该算法适用于数据压缩、异常检测等场景,保证系统在高负载下稳定运行。 本文转载自:https://www.vipshare.com
131 66
|
3天前
|
监控 算法 安全
内网桌面监控软件深度解析:基于 Python 实现的 K-Means 算法研究
内网桌面监控软件通过实时监测员工操作,保障企业信息安全并提升效率。本文深入探讨K-Means聚类算法在该软件中的应用,解析其原理与实现。K-Means通过迭代更新簇中心,将数据划分为K个簇类,适用于行为分析、异常检测、资源优化及安全威胁识别等场景。文中提供了Python代码示例,展示如何实现K-Means算法,并模拟内网监控数据进行聚类分析。
26 10
|
21天前
|
存储 算法 安全
控制局域网上网软件之 Python 字典树算法解析
控制局域网上网软件在现代网络管理中至关重要,用于控制设备的上网行为和访问权限。本文聚焦于字典树(Trie Tree)算法的应用,详细阐述其原理、优势及实现。通过字典树,软件能高效进行关键词匹配和过滤,提升系统性能。文中还提供了Python代码示例,展示了字典树在网址过滤和关键词屏蔽中的具体应用,为局域网的安全和管理提供有力支持。
49 17
|
3月前
|
搜索推荐 Python
利用Python内置函数实现的冒泡排序算法
在上述代码中,`bubble_sort` 函数接受一个列表 `arr` 作为输入。通过两层循环,外层循环控制排序的轮数,内层循环用于比较相邻的元素并进行交换。如果前一个元素大于后一个元素,就将它们交换位置。
155 67
|
3月前
|
存储 搜索推荐 Python
用 Python 实现快速排序算法。
快速排序的平均时间复杂度为$O(nlogn)$,空间复杂度为$O(logn)$。它在大多数情况下表现良好,但在某些特殊情况下可能会退化为最坏情况,时间复杂度为$O(n^2)$。你可以根据实际需求对代码进行调整和修改,或者尝试使用其他优化策略来提高快速排序的性能
152 61
|
3月前
|
算法 数据安全/隐私保护 开发者
马特赛特旋转算法:Python的随机模块背后的力量
马特赛特旋转算法是Python `random`模块的核心,由松本真和西村拓士于1997年提出。它基于线性反馈移位寄存器,具有超长周期和高维均匀性,适用于模拟、密码学等领域。Python中通过设置种子值初始化状态数组,经状态更新和输出提取生成随机数,代码简单高效。
140 63
|
2月前
|
机器学习/深度学习 人工智能 算法
【宠物识别系统】Python+卷积神经网络算法+深度学习+人工智能+TensorFlow+图像识别
宠物识别系统,本系统使用Python作为主要开发语言,基于TensorFlow搭建卷积神经网络算法,并收集了37种常见的猫狗宠物种类数据集【'阿比西尼亚猫(Abyssinian)', '孟加拉猫(Bengal)', '暹罗猫(Birman)', '孟买猫(Bombay)', '英国短毛猫(British Shorthair)', '埃及猫(Egyptian Mau)', '缅因猫(Maine Coon)', '波斯猫(Persian)', '布偶猫(Ragdoll)', '俄罗斯蓝猫(Russian Blue)', '暹罗猫(Siamese)', '斯芬克斯猫(Sphynx)', '美国斗牛犬
220 29
【宠物识别系统】Python+卷积神经网络算法+深度学习+人工智能+TensorFlow+图像识别
|
2月前
|
算法 网络协议 Python
探秘Win11共享文件夹之Python网络通信算法实现
本文探讨了Win11共享文件夹背后的网络通信算法,重点介绍基于TCP的文件传输机制,并提供Python代码示例。Win11共享文件夹利用SMB协议实现局域网内的文件共享,通过TCP协议确保文件传输的完整性和可靠性。服务器端监听客户端连接请求,接收文件请求并分块发送文件内容;客户端则连接服务器、接收数据并保存为本地文件。文中通过Python代码详细展示了这一过程,帮助读者理解并优化文件共享系统。

热门文章

最新文章