【算法一则】做算法学数据结构 - 简化路径 - 【栈】
目录
- 题目
- 栈
- 代码
- 题解
题目
给你一个字符串 path ,表示指向某一文件或目录的 Unix 风格 绝对路径 (以 ‘/’ 开头),请你将其转化为更加简洁的规范路径。
在 Unix 风格的文件系统中,一个点(.)表示当前目录本身;此外,两个点 (…) 表示将目录切换到上一级(指向父目录);两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠(即,‘//’)都被视为单个斜杠 ‘/’ 。 对于此问题,任何其他格式的点(例如,‘…’)均被视为文件/目录名称。
请注意,返回的 规范路径 必须遵循下述格式:
始终以斜杠 ‘/’ 开头。
两个目录名之间必须只有一个斜杠 ‘/’ 。
最后一个目录名(如果存在)不能 以 ‘/’ 结尾。
此外,路径仅包含从根目录到目标文件或目录的路径上的目录(即,不含 ‘.’ 或 ‘…’)。
返回简化后得到的 规范路径 。
示例 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 风格绝对路径。
栈
栈是一种常见的数据结构,它遵循先进后出(LIFO)的原则。栈有两个主要的操作:入栈(push)和出栈(pop)。入栈操作将元素放入栈的顶部,出栈操作将栈顶的元素移除并返回。
以下是一个简单的栈的Java实现示例:
import java.util.ArrayList;
import java.util.EmptyStackException;
import java.util.List;public class Stack<T> {private List<T> stackList;public Stack() {stackList = new ArrayList<>();}public void push(T element) {stackList.add(element);}public T pop() {if (isEmpty()) {throw new EmptyStackException();}int lastIndex = stackList.size() - 1;T element = stackList.get(lastIndex);stackList.remove(lastIndex);return element;}public T peek() {if (isEmpty()) {throw new EmptyStackException();}return stackList.get(stackList.size() - 1);}public boolean isEmpty() {return stackList.isEmpty();}public int size() {return stackList.size();}
}
上述代码中,我们使用一个 List
来存储栈中的元素。push
方法将元素添加到列表的末尾,pop
方法从列表的末尾移除元素并返回它。peek
方法返回栈顶的元素而不移除它。isEmpty
方法用于检查栈是否为空,size
方法返回栈的大小。
使用该栈的示例:
public class Main {public static void main(String[] args) {Stack<Integer> stack = new Stack<>();stack.push(1);stack.push(2);stack.push(3);System.out.println(stack.pop()); // 输出:3System.out.println(stack.peek()); // 输出:2System.out.println(stack.size()); // 输出:2System.out.println(stack.isEmpty()); // 输出:false}
}
上述示例展示了栈的基本操作,包括入栈、出栈、查看栈顶元素、获取栈的大小以及检查栈是否为空。
代码
public String simplifyPath(String path) {String[] split = path.split("/");Stack<String> stack = new Stack<>();Arrays.stream(split).forEach(s -> {if (s.equals("..")) {if (!stack.isEmpty()) {stack.pop();}} else if (!s.equals(".") && !s.equals("")) {stack.push(s);}});if (stack.size() > 0) {String lastElement = stack.lastElement();if (lastElement.equals("/")) {stack.remove(stack.size() - 1);}}StringBuilder sb = new StringBuilder();for (String s : stack) {sb.append("/").append(s);}return sb.toString().length() == 0 ? "/" : sb.toString();
}
题解
这段Java代码实现了简化文件路径的功能。给定一个字符串路径,例如 “/a/b/c/…/…/…/x/y/z”,该函数会将其简化为 “/x/y/z”。
代码的主要思路是使用栈来模拟路径的进入和返回。首先,将路径按照 “/” 进行分割,得到一个字符串数组。然后,遍历数组中的每个元素。
如果当前元素是 “…”,表示需要返回上一级目录,那么就从栈中弹出一个元素。如果当前元素不是 “.” 也不是空字符串,那么将其压入栈中。
遍历完数组后,如果栈中还有元素,表示最终的路径不为空。如果栈顶元素是 “/”,则将其移除。最后,将栈中的元素按照 “/” 进行拼接,得到简化后的路径。
如果最终的路径为空,返回 “/”,否则返回拼接后的路径字符串。
这段代码的时间复杂度为 O(n),其中 n 是路径字符串的长度。
相关文章:

【算法一则】做算法学数据结构 - 简化路径 - 【栈】
目录 题目栈代码题解 题目 给你一个字符串 path ,表示指向某一文件或目录的 Unix 风格 绝对路径 (以 ‘/’ 开头),请你将其转化为更加简洁的规范路径。 在 Unix 风格的文件系统中,一个点(.)表…...

OpenHarmony实战开发-如何使用Web预渲染实现功能介绍。
介绍 为了便于大家在使用本案例集时能够更详细的了解各个案例,本案例基于Web预渲染实现了案例介绍功能,即应用右下角的问号icon。 效果图预览 使用说明 因为直接加载的线上README,因此本功能需联网使用点击icon,即会弹出对应案…...
三七互娱,oppo,快手25届暑期实习内推
三七互娱,oppo,快手25届暑期实习内推 ①OPPO 【内推码】:X6866447 【一键内推】:https://careers.oppo.com/university/oppo/campus/post?shareId4546 【需求岗位】软件类、AI/算法类、硬件类、设计类、产品类 ②快手 【岗位】算法、工程、游…...

InnoDB架构:内存篇
InnoDB架构:内存篇 InnoDB是MySQL数据库中默认的存储引擎,它为数据库提供了事务安全型(ACID兼容)、行级锁定和外键支持等功能。InnoDB的架构设计优化了对于读取密集和写入密集型应用的性能表现,是一个高度优化的存储系…...

8个Python高效数据分析的技巧
这篇文章介绍了8个使用Python进行数据分析的方法,不仅能够提升运行效率,还能够使代码更加“优美”。 1 一行代码定义List 定义某种列表时,写For 循环过于麻烦,幸运的是,Python有一种内置的方法可以在一行代码中解决…...

暴力破解密码自动阻断
1 re模块 re 模块是 Python 中用于正则表达式操作的模块。正则表达式(Regular Expression)是一种强大的文本处理工具,它使用一种特殊的字符序列来表示字符串中的模式,并可以通过模式匹配、查找、替换等操作对文本进行高效处理。 …...

【华为】Telnet实验配置
【华为】Telnet 实验配置 应用场景三种认证方式配置注意事项拓扑无认证(None)交换机配置顺序Telnet ServerTelnet Client测试 密码认证(Password)配置顺序Telnet ServerTelnet Client测试 AAA认证(scheme)配…...

SAM功能改进VRP-SAM论文解读VRP-SAM: SAM with Visual Reference Prompt
现已总结SAM多方面相关的论文解读,具体请参考该专栏的置顶目录篇 一、总结 1. 简介 发表时间:2024年3月30日 论文: 2402.17726.pdf (arxiv.org)https://arxiv.org/pdf/2402.17726.pdf代码: syp2ysy/VRP-SAM (github.com)htt…...
MySQL truncate table 与 delete 清空表的区别和坑
拓展阅读 MySQL View MySQL truncate table 与 delete 清空表的区别和坑 MySQL Ruler mysql 日常开发规范 MySQL datetime timestamp 以及如何自动更新,如何实现范围查询 MySQL 06 mysql 如何实现类似 oracle 的 merge into MySQL 05 MySQL入门教程࿰…...

Spring GA、PRE、SNAPSHOT 版本含义及区别
GA:General Availability: 正式发布的版本,推荐使用(主要是稳定),与maven的releases类似; PRE: 预览版,内部测试版。主要是给开发人员和测试人员测试和找BUG用的,不建议使用; SNAPSHOT: 快照…...

一文看懂标准版和Pro版的区别
在CRMEB的众多产品中,有这样两款产品经常被拿来比较,它们就是CRMEB的标准版和Pro版商城系统,今天,我们就来盘一下这两款系统之间究竟有哪些不同。 1、Pro版系统性能更卓越 CRMEB Pro版采用Tp6 SwooleRedis高性能框架开发&#x…...

腾讯云服务器价格表(腾讯云服务器报价表)
腾讯云服务器提供了多种类型的产品,以满足不同用户的需求,其价格因产品类型、配置和使用时长等因素而有所不同。以下是根据最近的信息整理的腾讯云服务器价格表概览,但请注意,实际价格可能会有所变动,建议用户在购买前…...

试试把GPT和Suno结合起来用(附免费GPT)
什么是GPT GPT(生成预训练变换器)是由OpenAI开发的一种先进的人工智能模型,它能够理解和生成人类语言。通过大量的数据训练,GPT模型不仅能够撰写文章、编写代码,还能创作诗歌和故事。而现在,这种技术已经扩…...

SpringBoot修改菜品模块开发
需求分析与设计 一:产品原型 在菜品管理列表页面点击修改按钮,跳转到修改菜品页面,在修改页面回显菜品相关信息并进行修改,最后点击保存按钮完成修改操作。 修改菜品原型: 二:接口设计 通过对上述原型图…...
Rust开发笔记 | 系统编程的守护神
在如今这个信息技术不断发展的时代,系统编程语言演进的步伐从未停歇。Rust,作为现代化的系统编程语言,正凭借其出色的性能、安全性和并发处理能力赢得编程界的广泛赞誉。有别于传统的系统编程语言,Rust在保证高性能的同时…...

dcoker+nginx解决前端本地开发跨域
步骤 docker 拉取nginx镜像跑容器 并配置数据卷nginx.conf nginx.conf文件配置 这里展示server server {listen 80;listen [::]:80;server_name localhost;#access_log /var/log/nginx/host.access.log main;location / {# 当我们访问127.0.0.1:8028就会跳转到ht…...
基于云开发和微信小程序的爱宠家系统
基于云开发和微信小程序的爱宠家系统 “Development of PetCare Home System based on Cloud Computing and WeChat Mini Program” 完整下载链接:基于云开发和微信小程序的爱宠家系统 文章目录 基于云开发和微信小程序的爱宠家系统摘要第一章 系统概述1.1 研究背景1.2 研究目…...

光场相机建模与畸变校正改进方法
摘要:光场相机作为一种新型的成像系统,可以直接从一次曝光的图像中得到三维信息。为了能够更充分有效地利用光场数据包含的角度和位置信息,完成更加精准的场景深度计算,从而提升光场相机的三维重建的精度,需要实现精确…...

面试算法-173-二叉树的直径
题目 给你一棵二叉树的根节点,返回该树的 直径 。 二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。 两节点之间路径的 长度 由它们之间边数表示。 示例 1: 输入:root [1,2,3,4,…...
Python Typing模块
Python Typing模块 常用类型 类型说明int,long,float整型,长整形,浮点型bool,str布尔型,字符串类型List, Tuple, Dict, Set列表,元组,字典, 集合Iterable,Iterator可迭代类型,迭代器类型Generator生成器类型 后三行需要从typing…...
浅谈 React Hooks
React Hooks 是 React 16.8 引入的一组 API,用于在函数组件中使用 state 和其他 React 特性(例如生命周期方法、context 等)。Hooks 通过简洁的函数接口,解决了状态与 UI 的高度解耦,通过函数式编程范式实现更灵活 Rea…...

边缘计算医疗风险自查APP开发方案
核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...

Debian系统简介
目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版ÿ…...

理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端
🌟 什么是 MCP? 模型控制协议 (MCP) 是一种创新的协议,旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议,它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...
JAVA后端开发——多租户
数据隔离是多租户系统中的核心概念,确保一个租户(在这个系统中可能是一个公司或一个独立的客户)的数据对其他租户是不可见的。在 RuoYi 框架(您当前项目所使用的基础框架)中,这通常是通过在数据表中增加一个…...
【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论
路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中(图1): mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...
小木的算法日记-多叉树的递归/层序遍历
🌲 从二叉树到森林:一文彻底搞懂多叉树遍历的艺术 🚀 引言 你好,未来的算法大神! 在数据结构的世界里,“树”无疑是最核心、最迷人的概念之一。我们中的大多数人都是从 二叉树 开始入门的,它…...

Kubernetes 节点自动伸缩(Cluster Autoscaler)原理与实践
在 Kubernetes 集群中,如何在保障应用高可用的同时有效地管理资源,一直是运维人员和开发者关注的重点。随着微服务架构的普及,集群内各个服务的负载波动日趋明显,传统的手动扩缩容方式已无法满足实时性和弹性需求。 Cluster Auto…...

Unity VR/MR开发-VR开发与传统3D开发的差异
视频讲解链接:【XR马斯维】VR/MR开发与传统3D开发的差异【UnityVR/MR开发教程--入门】_哔哩哔哩_bilibili...
怎么开发一个网络协议模块(C语言框架)之(六) ——通用对象池总结(核心)
+---------------------------+ | operEntryTbl[] | ← 操作对象池 (对象数组) +---------------------------+ | 0 | 1 | 2 | ... | N-1 | +---------------------------+↓ 初始化时全部加入 +------------------------+ +-------------------------+ | …...