分类
LeetCode刷题

LeetCode 第71题 Simplify Path【堆栈】Java

原题地址:https://leetcode.com/problems/simplify-path

以 Unix 风格给出一个文件的绝对路径,你需要简化它。或者换句话说,将其转换为规范路径。

在 Unix 风格的文件系统中,一个点(.)表示当前目录本身;此外,两个点 (..) 表示将目录切换到上一级(指向父目录);两者都可以是复杂相对路径的组成部分。更多信息请参阅:Linux / Unix中的绝对路径 vs 相对路径

请注意,返回的规范路径必须始终以斜杠 / 开头,并且两个目录名之间必须只有一个斜杠 /。最后一个目录名(如果存在)不能以 / 结尾。此外,规范路径必须是表示绝对路径的最短字符串。

示例 1:

输入:”/home/”
输出:”/home”
解释:注意,最后一个目录名后面没有斜杠。

示例 2:

输入:”/../”
输出:”/”
解释:从根目录向上一级是不可行的,因为根是你可以到达的最高级。

示例 3:

输入:”/home//foo/”
输出:”/home/foo”
解释:在规范路径中,多个连续斜杠需要用一个斜杠替换。

示例 4:

输入:”/a/./b/../../c/”
输出:”/c”

示例 5:

输入:”/a/../../b/../c//.//”
输出:”/c”

示例 6:

输入:”/a//b////c/d//././/..”
输出:”/a/b/c”

堆栈就适合解决这类问题。我们首先把字符串用”/”分割成字符串数组。””和”.”都没有啥意义,我们就什么都不做。有内容就压栈,遇到”..”就弹栈,如果最后栈为空,就输出”/”。如果不为空就把栈里面的内容依次输出即可。

下面我们用动画演示这个过程以”/a//b///../c/d/..//.//..”为例:

代码如下:

Github 地址:https://github.com/tinyfool/leetcode/tree/master/src/p0071

其他堆栈和队列相关题目,参照堆栈和队列专题

打赏

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据