简化路径[中等]
优质博文: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中的所有字符串。
相关文章:
简化路径[中等]
优质博文:IT-BLOG-CN 一、题目 给你一个字符串path,表示指向某一文件或目录的Unix风格 绝对路径 (以/开头),请你将其转化为更加简洁的规范路径。在Unix风格的文件系统中,一个点.表示当前目录本身&#x…...
记一次若依项目组装树型结构数据的效率优化
背景 最近公司的项目使用了若依框架做开发,发现部门管理功能的部门如果有3万笔记录时,查询部门信息并组装为父子结构时运行特别缓慢,本地运行需要3分钟才能加载出来,因此接到优化的工作。 代码展示 首先看看表结构是这么定义的…...
秒杀系统之系统优化
3 系统优化 对于一个软件系统,提高性能可以有很多种手段,如提升硬件水平、调优JVM 性能,这里主要关注代码层面的性能优化—— 减少序列化:减少 Java 中的序列化操作可以很好的提升系统性能。序列化大部分是在 RPC 阶段发生&#x…...
【介绍下Python多线程,什么是Python多线程】
🌈个人主页: 程序员不想敲代码啊 🏆CSDN优质创作者,CSDN实力新星,CSDN博客专家 👍点赞⭐评论⭐收藏 🤝希望本文对您有所裨益,如有不足之处,欢迎在评论区提出指正,让我们共…...
FPGA相关论文阅读
一、Achieving 100Gbps Intrusion Prevention on a Single Server 论文名称中文翻译:在单台服务器上实现100Gbps吞吐量的入侵防御检测。 文章中的Mixed-1和Norm-1 二、Distributed Password Hash Computation on Commodity Heterogeneous Programmable Platforms…...
瑞芯微RK3588驱动设计之DVP并口摄像头2
dts配置看瑞芯微RK3588驱动配置之DVP并口摄像头1_rockchip 调试dvp设备 直接显示摄像头数据-CSDN博客 这里看看驱动的具体实现,以gc2145为例。 gc2145的驱动源码如下: // SPDX-License-Identifier: GPL-2.0 /** GC2145 CMOS Image Sensor driver*** C…...
安卓手机APP开发__支持64位的架构
安卓手机APP开发__支持64位的架构 目录 概述 读取你的APP 快速的状态检查 你的APP使用了原生的代码吗? 你的APP包含了64位的代码库吗? 确保在这些目录中有原生的代码库. 使用APK分析器查看原生的代码库 通过解压缩APK查看原生的代码库 用安卓工…...
Foxmail使用经验总结
目录 1.概述 2.版本历史 3.使用方法 3.1.安装和设置账户 3.2.收取和阅读邮件 3.3.发送邮件 3.4.管理联系人 3.5.日程安排和任务管理 3.6.定制设置和插件 3.7.跨平台同步 4.小结 1.概述 Fox…...
信息系统项目管理师0601:项目立项管理 — 考点总结(可直接理解记忆)
点击查看专栏目录 项目立项管理 — 考点总结(可直接理解记忆) 1.项目建议书(又称立项申请)是项目建设单位向上级主管部门提交项目申请时所必须的文件,是对拟建项目提出的框架性的总体设想。在项目建议书批准后,方可开展对外工作(掌握)。 2.项目建议书应该包括的核心内…...
实验三:机器学习1.0
要求: 针对实验1和实验2构建的数据集信息分析 设计实现通过数据简介进行大类分类的程序 代码实现: 训练集数据获取: read_data.py import json import pickledef read_intro():data []trypathr"E:\Procedure\Python\Experiment\f…...
Vue 3 + Vite项目实战:常见问题与解决方案全解析
文章目录 一、项目使用本地图片打包后不显示1、在html中时候,本地运行和打包后线上运行都ok。2、用动态数据,本地运行ok,打包后线上运行不显示3、适用于处理单个链接的资源文件4、用动态数据且本地和线上访问都可显示 二、使用插件vite-plugi…...
飞天使-k8s知识点31-rancher的正确打开方式
文章目录 安装之前优化一下内核参数以及系统内核版本 rancher安装主要是使用以下命令nginx的配置为解决办法 安装之前优化一下内核参数以及系统内核版本 内核版本 4.17 cat > /etc/modules-load.d/iptables.conf <<EOF ip_tables iptable_filter EOF 然后重启服务器…...
Vue.component v2v3注册(局部与全局)组件使用详解
在Vue中,可以通过两种方式注册组件:局部注册和全局注册。 局部注册是在父组件中通过import和components选项注册的组件,仅在当前父组件及其子组件中可用。 // 父组件中import ChildComponent from ./ChildComponent.vue;export default {co…...
HNU-算法设计与分析-作业5
第五次作业【回溯算法】 文章目录 第五次作业【回溯算法】<1> 算法分析题5-3 回溯法重写0-1背包<2> 算法分析题5-5 旅行商问题(剪枝)<3> 算法实现题5-2 最小长度电路板排列问题<4> 算法实现题5-7 n色方柱问题<5> 算法实现…...
基础之音视频2
01 前言 02 mp 03 mp实例 简易音乐播放器 04 音频 sound-pool 1.作用 播放多个音频,短促音频 2.过程 加载load- 3.示例 模拟手机选铃声 步骤: 创建SoundPool对象,设置相关属性 音频流存入hashmap 播放音频 05 videoview 3gp 体积小 mp4 …...
两小时看完花书(深度学习入门篇)
1.深度学习花书前言 机器学习早期的时候十分依赖于已有的知识库和人为的逻辑规则,需要人们花大量的时间去制定合理的逻辑判定,可以说是有多少人工,就有多少智能。后来逐渐发展出一些简单的机器学习方法例如logistic regression、naive bayes等…...
21【Aseprite 作图】画白菜
1 对着参考图画轮廓 2 缩小尺寸 变成这样 3 本来是红色的描边,可以通过油漆桶工具(取消 “连续”),就把红色的轮廓线,变成黑色的 同时用吸管工具,吸取绿色和白色,用油漆桶填充颜色 4 加上阴影…...
2024.05.15 [AI开发配环境]个人使用最新版远程服务器配环境大纲:docker、云盘、ssh、conda等
不包括在宿主机安装docker。 docker 找到心仪的镜像,比如从网上pull:https://hub.docker.com/r/pytorch/pytorch/tags?page&page_size&ordering&name2.0.1 docker pull pytorch/pytorch:2.0.1-cuda11.7-cudnn8-devel# 新建容器 docker r…...
opencv 轮廓区域检测
直线检测 void LineDetect(const cv::Mat &binaryImage) {cv::Mat xImage,yImage,binaryImage1,binaryImage2;// 形态学变化,闭操作 先膨胀,再腐蚀 可以填充小洞,填充小的噪点cv::Mat element cv::getStructuringElement(cv::MORPH_RE…...
2024-5-16
今日安排: 完结 nf_tables 模块的基本学习,然后开始审计源码mount 的使用,学习 namespace (昨昨昨昨天残留的任务)(:看我能搁到什么时候静不下心学习新知识就做 CTF 题目🦑🦑🦑 今…...
测试微信模版消息推送
进入“开发接口管理”--“公众平台测试账号”,无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息: 关注测试号:扫二维码关注测试号。 发送模版消息: import requests da…...
日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻
在如今就业市场竞争日益激烈的背景下,越来越多的求职者将目光投向了日本及中日双语岗位。但是,一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧?面对生疏的日语交流环境,即便提前恶补了…...
STM32+rt-thread判断是否联网
一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...
Neo4j 集群管理:原理、技术与最佳实践深度解析
Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...
sqlserver 根据指定字符 解析拼接字符串
DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...
PL0语法,分析器实现!
简介 PL/0 是一种简单的编程语言,通常用于教学编译原理。它的语法结构清晰,功能包括常量定义、变量声明、过程(子程序)定义以及基本的控制结构(如条件语句和循环语句)。 PL/0 语法规范 PL/0 是一种教学用的小型编程语言,由 Niklaus Wirth 设计,用于展示编译原理的核…...
深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南
🚀 C extern 关键字深度解析:跨文件编程的终极指南 📅 更新时间:2025年6月5日 🏷️ 标签:C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言🔥一、extern 是什么?&…...
QT: `long long` 类型转换为 `QString` 2025.6.5
在 Qt 中,将 long long 类型转换为 QString 可以通过以下两种常用方法实现: 方法 1:使用 QString::number() 直接调用 QString 的静态方法 number(),将数值转换为字符串: long long value 1234567890123456789LL; …...
C++:多态机制详解
目录 一. 多态的概念 1.静态多态(编译时多态) 二.动态多态的定义及实现 1.多态的构成条件 2.虚函数 3.虚函数的重写/覆盖 4.虚函数重写的一些其他问题 1).协变 2).析构函数的重写 5.override 和 final关键字 1&#…...
【前端异常】JavaScript错误处理:分析 Uncaught (in promise) error
在前端开发中,JavaScript 异常是不可避免的。随着现代前端应用越来越多地使用异步操作(如 Promise、async/await 等),开发者常常会遇到 Uncaught (in promise) error 错误。这个错误是由于未正确处理 Promise 的拒绝(r…...
