LeetCode(71):简化路径
LeetCode 路径 简化 71
2023-09-14 09:01:22 时间
Medium!
题目描述:
给定一个文档 (Unix-style) 的完全路径,请进行路径简化。
例如,
path = "/home/"
, => "/home"
path = "/a/./b/../../c/"
, => "/c"
边界情况:
- 你是否考虑了 路径 =
"/../"
的情况?
在这种情况下,你需返回"/"
。 - 此外,路径中也可能包含多个斜杠
'/'
,如"/home//foo/"
。
在这种情况下,你可忽略多余的斜杠,返回"/home/foo"
。
解题思路:
这道题让简化给定的路径,光是根据题目中给的那一个例子还真不太好总结出规律,应该再加上两个例子 path = "/a/./b/../c/"
, => "/a/c"和path =
"/a/./b/c/"
, => "/a/b/c",
这样我们就可以知道中间是"."的情况直接去掉,是".."时删掉它上面挨着的一个路径,而下面的边界条件给的一些情况中可以得知,如果是空的话返回"/",如果有多个"/"只保留一个。那么我们可以把路径看做是由一个或多个"/"分割开的众多子字符串,把它们分别提取出来一一处理即可。
C++解法一:
1 class Solution { 2 public: 3 string simplifyPath(string path) { 4 vector<string> v; 5 int i = 0; 6 while (i < path.size()) { 7 while (path[i] == '/' && i < path.size()) ++i; 8 if (i == path.size()) break; 9 int start = i; 10 while (path[i] != '/' && i < path.size()) ++i; 11 int end = i - 1; 12 string s = path.substr(start, end - start + 1); 13 if (s == "..") { 14 if (!v.empty()) v.pop_back(); 15 } else if (s != ".") { 16 v.push_back(s); 17 } 18 } 19 if (v.empty()) return "/"; 20 string res; 21 for (int i = 0; i < v.size(); ++i) { 22 res += '/' + v[i]; 23 } 24 return res; 25 } 26 };
还有一种解法是利用了C语言中的函数strtok来分隔字符串,但是需要把string和char*类型相互转换,转换方法请戳http://www.cnblogs.com/grandyang/p/4312273.html。除了这块不同,其余的思想和上面那种解法相同。
C 解法一:
1 class Solution { 2 public: 3 string simplifyPath(string path) { 4 vector<string> v; 5 char *cstr = new char[path.length() + 1]; 6 strcpy(cstr, path.c_str()); 7 char *pch = strtok(cstr, "/"); 8 while (pch != NULL) { 9 string p = string(pch); 10 if (p == "..") { 11 if (!v.empty()) v.pop_back(); 12 } else if (p != ".") { 13 v.push_back(p); 14 } 15 pch = strtok(NULL, "/"); 16 } 17 if (v.empty()) return "/"; 18 string res; 19 for (int i = 0; i < v.size(); ++i) { 20 res += '/' + v[i]; 21 } 22 return res; 23 } 24 };
C++中也有专门处理字符串的机制,我们可以使用stringstream来分隔字符串,然后对每一段分别处理,思路和上面的方法相似。
C++ 解法二:
1 class Solution { 2 public: 3 string simplifyPath(string path) { 4 string res, t; 5 stringstream ss(path); 6 vector<string> v; 7 while (getline(ss, t, '/')) { 8 if (t == "" || t == ".") continue; 9 if (t == ".." && !v.empty()) v.pop_back(); 10 else if (t != "..") v.push_back(t); 11 } 12 for (string s : v) res += "/" + s; 13 return res.empty() ? "/" : res; 14 } 15 };
相关文章
- Java实现 LeetCode 817 链表组件(暴力)
- Java实现 LeetCode 665 非递减数列(暴力)
- Java实现 LeetCode 576 出界的路径数(DFS || DP)
- Java实现 LeetCode 564 寻找最近的回文数(今天要GG在这道题了 头晕+题难(((φ(◎ロ◎;)φ))))...
- Java实现 LeetCode 551 学生出勤记录 I(暴力大法好)
- Java实现 LeetCode 335 路径交叉
- Java实现 LeetCode 327 区间和的个数
- Java实现 LeetCode 225 用队列实现栈
- Java实现 LeetCode 209 长度最小的子数组
- Java实现 LeetCode 124 二叉树中的最大路径和
- Java实现 LeetCode 113 路径总和 II
- Java实现 LeetCode 64 最小路径和
- Java实现 LeetCode 63 不同路径 II(二)
- 每日一道 LeetCode (8):删除排序数组中的重复项和移除元素
- LeetCode(62):不同路径
- leetcode 124. 二叉树中的最大路径和
- 【LeetCode 中等 字符串 python3】524 通过删除字母匹配到字典里最长单词
- 【LeetCode Python实现】二次元日麻游戏 雀魂麻将
- Leetcode 1598. 文件夹操作日志搜集器
- 【2022最新】Vscode配置Python环境Leetcode刷题指南
- 【Leetcode刷题Python】滑雪路径消耗时间:Testing Round #16 (Unrated) C. Skier
- 【Leetcode刷题Python】1496.判断路径是否相交
- 【LeetCode】剑指Offer 34.二叉树中和为某一值的路径