【栈】Leetcode 71. 简化路径【中等】
简化路径
-
给你一个字符串 path ,表示指向某一文件或目录的 Unix 风格 绝对路径 (以 ‘/’ 开头),请你将其转化为更加简洁的规范路径。
-
在 Unix 风格的文件系统中,一个点(.)表示当前目录本身;此外,两个点 (…) 表示将目录切换到上一级(指向父目录);两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠(即,‘//’)都被视为单个斜杠 ‘/’ 。 对于此问题,任何其他格式的点(例如,‘…’)均被视为文件/目录名称。
请注意,返回的 规范路径 必须遵循下述格式:
- 始终以斜杠 ‘/’ 开头。
- 两个目录名之间必须只有一个斜杠 ‘/’ 。
- 最后一个目录名(如果存在)不能 以 ‘/’ 结尾。
- 此外,路径仅包含从根目录到目标文件或目录的路径上的目录(即,不含 ‘.’ 或 ‘…’)。
返回简化后得到的 规范路径 。
示例 1:
输入:path = “/home//foo/”
输出:“/home/foo”
解释:在规范路径中,多个连续斜杠需要用一个斜杠替换。
示例 2:
输入:path = “/a/./b/…/…/c/”
输出:“/c”
- 开始路径: /
- 进入目录 a: /a
- 当前目录 .: /a(不变)
- 进入目录 b: /a/b
- 返回上一级目录 …: /a
- 再次返回上一级目录 …: /
- 进入目录 c: /c
- 通过这些步骤,可以看到,所有的部分按顺序处理后,最终简化路径是 /c。
解题思路
-
拆分路径: 使用斜杠 / 将路径字符串拆分为多个部分。
-
使用栈处理路径部分:
-
创建一个栈,用于存储路径中的有效部分。 -
遍历拆分后的路径部分,逐一处理: -
如果部分为空字符串或为 .,则跳过。 -
如果部分为 ..,则弹出栈顶元素(如果栈不为空),表示返回上一级目录。 -
其他情况下,将部分压入栈中,表示进入新的子目录。 -
构建简化后的路径: 使用栈中的部分重新构建简化后的路径,确保路径以 / 开头并且各部分之间只有一个 /。
Java实现
public class SimplifyPath {public String simplifyPath(String path) {// 使用斜杠拆分路径String[] parts = path.split("/");Stack<String> stack = new Stack<>();// 遍历每个部分for (String part : parts) {if (part.equals("") || part.equals(".")) {// 跳过空字符串和 "."continue;} else if (part.equals("..")) {// 弹出栈顶元素,表示返回上一级目录if (!stack.isEmpty()) {stack.pop();}} else {// 其他情况下,将部分压入栈中stack.push(part);}}// 构建简化后的路径StringBuilder simplifiedPath = new StringBuilder();for (String dir : stack) {simplifiedPath.append("/").append(dir);}// 如果简化后的路径为空,返回根目录 "/"return simplifiedPath.length() > 0 ? simplifiedPath.toString() : "/";}public static void main(String[] args) {SimplifyPath sp = new SimplifyPath();System.out.println(sp.simplifyPath("/home/")); // 输出: "/home"System.out.println(sp.simplifyPath("/../")); // 输出: "/"System.out.println(sp.simplifyPath("/home//foo/")); // 输出: "/home/foo"System.out.println(sp.simplifyPath("/a/./b/../../c/")); // 输出: "/c"}
}
时间空间复杂度
- 时间复杂度: O(n),其中 n 是输入路径的长度。拆分路径和遍历路径部分都需要线性时间。
- 空间复杂度: O(n),栈空间在最坏情况下可能需要存储所有路径部分。构建最终简化路径的字符串也需要线性空间。
相关文章:
【栈】Leetcode 71. 简化路径【中等】
简化路径 给你一个字符串 path ,表示指向某一文件或目录的 Unix 风格 绝对路径 (以 ‘/’ 开头),请你将其转化为更加简洁的规范路径。 在 Unix 风格的文件系统中,一个点(.)表示当前目录本身&am…...
简单操作一单利润500+,最新快手缺货赔付玩法,【找店教程+详细教程】
在如今快速变化的时代,寻找充满创新的收入来源已经成为了一种趋势。这不仅是为了实现财务的自由,更是为了在生活中拥有更多的选择权。一项革新的实践——利用手机进行快手缺货赔付单号的操作,已经成为许多人稳定“下车”的一个新途径。 据了…...
【软件设计师】先导
一、考试科目: 上午:计算机与软件工程知识,考试时间150min,75空单选题(不一定一题一空) 下午:软件设计,考试时间150分钟,问答题,6道只做5大题(前四…...
npm : 无法将“npm”项识别为 cmdlet、函数、脚本文件或可运行程序的名称
提示:我解决这个bug跟别人思路可能不太一样,因为我是之前好用,换个项目就不好使了,倦了 文章目录 前言项目场景:解决方案:下载 nvm安装 nvm重新下载所需Node 版本nvm常用命令 前言 提示:这里可…...
如何用 MoonBit 实现 diff?
你使用过 Unix 下的小工具 diff 吗? 没有也没关系,简而言之,它是一个比对两个文本文件之间有什么不同之处的工具。它的作用不止于此,Unix 下还有一个叫 patch 的小工具。 时至今日,很少有人手动为某个软件包打补丁了…...
opencl色域变换,处理传递显存数据
在使用ffmpeg解码后的多路解码数据非常慢,还要给AI做行的加速方式是在显存处理数据,在视频拼接融合产品的产品与架构设计中,提出了比较可靠的方式是使用cuda,那么没有cuda的显卡如何处理呢 ,比较好的方式是使用opencl来…...
COD论文笔记 Boundary-Guided Camouflaged Object Detection
动机 挑战性任务:伪装物体检测(COD)是一个重要且具有挑战性的任务,因为伪装物体往往与背景高度相似,使得准确识别和分割非常困难。现有方法的不足:现有的深度学习方法难以有效识别伪装物体的结构和细节&am…...
java内存模型介绍
Java内存模型(Java Memory Model,JMM)是一种规范,它定义了Java虚拟机(JVM)如何在内存中存储和访问Java对象的方式,以及多个线程如何访问这些对象时的规则。它的主要目标是定义程序中的各个线程如…...
CSS语法介绍
文章目录 前言一、CSS引入方式1.行内操作2.内部操作3.外部操作 二、常用选择器1.标签选择器2.类选择器3.id选择器4.群组选择器5.后代选择器 三、字体常用设置1.字体类型2.字体大小3.字体样式4.字体粗细 四、div盒子模型1.盒子边框2.外边距3.内边距4.浮动 综合实战案例 前言 以…...
Jeecg | 完成配置后,如何启动整个项目?
前端启动步骤: 1. 以管理员身份打开控制台,切换到前端项目目录。 2. 输入 pnpm install 3. 输入 pnpm dev 4. 等待前端成功运行。 可以看到此时前端已经成功启动。 后端启动步骤: 1. 启动 mysql 服务器。 管理员身份打开控制台&#…...
Kubectl 的使用——k8s陈述式资源管理
一、kebuctl简介: kubectl 是官方的CLI命令行工具,用于与 apiserver 进行通信,将用户在命令行输入的命令,组织并转化为 apiserver 能识别的信息,进而实现管理 k8s 各种资源的一种有效途径。 对资源的增、删、查操作比较方便&…...
多天线技术
多天线技术可以分为两类:分集技术和空间复用技术。分集技术利用多天线接收或者发射载有同一信息的信号,提高传输的可靠性。分集技术是将瑞利衰落无线信道换成更加稳定的信道。 发射端未知CSI时的信道容量 发射端已知CSI时的信道容量 信道估计ÿ…...
Meta发布Chameleon模型预览,挑战多模态AI前沿
每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗?订阅我们的简报,深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同,从行业内部的深度分析和实用指南中受益。不要错过这个机会,成为AI领…...
声压级越大,STIPA 越好,公共广播就越清晰吗?
在公共广播中,有些朋友经常问到是不是声压越大,广播清晰度就越高,下面我从搜集了一些专业技术资料,供大家参考。 一、声压级越大,STIPA 越好吗? 不完全是。最初,人们认为当声压级达到 60 dBA 以…...
基于springboot+vue的4S店车辆管理系统
开发语言:Java框架:springbootJDK版本:JDK1.8服务器:tomcat7数据库:mysql 5.7(一定要5.7版本)数据库工具:Navicat11开发软件:eclipse/myeclipse/ideaMaven包:…...
深入理解 HTTP 缓存
浏览器缓存不是本地存储,要分清。浏览器缓存分为强缓存和协商缓存。本篇文章参考:使用 HTTP 缓存防止不必要的网络请求 讲解之前,我画了个简图来解释浏览器从缓存中获取资源的过程。 1. 强缓存 强缓存是浏览器缓存机制中的一种,…...
upload-labs 通关方法
目录 Less-1(JS前端验证) Less-2(MIME验证) Less-3(黑名单,特殊过滤) Less-4(黑名单验证,.htaccess) Less-5(黑名单,点空格点绕过…...
5-26 Cpp学习笔记
1、如果子类实现了基类的函数,返回值、参数都相同,就覆盖了基类的函数。 2、使用作用域解析运算符来调用基类的函数。myDinner.Swim(); —— 调用子类的。myDinner.Fish::Swim(); —— 调用基类的(基类是Fish) 3、在子类中使用关键字using解除对Fish::…...
YOLOv8_pose的训练、验证、预测及导出[关键点检测实践篇]
1.关键点数据集划分和配置 从上面得到的数据还不能够直接训练,需要按照一定的比例划分训练集和验证集,并按照下面的结构来存放数据,划分代码如下所示,该部分内容和YOLOv8的训练、验证、预测及导出[目标检测实践篇]_yolov8训练测试验证-CSDN博客是重复的,代码如下: …...
架构师必考题--软件系统质量属性
软件系统质量属性 1.质量属性2.质量属性场景描述3.系统架构评估 这个知识点是系统架构师必考的题目,也是案例分析题第一题, 有时候会出现在选择题里面,考的分数也是非常高的。 1.质量属性 属性说明可用性错误检测/恢复/避免性能资源需求/管理…...
接口测试中缓存处理策略
在接口测试中,缓存处理策略是一个关键环节,直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性,避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明: 一、缓存处理的核…...
【Python】 -- 趣味代码 - 小恐龙游戏
文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...
【第二十一章 SDIO接口(SDIO)】
第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...
基础测试工具使用经验
背景 vtune,perf, nsight system等基础测试工具,都是用过的,但是没有记录,都逐渐忘了。所以写这篇博客总结记录一下,只要以后发现新的用法,就记得来编辑补充一下 perf 比较基础的用法: 先改这…...
关于 WASM:1. WASM 基础原理
一、WASM 简介 1.1 WebAssembly 是什么? WebAssembly(WASM) 是一种能在现代浏览器中高效运行的二进制指令格式,它不是传统的编程语言,而是一种 低级字节码格式,可由高级语言(如 C、C、Rust&am…...
省略号和可变参数模板
本文主要介绍如何展开可变参数的参数包 1.C语言的va_list展开可变参数 #include <iostream> #include <cstdarg>void printNumbers(int count, ...) {// 声明va_list类型的变量va_list args;// 使用va_start将可变参数写入变量argsva_start(args, count);for (in…...
DiscuzX3.5发帖json api
参考文章:PHP实现独立Discuz站外发帖(直连操作数据库)_discuz 发帖api-CSDN博客 简单改造了一下,适配我自己的需求 有一个站点存在多个采集站,我想通过主站拿标题,采集站拿内容 使用到的sql如下 CREATE TABLE pre_forum_post_…...
Kubernetes 节点自动伸缩(Cluster Autoscaler)原理与实践
在 Kubernetes 集群中,如何在保障应用高可用的同时有效地管理资源,一直是运维人员和开发者关注的重点。随着微服务架构的普及,集群内各个服务的负载波动日趋明显,传统的手动扩缩容方式已无法满足实时性和弹性需求。 Cluster Auto…...
第八部分:阶段项目 6:构建 React 前端应用
现在,是时候将你学到的 React 基础知识付诸实践,构建一个简单的前端应用来模拟与后端 API 的交互了。在这个阶段,你可以先使用模拟数据,或者如果你的后端 API(阶段项目 5)已经搭建好,可以直接连…...
篇章二 论坛系统——系统设计
目录 2.系统设计 2.1 技术选型 2.2 设计数据库结构 2.2.1 数据库实体 1. 数据库设计 1.1 数据库名: forum db 1.2 表的设计 1.3 编写SQL 2.系统设计 2.1 技术选型 2.2 设计数据库结构 2.2.1 数据库实体 通过需求分析获得概念类并结合业务实现过程中的技术需要&#x…...
