当前位置: 首页 > news >正文

【栈】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 &#xff0c;表示指向某一文件或目录的 Unix 风格 绝对路径 &#xff08;以 ‘/’ 开头&#xff09;&#xff0c;请你将其转化为更加简洁的规范路径。 在 Unix 风格的文件系统中&#xff0c;一个点&#xff08;.&#xff09;表示当前目录本身&am…...

简单操作一单利润500+,最新快手缺货赔付玩法,【找店教程+详细教程】

在如今快速变化的时代&#xff0c;寻找充满创新的收入来源已经成为了一种趋势。这不仅是为了实现财务的自由&#xff0c;更是为了在生活中拥有更多的选择权。一项革新的实践——利用手机进行快手缺货赔付单号的操作&#xff0c;已经成为许多人稳定“下车”的一个新途径。 据了…...

【软件设计师】先导

一、考试科目&#xff1a; 上午&#xff1a;计算机与软件工程知识&#xff0c;考试时间150min&#xff0c;75空单选题&#xff08;不一定一题一空&#xff09; 下午&#xff1a;软件设计&#xff0c;考试时间150分钟&#xff0c;问答题&#xff0c;6道只做5大题&#xff08;前四…...

npm : 无法将“npm”项识别为 cmdlet、函数、脚本文件或可运行程序的名称

提示&#xff1a;我解决这个bug跟别人思路可能不太一样&#xff0c;因为我是之前好用&#xff0c;换个项目就不好使了&#xff0c;倦了 文章目录 前言项目场景&#xff1a;解决方案&#xff1a;下载 nvm安装 nvm重新下载所需Node 版本nvm常用命令 前言 提示&#xff1a;这里可…...

如何用 MoonBit 实现 diff?

你使用过 Unix 下的小工具 diff 吗&#xff1f; 没有也没关系&#xff0c;简而言之&#xff0c;它是一个比对两个文本文件之间有什么不同之处的工具。它的作用不止于此&#xff0c;Unix 下还有一个叫 patch 的小工具。 时至今日&#xff0c;很少有人手动为某个软件包打补丁了…...

opencl色域变换,处理传递显存数据

在使用ffmpeg解码后的多路解码数据非常慢&#xff0c;还要给AI做行的加速方式是在显存处理数据&#xff0c;在视频拼接融合产品的产品与架构设计中&#xff0c;提出了比较可靠的方式是使用cuda&#xff0c;那么没有cuda的显卡如何处理呢 &#xff0c;比较好的方式是使用opencl来…...

COD论文笔记 Boundary-Guided Camouflaged Object Detection

动机 挑战性任务&#xff1a;伪装物体检测&#xff08;COD&#xff09;是一个重要且具有挑战性的任务&#xff0c;因为伪装物体往往与背景高度相似&#xff0c;使得准确识别和分割非常困难。现有方法的不足&#xff1a;现有的深度学习方法难以有效识别伪装物体的结构和细节&am…...

java内存模型介绍

Java内存模型&#xff08;Java Memory Model&#xff0c;JMM&#xff09;是一种规范&#xff0c;它定义了Java虚拟机&#xff08;JVM&#xff09;如何在内存中存储和访问Java对象的方式&#xff0c;以及多个线程如何访问这些对象时的规则。它的主要目标是定义程序中的各个线程如…...

CSS语法介绍

文章目录 前言一、CSS引入方式1.行内操作2.内部操作3.外部操作 二、常用选择器1.标签选择器2.类选择器3.id选择器4.群组选择器5.后代选择器 三、字体常用设置1.字体类型2.字体大小3.字体样式4.字体粗细 四、div盒子模型1.盒子边框2.外边距3.内边距4.浮动 综合实战案例 前言 以…...

Jeecg | 完成配置后,如何启动整个项目?

前端启动步骤&#xff1a; 1. 以管理员身份打开控制台&#xff0c;切换到前端项目目录。 2. 输入 pnpm install 3. 输入 pnpm dev 4. 等待前端成功运行。 可以看到此时前端已经成功启动。 后端启动步骤&#xff1a; 1. 启动 mysql 服务器。 管理员身份打开控制台&#…...

Kubectl 的使用——k8s陈述式资源管理

一、kebuctl简介: kubectl 是官方的CLI命令行工具&#xff0c;用于与 apiserver 进行通信&#xff0c;将用户在命令行输入的命令&#xff0c;组织并转化为 apiserver 能识别的信息&#xff0c;进而实现管理 k8s 各种资源的一种有效途径。 对资源的增、删、查操作比较方便&…...

多天线技术

多天线技术可以分为两类&#xff1a;分集技术和空间复用技术。分集技术利用多天线接收或者发射载有同一信息的信号&#xff0c;提高传输的可靠性。分集技术是将瑞利衰落无线信道换成更加稳定的信道。 发射端未知CSI时的信道容量 发射端已知CSI时的信道容量 信道估计&#xff…...

Meta发布Chameleon模型预览,挑战多模态AI前沿

每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗&#xff1f;订阅我们的简报&#xff0c;深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同&#xff0c;从行业内部的深度分析和实用指南中受益。不要错过这个机会&#xff0c;成为AI领…...

声压级越大,STIPA 越好,公共广播就越清晰吗?

在公共广播中&#xff0c;有些朋友经常问到是不是声压越大&#xff0c;广播清晰度就越高&#xff0c;下面我从搜集了一些专业技术资料&#xff0c;供大家参考。 一、声压级越大&#xff0c;STIPA 越好吗&#xff1f; 不完全是。最初&#xff0c;人们认为当声压级达到 60 dBA 以…...

基于springboot+vue的4S店车辆管理系统

开发语言&#xff1a;Java框架&#xff1a;springbootJDK版本&#xff1a;JDK1.8服务器&#xff1a;tomcat7数据库&#xff1a;mysql 5.7&#xff08;一定要5.7版本&#xff09;数据库工具&#xff1a;Navicat11开发软件&#xff1a;eclipse/myeclipse/ideaMaven包&#xff1a;…...

深入理解 HTTP 缓存

浏览器缓存不是本地存储&#xff0c;要分清。浏览器缓存分为强缓存和协商缓存。本篇文章参考&#xff1a;使用 HTTP 缓存防止不必要的网络请求 讲解之前&#xff0c;我画了个简图来解释浏览器从缓存中获取资源的过程。 1. 强缓存 强缓存是浏览器缓存机制中的一种&#xff0c;…...

upload-labs 通关方法

目录 Less-1&#xff08;JS前端验证&#xff09; Less-2&#xff08;MIME验证&#xff09; Less-3&#xff08;黑名单&#xff0c;特殊过滤&#xff09; Less-4&#xff08;黑名单验证&#xff0c;.htaccess&#xff09; Less-5&#xff08;黑名单&#xff0c;点空格点绕过…...

5-26 Cpp学习笔记

1、如果子类实现了基类的函数&#xff0c;返回值、参数都相同&#xff0c;就覆盖了基类的函数。 2、使用作用域解析运算符来调用基类的函数。myDinner.Swim(); —— 调用子类的。myDinner.Fish::Swim(); —— 调用基类的(基类是Fish) 3、在子类中使用关键字using解除对Fish::…...

YOLOv8_pose的训练、验证、预测及导出[关键点检测实践篇]

1.关键点数据集划分和配置 从上面得到的数据还不能够直接训练,需要按照一定的比例划分训练集和验证集,并按照下面的结构来存放数据,划分代码如下所示,该部分内容和YOLOv8的训练、验证、预测及导出[目标检测实践篇]_yolov8训练测试验证-CSDN博客是重复的,代码如下: …...

架构师必考题--软件系统质量属性

软件系统质量属性 1.质量属性2.质量属性场景描述3.系统架构评估 这个知识点是系统架构师必考的题目&#xff0c;也是案例分析题第一题&#xff0c; 有时候会出现在选择题里面&#xff0c;考的分数也是非常高的。 1.质量属性 属性说明可用性错误检测/恢复/避免性能资源需求/管理…...

深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录

ASP.NET Core 是一个跨平台的开源框架&#xff0c;用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录&#xff0c;以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...

学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2

每日一言 今天的每一份坚持&#xff0c;都是在为未来积攒底气。 案例&#xff1a;OLED显示一个A 这边观察到一个点&#xff0c;怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 &#xff1a; 如果代码里信号切换太快&#xff08;比如 SDA 刚变&#xff0c;SCL 立刻变&#…...

Springboot社区养老保险系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;社区养老保险系统小程序被用户普遍使用&#xff0c;为方…...

Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?

Redis 的发布订阅&#xff08;Pub/Sub&#xff09;模式与专业的 MQ&#xff08;Message Queue&#xff09;如 Kafka、RabbitMQ 进行比较&#xff0c;核心的权衡点在于&#xff1a;简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...

Java数值运算常见陷阱与规避方法

整数除法中的舍入问题 问题现象 当开发者预期进行浮点除法却误用整数除法时,会出现小数部分被截断的情况。典型错误模式如下: void process(int value) {double half = value / 2; // 整数除法导致截断// 使用half变量 }此时...

Selenium常用函数介绍

目录 一&#xff0c;元素定位 1.1 cssSeector 1.2 xpath 二&#xff0c;操作测试对象 三&#xff0c;窗口 3.1 案例 3.2 窗口切换 3.3 窗口大小 3.4 屏幕截图 3.5 关闭窗口 四&#xff0c;弹窗 五&#xff0c;等待 六&#xff0c;导航 七&#xff0c;文件上传 …...

GO协程(Goroutine)问题总结

在使用Go语言来编写代码时&#xff0c;遇到的一些问题总结一下 [参考文档]&#xff1a;https://www.topgoer.com/%E5%B9%B6%E5%8F%91%E7%BC%96%E7%A8%8B/goroutine.html 1. main()函数默认的Goroutine 场景再现&#xff1a; 今天在看到这个教程的时候&#xff0c;在自己的电…...

Web后端基础(基础知识)

BS架构&#xff1a;Browser/Server&#xff0c;浏览器/服务器架构模式。客户端只需要浏览器&#xff0c;应用程序的逻辑和数据都存储在服务端。 优点&#xff1a;维护方便缺点&#xff1a;体验一般 CS架构&#xff1a;Client/Server&#xff0c;客户端/服务器架构模式。需要单独…...

WebRTC从入门到实践 - 零基础教程

WebRTC从入门到实践 - 零基础教程 目录 WebRTC简介 基础概念 工作原理 开发环境搭建 基础实践 三个实战案例 常见问题解答 1. WebRTC简介 1.1 什么是WebRTC&#xff1f; WebRTC&#xff08;Web Real-Time Communication&#xff09;是一个支持网页浏览器进行实时语音…...

毫米波雷达基础理论(3D+4D)

3D、4D毫米波雷达基础知识及厂商选型 PreView : https://mp.weixin.qq.com/s/bQkju4r6med7I3TBGJI_bQ 1. FMCW毫米波雷达基础知识 主要参考博文&#xff1a; 一文入门汽车毫米波雷达基本原理 &#xff1a;https://mp.weixin.qq.com/s/_EN7A5lKcz2Eh8dLnjE19w 毫米波雷达基础…...