哈尔滨快速建站模板,青岛网站建设搜q.479185700,企业营销网站建设公司哪家好,网站建设流程总结文章目录 Tag题目来源题目解读解题思路方法一#xff1a;字符串数组模拟栈 其他语言python3 写在最后 Tag
【栈】【字符串】 题目来源
71. 简化路径 题目解读
将 Unix 风格的绝对路径转化成更加简洁的规范路径。字符串中会出现 字母、数字、/、_、. 和 .. 这几种字符#… 文章目录 Tag题目来源题目解读解题思路方法一字符串数组模拟栈 其他语言python3 写在最后 Tag
【栈】【字符串】 题目来源
71. 简化路径 题目解读
将 Unix 风格的绝对路径转化成更加简洁的规范路径。字符串中会出现 字母、数字、/、_、. 和 .. 这几种字符其中 . 表示当前目录本身.. 表示将目录切换到上一级目录。
最后返回的 规范路径 必须满足以下几个要求
必须以斜杠 / 开头两个目录名之间必须只有一个 /最后一个路径名之后不能以 / 结尾需要将路径字符串中的 . 和 .. 转到对应的路径输出。 解题思路
方法一字符串数组模拟栈
对于本题表示绝对路径的字符串中的目录名或者目录操作. 和 ..都位于 / 之间因此我们可以先根据分隔符 / 来分割字符串得到目录名和目录操作。对应的 C 代码如下
vectorstring split(string ss, char delim) {/** 以字符 delim 分割字符串 ss字符串数组中可能会出现空字符串*/vectorstring res; string str;for (auto s : ss) {if (s delim) {res.push_back(str);str ;}else {str s;}}res.push_back(str); // 防止 ss 最后一个字符不是分隔时丢掉最后一个字符串return res;
}以上代码表示根据分隔符 delim 来分割字符串 ss将分割后的字符串存放到数组中。
在绝对路径中可能会存在多个连续的 /那么经过 split() 分割代码分割后的字符串数组中可能会出现空字符串这一点需要注意后续在遍历字符串数组时不需要处理空字符。
有了目录名和目录操作之后我们就可以根据目录名和目录操作对目录进行操作生成简洁的规范路径了。因为在路径操作中会返回上一级目录这里有一种 “先进后出” 的特性所以使用 栈 这种基本的数据结构来存储目录名遇到 ..我们就弹出当前的栈顶元素新漏出来的字符串就是当前的目录。简化路径之后我们还需要将栈中的所有目录名使用 / 连接起来这一步骤需要从栈底到栈顶的顺序遍历栈中目录因此为了方便遍历操作使用字符串数组模拟栈。
选定了基本的数据结构之后我们就可以遍历字符串数组
如果当前的字符串为 ..并且栈非空那么我们就要弹出栈顶元素模拟返回上一级目录否则如果当前的字符串非空并且不为 .那么就将当前的目录名加入栈中。
遍历结束后我们将栈中目录使用 / 拼接得到简洁的规范路径 res
如果栈为空res /否则枚举栈中目录名 str更新 res / str最后返回 res。
实现代码
class Solution {
public:vectorstring split(string ss, char delim) {/** 以字符 delim 分割字符串 ss字符串数组中可能会出现空字符串*/vectorstring res; string str;for (auto s : ss) {if (s delim) {res.push_back(str);str ;}else {str s;}}res.push_back(str); // 防止 ss 最后一个字符不是分隔时丢掉最后一个字符串return res;}string simplifyPath(string path) {vectorstring names split(path, /);vectorstring stk;for (string name : names) {// 遇到 .. 切换到上一级目录if (name ..) {if (!stk.empty()) {stk.pop_back();}}// 遇到目录名加入栈else if (!name.empty() name ! .) {stk.push_back(name);}}// 将栈中的目录以 / 作为分隔包装起来string res;if (stk.empty()) {res /;}else {for (string str : stk) {res / str;}}return res;}
};复杂度分析
时间复杂度 O ( n ) O(n) O(n) n n n 是字符串 path 的长度。
空间复杂度 O ( n ) O(n) O(n)需要 O ( n ) O(n) O(n) 的空间存储 names 中的所有字符串。 其他语言
python3
class Solution:def simplifyPath(self, path: str) - str:names path.split(/)stack list()for name in names:if name ..:if stack:stack.pop()elif name and name ! .:stack.append(name)return / /.join(stack)写在最后
如果文章内容有任何错误或者您对文章有任何疑问欢迎私信博主或者在评论区指出 。
如果大家有更优的时间、空间复杂度方法欢迎评论区交流。
最后感谢您的阅读如果感到有所收获的话可以给博主点一个 哦。
