「这是我参与11月更文挑战的第4天,活动详情查看:2021最后一次更文挑战」
前言
力扣第七十一题 简化路径
如下所示:
给你一个字符串 path
,表示指向某一文件或目录的 Unix 风格 绝对路径 (以 '/'
开头),请你将其转化为更加简洁的规范路径。
在 Unix 风格的文件系统中,一个点(.
)表示当前目录本身;此外,两个点 (..
) 表示将目录切换到上一级(指向父目录);两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠(即,'//'
)都被视为单个斜杠 '/'
。 对于此问题,任何其他格式的点(例如,'...'
)均被视为文件/目录名称。
请注意,返回的 规范路径 必须遵循下述格式:
- 始终以斜杠
'/'
开头。 - 两个目录名之间必须只有一个斜杠
'/'
。 - 最后一个目录名(如果存在)不能 以
'/'
结尾。 - 此外,路径仅包含从根目录到目标文件或目录的路径上的目录(即,不含
'.'
或'..'
)。
返回简化后得到的 规范路径 。
示例 1:
输入: path = "/home/"
输出: "/home"
解释: 注意,最后一个目录名后面没有斜杠。
复制代码
示例 2:
输入: path = "/a/./b/../../c/"
输出: "/c"
复制代码
一、思路
我刚开始在做这一题的时候,准备使用正则来替换字符串中的一些特定内容。后面发现无法处理 .
和 ..
的逻辑问题。
后面我发现 简化路径
就是找到所有文件的名称即可,路径中不包括 .
。而 ..
就是回到父级目录,我们可以使用 栈 来实现这一逻辑。
实现的大致步骤如下所示:
- 基于
/
将字符串分组,这样字符串数组arr
中就不含有/
了 - 遍历
arr
,会有如下三种情况- 空字符串 `` 和
.
:此时不做任何处理 - 字符串
..
:栈顶出栈即可,表示回退到上一目录 - 其他情况均入栈
- 空字符串 `` 和
- 遍历栈,拼出完整的路径即可。
tips:为什么使用
/
分组后,会出现空字符串呢? 答:因为像以 `/` 起始或路径中含有 `//` 的情况,都会出现空字符
的情况
举个例子
此处以示例中的 "/a/./b/../../c/"
作为例子
- 通过
/
分组后结果为arr = {"", "a", ".", "b", "..", "..", "c"}
- 开始遍历
arr
,当i=0
时,arr[0]
为""
,丢弃即可 - 当
i=1
时,arr[1] = "a"
,入栈。栈内为"a"
- 当
i=2
时,arr[2] = "."
,丢弃。 - 当
i=3
时,arr[3] = "b"
,入栈。栈内为"a" -> "b"
- 当
i=4
时,arr[4] = ".."
,栈顶出栈。栈内为"a"
- 当
i=5
时,arr[5] = ".."
,栈顶出栈。栈内为 `` - 当
i=6
时,arr[6] = "c"
,入栈。栈内为"c"
- 返回结果
"/c"
即可
二、实现
实现代码
实现代码与思路中保持一致
public String simplifyPath(String path) {
// 利用斜杠来分割字符串
String[] arr = path.split("/");
Stack<String> stack = new Stack<>();
for (String str : arr) {
if ((".").equals(str) || ("").equals(str)) { // 当前目录
// 什么都不做
} else if ("..".equals(str)) { // 向上一级
if (!stack.isEmpty()) { // 栈不为空,出战
stack.pop();
}
} else {
stack.push(str);
}
}
// 遍历栈,得到结果
StringBuilder sb = new StringBuilder();
while (!stack.isEmpty()) {
sb.insert(0 , "/" + stack.pop());
}
return "".equals(sb.toString()) ? "/" : sb.toString();
}
复制代码
测试代码
public static void main(String[] args) {
String path = "/a/./b/../../c/";
new Number71().simplifyPath(path);
}
复制代码
结果
三、总结
感谢看到最后,非常荣幸能够帮助到你~♥
如果你觉得我写的还不错的话,不妨给我点个赞吧!如有疑问,也可评论区见~
近期评论