-
每日一题：LeetCode：71.简化路径
时间：2022-01-06
力扣难度：Medium
个人难度：Easy
数据结构：字符串、栈
算法：模拟、双指针
2022-01-06：LeetCode：71.简化路径
1. 题目描述
-
题目：原题链接
给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格的绝对路径 ，以
/开头，请你将其转化为更加简洁的规范路径在 Unix 风格的文件系统中，一个点
.表示当前目录本身此外，两个点
..表示将目录切换到上一级即父目录；两者都可以是复杂相对路径的组成部分任意多个连续的斜杠，如：
//都被视为单个斜杠/， 对于此问题，任何其他格式的点（例如，...）均被视为文件或目录名称-
请注意，返回的规范路径必须遵循下述格式
始终以斜杠
/开头两个目录名之间必须只有一个斜杠
/最后一个目录名（如果存在）不能 以
/结尾。此外，路径仅包含从根目录到目标文件或目录的路径上的目录，即不含
.或..
返回简化后得到的 规范路径
-
输入输出规范
输入：字符串path
输出：简化后的字符串
-
输入输出示例
输入："/../I/./love//996/../you/"
输出："/I/love/you"
输入："/a/./b/../../c/"
输出："/c"
2. 方法一：字符串模拟+栈
-
思路
本题首先可以根据题目对简化后字符串的要求入手，遍历整个字符串，对
/、.、..等分别进行处理最终将满足的子目录路径拼接到
StringBuilder中注意对于
..切换到父目录时，需要判断是否到了根目录，已到根目录的话输出/
-
复杂度分析：n是path字符串的长度
时间复杂度：O(n)，遍历了整个path字符串，且最后输出时也遍历了存放子目录的List
空间复杂度：O(n)，使用了一个List集合存放子路径
题解
public String simplifyPath(String path) {
if (path == null || path.length() == 0 || path.charAt(0) != '/') return null;
List<String> pathList = new ArrayList<>();
int n = path.length();
for (int i = 0; i < n; ) {
if (path.charAt(i) == '/') { // 处理 [//]
i++;
} else {
// 记录当前位置
int index = i;
while (i < n && path.charAt(i) != '/') {
i++;
}
// 截取一个子目录
String subPath = path.substring(index, i);
// 处理 [..]
if ("..".equals(subPath)) {
if(!pathList.isEmpty()) {
pathList.remove(pathList.size() - 1);
}
// 处理 [.] [//]
}else if (!".".equals(subPath) && !"".equals(subPath))
// 存入子目录
pathList.add(subPath);
}
}
StringBuilder sb = new StringBuilder();
if (!pathList.isEmpty()) {
for(String subPath : pathList)
sb.append("/").append(subPath);
}
return "".equals(sb.toString()) ? "/" : sb.toString();
}
3. 方法二：字符串分割+栈
-
思路
和方法一类似，除了使用List集合，也可以使用栈结构来存放子目录
使用字符串分割方法
split()，无需遍历整个path字符串，只需要遍历分割后的字符串数组即可由于栈是先进后出(FILO)的，所以使用双端队列，如
LinkedList，从而方便在最后拼接简化后字符串时的操作
-
复杂度分析：n是path字符串的长度
时间复杂度：O(n)，分割方法
split()实际上也是遍历了整个path字符串空间复杂度：O(n)，使用了一个栈结构存放子路径
题解
public String simplifyPath(String path) {
if (path == null || path.length() == 0 || path.charAt(0) != '/') return null;
Deque<String> stack = new LinkedList<>();
String[] strs = path.split("/");
for (String str : strs) {
if ("..".equals(str)) {
if (!stack.isEmpty()) {
stack.removeLast();
}
} else if (!".".equals(str) && !"".equals(str)) {
stack.offerLast(str);
}
}
StringBuilder sb = new StringBuilder();
while (!stack.isEmpty()) {
sb.append("/").append(stack.removeFirst());
}
return "".equals(sb.toString()) ? "/" : sb.toString();
}
-
思考与优化
思考：如何直接在一个循环中完成对简化后字符串的拼接，而不是将所有子目录保存到一个栈或者集合中，最后在遍历集合来拼接字符串
优化：使用两个指针
start、end来记录每次拼接的字符串的起始和结尾位置，如果后面遇到了..，则根据指针来删除字符串的内容由于可能存在多个
..，所以两个指针start、end也分别需要表示为集合的类型
题解：优化版本
public String simplifyPath(String path) {
if (path == null || path.length() == 0 || path.charAt(0) != '/') return null;
StringBuilder sb = new StringBuilder();
// 起始和结尾指针
Stack<Integer> start = new Stack<>();
Stack<Integer> end = new Stack<>();
// 初始化
start.push(0);
end.push(1);
String[] strs = path.split("/");
for (String str : strs) {
// 处理 [..]
if ("..".equals(str)) {
if (!start.isEmpty()) {
sb.delete(start.pop(), end.pop());
} else {
sb.delete(0, 1);
}
// 处理 [.] [//]
} else if (!".".equals(str) && !"".equals(str)) {
start.push(sb.length());
sb.append("/").append(str);
end.push(sb.length());
}
}
return "".equals(sb.toString()) ? "/" : sb.toString();
}
最后
新人LeetCoder，发布的题解有些会参考其他大佬的思路(参考资料的链接会放在最下面)，欢迎大家关注我 ~ ~ ~
如果本文有所帮助的话，希望大家可以给个三连「点赞」&「收藏」&「关注」 ~ ~ ~
也希望大家有空的时候光临我的「个人博客」。
