一、题目
1、算法题目
“给定一个纸箱某一个文件或目录的绝对路径字符串，返回更加简洁的规范路径。”
题目链接：
来源：力扣（LeetCode）
链接：71. 简化路径 - 力扣（LeetCode） (leetcode-cn.com)
2、题目描述
给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 '/' 开头），请你将其转化为更加简洁的规范路径。
在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠（即，'//'）都被视为单个斜杠 '/' 。 对于此问题，任何其他格式的点（例如，'...'）均被视为文件/目录名称。
请注意，返回的 规范路径 必须遵循下述格式：
- 始终以斜杠 '/' 开头。
- 两个目录名之间必须只有一个斜杠 '/' 。
- 最后一个目录名（如果存在）不能 以 '/' 结尾。
- 此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 '.' 或 '..'）。
返回简化后得到的 规范路径 。
示例 1： 输入： path = "/home/" 输出： "/home" 解释： 注意，最后一个目录名后面没有斜杠。 复制代码
示例 2： 输入： path = "/../" 输出： "/" 解释： 从根目录向上一级是不可行的，因为根目录是你可以到达的最高级。 复制代码
二、解题
1、思路分析
这道题，先分析题意，给定一个路径，进行简化，有几种情况：
- 多个连续/简化为一个/
- 一个点.表示当前目录，去除
- 两个点..表示上机目录，需返回上一级
当遇到两个点，需要返回上级目录，类似于弹出栈顶元素的操作。
遍历路径字符串，遇到/就跳过，遇到非斜杠，统计两个斜杠中间的.点数，一个点表示同级目录，跳过；
两个点标识上级目录，弹出栈顶元素。
当为其他字符串即为文件名时，直接入栈。
2、代码实现
代码参考：
public class Solution { public string SimplifyPath(string path) { Stack<string> s = new Stack<string>(); string[] spiltArr = path.Split('/'); for (int i = 0; i < spiltArr.Length; i++) { if (spiltArr[i] == "") { continue; } if (spiltArr[i] == "..") { if (s.Count > 0) { s.Pop(); } } else if (spiltArr[i] != ".") { s.Push(spiltArr[i]); } } if (s.Count != 0) { StringBuilder sb = new StringBuilder(); while (s.Count != 0) { sb.Insert(0, s.Pop()); sb.Insert(0, "/"); } return sb.ToString(); } else { return "/"; } } } 复制代码
网络异常，图片无法展示
|
3、时间复杂度
时间复杂度 ： O(n)
字符串中每个字符最多被遍历一次。
空间复杂度： O(n)
其中n代表字符串的长度。
三、总结
Linux的目录层级就是用栈实现的, 为了简单，直接使用字符串模拟栈的操作。
