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

【算法一则】做算法学数据结构 - 简化路径 - 【栈】

目录

  • 题目
  • 代码
  • 题解

题目

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

OpenHarmony实战开发-如何使用Web预渲染实现功能介绍。

介绍 为了便于大家在使用本案例集时能够更详细的了解各个案例&#xff0c;本案例基于Web预渲染实现了案例介绍功能&#xff0c;即应用右下角的问号icon。 效果图预览 使用说明 因为直接加载的线上README&#xff0c;因此本功能需联网使用点击icon&#xff0c;即会弹出对应案…...

三七互娱,oppo,快手25届暑期实习内推

三七互娱&#xff0c;oppo&#xff0c;快手25届暑期实习内推 ①OPPO 【内推码】&#xff1a;X6866447 【一键内推】:https://careers.oppo.com/university/oppo/campus/post?shareId4546 【需求岗位】软件类、AI/算法类、硬件类、设计类、产品类 ②快手 【岗位】算法、工程、游…...

InnoDB架构:内存篇

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

8个Python高效数据分析的技巧

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

暴力破解密码自动阻断

1 re模块 re 模块是 Python 中用于正则表达式操作的模块。正则表达式&#xff08;Regular Expression&#xff09;是一种强大的文本处理工具&#xff0c;它使用一种特殊的字符序列来表示字符串中的模式&#xff0c;并可以通过模式匹配、查找、替换等操作对文本进行高效处理。 …...

【华为】Telnet实验配置

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

SAM功能改进VRP-SAM论文解读VRP-SAM: SAM with Visual Reference Prompt

现已总结SAM多方面相关的论文解读&#xff0c;具体请参考该专栏的置顶目录篇 一、总结 1. 简介 发表时间&#xff1a;2024年3月30日 论文&#xff1a; 2402.17726.pdf (arxiv.org)https://arxiv.org/pdf/2402.17726.pdf代码&#xff1a; syp2ysy/VRP-SAM (github.com)htt…...

MySQL truncate table 与 delete 清空表的区别和坑

拓展阅读 MySQL View MySQL truncate table 与 delete 清空表的区别和坑 MySQL Ruler mysql 日常开发规范 MySQL datetime timestamp 以及如何自动更新&#xff0c;如何实现范围查询 MySQL 06 mysql 如何实现类似 oracle 的 merge into MySQL 05 MySQL入门教程&#xff0…...

Spring GA、PRE、SNAPSHOT 版本含义及区别

GA:General Availability: 正式发布的版本&#xff0c;推荐使用&#xff08;主要是稳定&#xff09;&#xff0c;与maven的releases类似&#xff1b; PRE: 预览版,内部测试版。主要是给开发人员和测试人员测试和找BUG用的&#xff0c;不建议使用&#xff1b; SNAPSHOT: 快照…...

一文看懂标准版和Pro版的区别

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

腾讯云服务器价格表(腾讯云服务器报价表)

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

试试把GPT和Suno结合起来用(附免费GPT)

什么是GPT GPT&#xff08;生成预训练变换器&#xff09;是由OpenAI开发的一种先进的人工智能模型&#xff0c;它能够理解和生成人类语言。通过大量的数据训练&#xff0c;GPT模型不仅能够撰写文章、编写代码&#xff0c;还能创作诗歌和故事。而现在&#xff0c;这种技术已经扩…...

SpringBoot修改菜品模块开发

需求分析与设计 一&#xff1a;产品原型 在菜品管理列表页面点击修改按钮&#xff0c;跳转到修改菜品页面&#xff0c;在修改页面回显菜品相关信息并进行修改&#xff0c;最后点击保存按钮完成修改操作。 修改菜品原型&#xff1a; 二&#xff1a;接口设计 通过对上述原型图…...

Rust开发笔记 | 系统编程的守护神

在如今这个信息技术不断发展的时代&#xff0c;系统编程语言演进的步伐从未停歇。Rust&#xff0c;作为现代化的系统编程语言&#xff0c;正凭借其出色的性能、安全性和并发处理能力赢得编程界的广泛赞誉。有别于传统的系统编程语言&#xff0c;Rust在保证高性能的同时&#xf…...

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 研究目…...

光场相机建模与畸变校正改进方法

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

面试算法-173-二叉树的直径

题目 给你一棵二叉树的根节点&#xff0c;返回该树的 直径 。 二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。 两节点之间路径的 长度 由它们之间边数表示。 示例 1&#xff1a; 输入&#xff1a;root [1,2,3,4,…...

Python Typing模块

Python Typing模块 常用类型 类型说明int,long,float整型,长整形,浮点型bool,str布尔型&#xff0c;字符串类型List, Tuple, Dict, Set列表&#xff0c;元组&#xff0c;字典, 集合Iterable,Iterator可迭代类型&#xff0c;迭代器类型Generator生成器类型 后三行需要从typing…...

线程同步:确保多线程程序的安全与高效!

全文目录&#xff1a; 开篇语前序前言第一部分&#xff1a;线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分&#xff1a;synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分&#xff…...

Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务

通过akshare库&#xff0c;获取股票数据&#xff0c;并生成TabPFN这个模型 可以识别、处理的格式&#xff0c;写一个完整的预处理示例&#xff0c;并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务&#xff0c;进行预测并输…...

电脑插入多块移动硬盘后经常出现卡顿和蓝屏

当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时&#xff0c;可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案&#xff1a; 1. 检查电源供电问题 问题原因&#xff1a;多块移动硬盘同时运行可能导致USB接口供电不足&#x…...

【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验

系列回顾&#xff1a; 在上一篇中&#xff0c;我们成功地为应用集成了数据库&#xff0c;并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了&#xff01;但是&#xff0c;如果你仔细审视那些 API&#xff0c;会发现它们还很“粗糙”&#xff1a;有…...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)

UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中&#xff0c;UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化&#xf…...

(转)什么是DockerCompose?它有什么作用?

一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用&#xff0c;而无需手动一个个创建和运行容器。 Compose文件是一个文本文件&#xff0c;通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...

大数据学习(132)-HIve数据分析

​​​​&#x1f34b;&#x1f34b;大数据学习&#x1f34b;&#x1f34b; &#x1f525;系列专栏&#xff1a; &#x1f451;哲学语录: 用力所能及&#xff0c;改变世界。 &#x1f496;如果觉得博主的文章还不错的话&#xff0c;请点赞&#x1f44d;收藏⭐️留言&#x1f4…...

USB Over IP专用硬件的5个特点

USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中&#xff0c;从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备&#xff08;如专用硬件设备&#xff09;&#xff0c;从而消除了直接物理连接的需要。USB over IP的…...

HDFS分布式存储 zookeeper

hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架&#xff0c;允许使用简单的变成模型跨计算机对大型集群进行分布式处理&#xff08;1.海量的数据存储 2.海量数据的计算&#xff09;Hadoop核心组件 hdfs&#xff08;分布式文件存储系统&#xff09;&a…...

Mysql中select查询语句的执行过程

目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析&#xff08;Parser&#xff09; 2.4、执行sql 1. 预处理&#xff08;Preprocessor&#xff09; 2. 查询优化器&#xff08;Optimizer&#xff09; 3. 执行器…...