【栈】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.质量属性 属性说明可用性错误检测/恢复/避免性能资源需求/管理…...
linux之kylin系统nginx的安装
一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源(HTML/CSS/图片等),响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址,提高安全性 3.负载均衡服务器 支持多种策略分发流量…...
【Go】3、Go语言进阶与依赖管理
前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课,做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程,它的核心机制是 Goroutine 协程、Channel 通道,并基于CSP(Communicating Sequential Processes࿰…...
相机从app启动流程
一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...
HBuilderX安装(uni-app和小程序开发)
下载HBuilderX 访问官方网站:https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本: Windows版(推荐下载标准版) Windows系统安装步骤 运行安装程序: 双击下载的.exe安装文件 如果出现安全提示&…...
鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/
使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题:docker pull 失败 网络不同,需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...
JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作
一、上下文切换 即使单核CPU也可以进行多线程执行代码,CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短,所以CPU会不断地切换线程执行,从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...
.Net Framework 4/C# 关键字(非常用,持续更新...)
一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...
稳定币的深度剖析与展望
一、引言 在当今数字化浪潮席卷全球的时代,加密货币作为一种新兴的金融现象,正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而,加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下,稳定…...
九天毕昇深度学习平台 | 如何安装库?
pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子: 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...
NPOI操作EXCEL文件 ——CAD C# 二次开发
缺点:dll.版本容易加载错误。CAD加载插件时,没有加载所有类库。插件运行过程中用到某个类库,会从CAD的安装目录找,找不到就报错了。 【方案2】让CAD在加载过程中把类库加载到内存 【方案3】是发现缺少了哪个库,就用插件程序加载进…...
