【算法一则】做算法学数据结构 - 简化路径 - 【栈】
目录
- 题目
- 栈
- 代码
- 题解
题目
给你一个字符串 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…...
后进先出(LIFO)详解
LIFO 是 Last In, First Out 的缩写,中文译为后进先出。这是一种数据结构的工作原则,类似于一摞盘子或一叠书本: 最后放进去的元素最先出来 -想象往筒状容器里放盘子: (1)你放进的最后一个盘子(…...
接口测试中缓存处理策略
在接口测试中,缓存处理策略是一个关键环节,直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性,避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明: 一、缓存处理的核…...
挑战杯推荐项目
“人工智能”创意赛 - 智能艺术创作助手:借助大模型技术,开发能根据用户输入的主题、风格等要求,生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用,帮助艺术家和创意爱好者激发创意、提高创作效率。 - 个性化梦境…...
【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15
缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下: struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...
蓝桥杯 2024 15届国赛 A组 儿童节快乐
P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡,轻快的音乐在耳边持续回荡,小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下,六一来了。 今天是六一儿童节,小蓝老师为了让大家在节…...
电脑插入多块移动硬盘后经常出现卡顿和蓝屏
当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时,可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案: 1. 检查电源供电问题 问题原因:多块移动硬盘同时运行可能导致USB接口供电不足&#x…...
Unit 1 深度强化学习简介
Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库,例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体,比如 SnowballFight、Huggy the Do…...
【JavaWeb】Docker项目部署
引言 之前学习了Linux操作系统的常见命令,在Linux上安装软件,以及如何在Linux上部署一个单体项目,大多数同学都会有相同的感受,那就是麻烦。 核心体现在三点: 命令太多了,记不住 软件安装包名字复杂&…...
iOS性能调优实战:借助克魔(KeyMob)与常用工具深度洞察App瓶颈
在日常iOS开发过程中,性能问题往往是最令人头疼的一类Bug。尤其是在App上线前的压测阶段或是处理用户反馈的高发期,开发者往往需要面对卡顿、崩溃、能耗异常、日志混乱等一系列问题。这些问题表面上看似偶发,但背后往往隐藏着系统资源调度不当…...
DingDing机器人群消息推送
文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人,点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置,详见说明文档 成功后,记录Webhook 2 API文档说明 点击设置说明 查看自…...
