简化路径[中等]

优质博文:IT-BLOG-CN
在这里插入图片描述

一、题目

给你一个字符串path,表示指向某一文件或目录的Unix风格 绝对路径 (以/开头),请你将其转化为更加简洁的规范路径。在Unix风格的文件系统中,一个点.表示当前目录本身;此外,两个点..表示将目录切换到上一级(指向父目录);两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠(即,//)都被视为单个斜杠/ 。 对于此问题,任何其他格式的点(例如,...)均被视为文件/目录名称。

请注意,返回的 规范路径 必须遵循下述格式:
【1】始终以斜杠/开头。
【2】两个目录名之间必须只有一个斜杠/
【3】最后一个目录名(如果存在)不能 以/结尾。
【4】此外,路径仅包含从根目录到目标文件或目录的路径上的目录(即,不含...)。

返回简化后得到的 规范路径。

示例 1:
输入:path = "/home/"
输出:/home
解释:注意,最后一个目录名后面没有斜杠。

示例 2:
输入:path = "/../"
输出:/
解释:从根目录向上一级是不可行的,因为根目录是你可以到达的最高级。

示例 3:
输入:path = "/home//foo/"
输出:/home/foo
解释:在规范路径中,多个连续斜杠需要用一个斜杠替换。

示例 4:
输入:path = "/a/./b/../../c/"
输出:/c

1 <= path.length <= 3000
path由英文字母,数字,‘.’,‘/’ 或 ‘_’ 组成。
path是一个有效的Unix风格绝对路径。

二、代码

栈: 首先将给定的字符串path根据/分割成一个由若干字符串组成的列表,记为paths。根据题目中规定的「规范路径的下述格式」,paths中包含的字符串只能为以下几种:
【1】空字符串。例如当出现多个连续的/,就会分割出空字符串;
【2】一个点.
【3】两个点..
【4】只包含英文字母、数字或_的目录名。

对于「空字符串」以及「一个点」,我们实际上无需对它们进行处理,因为「空字符串」没有任何含义,而「一个点」表示当前目录本身,我们无需切换目录。

对于「两个点」或者「目录名」,我们则可以用一个栈来维护路径中的每一个目录名。当我们遇到「两个点」时,需要将目录切换到上一级,因此只要栈不为空,我们就弹出栈顶的目录。当我们遇到「目录名」时,就把它放入栈。

这样一来,我们只需要遍历paths中的每个字符串并进行上述操作即可。在所有的操作完成后,我们将从栈底到栈顶的字符串用/进行连接,再在最前面加上/表示根目录,就可以得到简化后的规范路径。

class Solution {public String simplifyPath(String path) {if (path == null || path.length() == 0) {return "/";}// 思想:因为有 .. 返回上一层,所以需要通过栈的思想进行处理Deque<String> stack = new LinkedList<>();String[] paths = path.split("/");// 遍历路径:对空字符串和.不进行处理,其它的压入栈,对..进行弹出;for(String p : paths) {if ("..".equals(p)) {if (!stack.isEmpty() ){stack.pollLast();}} else if (p.length() > 0 && !".".equals(p)) {stack.offerLast(p);}}StringBuffer sb = new StringBuffer();if (stack.isEmpty()) {return "/";}while (!stack.isEmpty()) {sb.append("/").append(stack.pollFirst());}return sb.toString();}
}

时间复杂度: O(n),其中n是字符串path的长度。
空间复杂度: O(n)。我们需要O(n)的空间存储names中的所有字符串。

一句话解释: 栈解决,把当前目录压入栈中,遇到…弹出栈顶,最后返回栈中元素.

class Solution:def simplifyPath(self, path: str) -> str:stack = []path = path.split("/")for item in path:if item == "..":if stack : stack.pop()elif item and item != ".":stack.append(item)return "/" + "/".join(stack)

正序遍历,对多种情况先进行判断,再进行字符串拼接

先用“/”分割字符串,再判断每个子串的情况:
是单词就添加进list,是 … 就除去list的末尾元素,其他情况忽略最终用“/”拼接成答案res返回即可

class Solution {public String simplifyPath(String path) {List<String> list = new ArrayList<>();String[] split = path.split("/");for (int i = 0; i < split.length; i++) {if (split[i].equals(".") || split[i].isEmpty()){continue;} else if (split[i].equals("..")) {if (!list.isEmpty())list.remove(list.size()-1);}else {list.add(split[i]);}}StringBuilder res = new StringBuilder();for (int i = 0; i < list.size(); i++) {res.append("/").append(list.get(i));}return !res.toString().isEmpty() ? res.toString() : "/";}
}

时间复杂度: O(n),其中n是字符串path的长度。
空间复杂度: O(n)。我们需要O(n)的空间存储names中的所有字符串。

模拟:根据题意,使用栈进行模拟即可。

具体的,从前往后处理path,每次以item为单位进行处理(有效的文件名),根据item为何值进行分情况讨论:

item为有效值 :存入栈中;
item为 … :弹出栈顶元素(若存在);
item为 . :不作处理。

class Solution {public String simplifyPath(String path) {Deque<String> d = new ArrayDeque<>();int n = path.length();for (int i = 1; i < n; ) {if (path.charAt(i) == '/' && ++i >= 0) continue;int j = i + 1;while (j < n && path.charAt(j) != '/') j++;String item = path.substring(i, j);if (item.equals("..")) {if (!d.isEmpty()) d.pollLast();} else if (!item.equals(".")) {d.addLast(item);}i = j;}StringBuilder sb = new StringBuilder();while (!d.isEmpty()) sb.append("/" + d.pollFirst());return sb.length() == 0 ? "/" : sb.toString();}
}

时间复杂度: O(n),其中n是字符串path的长度。
空间复杂度: O(n)。我们需要O(n)的空间存储names中的所有字符串。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/328705.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

vue3 自定义组件

在项目中&#xff0c;我们会遇到一些没有现成的组件&#xff0c;那这个时候我们就需要自己去写一个满足我们需求的组件。 比如&#xff0c;我需要一个上下排布&#xff0c;上面显示标题&#xff0c;下面显示内容的组件。封装完成后方便复用。 1、布局组件 我定义一个上下结构的…

2024生日快乐祝福HTML源码

源码介绍 2024生日快乐祝福HTML源码&#xff0c;源码由HTMLCSSJS组成&#xff0c;记事本打开源码文件可以进行内容文字之类的修改&#xff0c;双击html文件可以本地运行效果&#xff0c;也可以上传到服务器里面&#xff0c; 源码截图 源码下载 2024生日快乐祝福HTML源码

Gradio 案例——将 dicom 文件转为 nii文件

文章目录 Gradio 案例——将 dicom 文件转为 nii文件界面截图依赖安装项目目录结构代码 Gradio 案例——将 dicom 文件转为 nii文件 利用 SimpleITK 库&#xff0c;将 dicom 文件转为 nii文件更完整、丰富的示例项目见 GitHub - AlionSSS/dcm2niix-webui: The web UI for dcm2…

一种请求头引起的跨域问题记录(statusCode = 400/CORS)

问题表象 问题描述 当我们需要在接口的headers中添加一个自定义的变量的时候&#xff0c;前端的处理是直接在拦截器或者是接口配置的地方直接进行写&#xff0c;比如下面的这段比较基础的写法&#xff1a; $http({method: "post",url:constants.backend.SERVER_LOGIN…

selenium发展史

Selenium Core 2004 年&#xff0c;Thoughtworks 的工程师 Jason Huggins 正在负责一个 Web 应用的测试工作&#xff0c;由于这个项目需要频繁回归&#xff0c;这导致他不得不每天做着重复且低效的工作。为了解决这个困境&#xff0c;Jason 开发了一个运行在 JavaScript 沙箱中…

React框架-Next 学习-1

创建一个 Next.js 应用,node版本要高&#xff0c;16.5以上 npm淘宝镜像切为https://registry.npmmirror.com npm config set registry https://registry.npmmirror.com npx create-next-applatest//安装后 使用npm run dev 启动 Next.js 是围绕着 页面&#xff08;pages&am…

我21岁玩“撸货”,被骗1000多万

最近&#xff0c;撸货业界内发生了一些颇受瞩目的事件。 在郑州&#xff0c;数码档口下面抢手团长跑路失联&#xff0c;涉及金额几百万&#xff0c;在南京&#xff0c;一家知名的电商平台下的收货站点突然失联&#xff0c;涉及金额高达一千多万&#xff0c;令众多交易者震惊不已…

回归预测 | Matlab实现GA-LSSVM遗传算法优化最小二乘支持向量机多输入单输出回归预测

回归预测 | Matlab实现GA-LSSVM遗传算法优化最小二乘支持向量机多输入单输出回归预测 目录 回归预测 | Matlab实现GA-LSSVM遗传算法优化最小二乘支持向量机多输入单输出回归预测预测效果基本介绍模型描述程序设计参考资料 预测效果 基本介绍 Matlab实现GA-LSSVM遗传算法优化最小…

基于 Spring Boot 博客系统开发(十)

基于 Spring Boot 博客系统开发&#xff08;十&#xff09; 本系统是简易的个人博客系统开发&#xff0c;为了更加熟练地掌握 SprIng Boot 框架及相关技术的使用。&#x1f33f;&#x1f33f;&#x1f33f; 基于 Spring Boot 博客系统开发&#xff08;九&#xff09;&#x1f…

【考研数学】张宇《1000题》强化阶段正确率多少算合格?

张宇1000题真的很练人心态.... 基础不好&#xff0c;建议别碰1000题 基础好&#xff0c;1000题建议在两个月以内刷完 如果自己本身在基础阶段学的比较水&#xff0c;自己的薄弱点刷了一小部分题没有针对性完全解决&#xff0c;转身去刷1000题就会发现&#xff0c;会的题目刷…

算术平均数

算术平均数&#xff08;average&#xff09;是一组数据相加后除以数据的个数而得到的结果&#xff0c;是度量数据水平的常用统计量&#xff0c;在参数估计和假设检验中经常用到。比如&#xff1a;用职工平均工资来衡量职工工资的一般水平&#xff0c;用平均体重来观察某一人群体…

通信指挥类装备(多链路聚合设备)-应急通信指挥解决方案

现场通信指挥系统是一种功能全面的便携式音视频融合指挥通信平台&#xff0c;可实现现场应急救援指挥、多种通信手段融合、现场通信组网等功能&#xff0c;是现场指挥系统的延伸。 多链路聚合设备&#xff0c;是一款通信指挥类装备&#xff0c;具有 4G/5G&#xff0c;专网&…

YOLOv8训练流程-原理解析[目标检测理论篇]

关于YOLOv8的主干网络在YOLOv8网络结构介绍-CSDN博客介绍了&#xff0c;为了更好地学习本章内容&#xff0c;建议先去看预测流程的原理分析YOLOv8原理解析[目标检测理论篇]-CSDN博客&#xff0c;再次把YOLOv8网络结构图放在这里&#xff0c;方便随时查看。 ​ 1.前言 YOLOv8训练…

《ESP8266通信指南》17-结尾篇(完结撒花)

《ESP8266通信指南》16-MQTT收发通信-完整代码-&#xff08;Lua烧录代码的深度思考与串口拦截&#xff09;-CSDN博客 《ESP8266通信指南》系列的第十六篇&#xff0c;专注于MQTT收发通信的完整代码以及深度思考与串口拦截。本小节首先列出了往期内容&#xff0c;然后提出了本节…

哈希表的理解和实现

目录 1. 哈希的概念 (是什么) 2. 实现哈希的两种方式 (哈希函数) 2.1. 直接定址法 2.2. 除留余数法 2.2.1. 哈希冲突 3. 补充知识 3.1. 负载因子 3.2. 线性探测和二次探测 4. 闭散列实现哈希表 (开放定址法) 4.1. 开放定址法的实现框架 4.2. Xq::hash_table::insert…

今天遇到一个GPT解决不了的问题

问题描述 你好&#xff0c;postman的一个post请求&#xff0c;编辑器里面放了一个很长的json数据&#xff0c;报Tokenization is skipped for long lines for performance reasons. This can be configured via editor.maxTokenizationLineLength.&#xff0c;但是同样的数据&a…

家用充电桩远程监控安全管理系统解决方案

家用充电桩远程监控安全管理系统解决方案 在当今电动汽车日益普及的背景下&#xff0c;家用充电桩的安全管理成为了广大车主关注的重点问题。为了实现对充电桩的高效、精准、远程监控&#xff0c;一套完善的家用充电桩远程监控安全管理系统解决方案应运而生。本方案旨在通过先…

AI 绘画神器 Fooocus 图生图:图像放大或变化、图像提示、图像重绘或扩充、反推提示词、生成参数提取、所需模型下载

本文收录于《AI绘画从入门到精通》专栏&#xff0c;专栏总目录&#xff1a;点这里&#xff0c;订阅后可阅读专栏内所有文章。 大家好&#xff0c;我是水滴~~ 本文讲述 Fooocus 的图生图功能&#xff0c;主要内容包括&#xff1a;图像放大或变化、图像提示、图像重绘或扩充、反推…

深入理解MySQL三大日志:redo log、binlog、undo log

前言 MySQL是一个功能强大的关系型数据库管理系统&#xff0c;它的高可靠性、高性能和易用性使得它成为众多企业和开发者的首选。在MySQL内部&#xff0c;为了保证数据的完整性、恢复能力和并发性能&#xff0c;设计了一套复杂的日志系统。其中&#xff0c;redo log、bin log和…

Qt+C++串口调试工具

程序示例精选 QtC串口调试工具 如需安装运行环境或远程调试&#xff0c;见文章底部个人QQ名片&#xff0c;由专业技术人员远程协助&#xff01; 前言 这篇博客针对《QtC串口调试工具》编写代码&#xff0c;代码整洁&#xff0c;规则&#xff0c;易读。 学习与应用推荐首选。 …