【算法一则】做算法学数据结构 - 简化路径 - 【栈】
目录
- 题目
- 栈
- 代码
- 题解
题目
给你一个字符串 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…...
TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案
一、TRS收益互换的本质与业务逻辑 (一)概念解析 TRS(Total Return Swap)收益互换是一种金融衍生工具,指交易双方约定在未来一定期限内,基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...
【HTML-16】深入理解HTML中的块元素与行内元素
HTML元素根据其显示特性可以分为两大类:块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...
Rust 异步编程
Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...
vue3+vite项目中使用.env文件环境变量方法
vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量,这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...
OPENCV形态学基础之二腐蚀
一.腐蚀的原理 (图1) 数学表达式:dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一,腐蚀跟膨胀属于反向操作,膨胀是把图像图像变大,而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...
蓝桥杯 冶炼金属
原题目链接 🔧 冶炼金属转换率推测题解 📜 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V,是一个正整数,表示每 V V V 个普通金属 O O O 可以冶炼出 …...
使用Spring AI和MCP协议构建图片搜索服务
目录 使用Spring AI和MCP协议构建图片搜索服务 引言 技术栈概览 项目架构设计 架构图 服务端开发 1. 创建Spring Boot项目 2. 实现图片搜索工具 3. 配置传输模式 Stdio模式(本地调用) SSE模式(远程调用) 4. 注册工具提…...
安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲
文章目录 前言第一部分:体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分:体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...
libfmt: 现代C++的格式化工具库介绍与酷炫功能
libfmt: 现代C的格式化工具库介绍与酷炫功能 libfmt 是一个开源的C格式化库,提供了高效、安全的文本格式化功能,是C20中引入的std::format的基础实现。它比传统的printf和iostream更安全、更灵活、性能更好。 基本介绍 主要特点 类型安全:…...
【Linux】Linux安装并配置RabbitMQ
目录 1. 安装 Erlang 2. 安装 RabbitMQ 2.1.添加 RabbitMQ 仓库 2.2.安装 RabbitMQ 3.配置 3.1.启动和管理服务 4. 访问管理界面 5.安装问题 6.修改密码 7.修改端口 7.1.找到文件 7.2.修改文件 1. 安装 Erlang 由于 RabbitMQ 是用 Erlang 编写的,需要先安…...
