力扣71——简化路径
source link: http://mp.weixin.qq.com/s?__biz=MzU0NTk3NDMyMQ%3D%3D&%3Bmid=2247483896&%3Bidx=1&%3Bsn=ddf51be36f5ae51b8f8a9fbcd3bbde35
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
原题
以 Unix 风格给出一个文件的绝对路径，你需要简化它。或者换句话说，将其转换为规范路径。
在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。更多信息请参阅：Linux / Unix中的绝对路径 vs 相对路径
请注意，返回的规范路径必须始终以斜杠 / 开头，并且两个目录名之间必须只有一个斜杠 /。最后一个目录名（如果存在）不能以 / 结尾。此外，规范路径必须是表示绝对路径的最短字符串。
示例 1：
输入："/home/" 输出："/home" 解释：注意，最后一个目录名后面没有斜杠。
示例 2：
输入："/../" 输出："/" 解释：从根目录向上一级是不可行的，因为根是你可以到达的最高级。
示例 3：
输入："/home//foo/" 输出："/home/foo" 解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。
示例 4：
输入："/a/./b/../../c/" 输出："/c"
示例 5：
输入："/a/../../b/../c//.//" 输出："/c"
示例 6：
输入："/a//b////c/d//././/.." 输出："/a/b/c"
原题url:https://leetcode-cn.com/problems/simplify-path/
解法
看起也不难，但一开始我拿到的时候也是无从下手。
利用栈
看到 .. 的逻辑就特别容易让人想到后退，而记录后退最方便的数据结构应该就是 栈 了。至于 . 就可以想象成可以忽略的内容，而 / 则可以作为分隔符了，来看看代码：
class Solution {
public String simplifyPath(String path) {
// 存储路径
Stack<String> stack = new Stack<>();
// 分隔
String[] array = path.split("/");
for (String str : array) {
// 忽略
if (str.equals("") || str.equals(".")) {
continue;
}
// 后退
if (str.equals("..")) {
stack.pop();
continue;
}
// 需要存储的内容
stack.push(str);
}
StringBuilder sb = new StringBuilder();
for (String str : stack) {
sb.append("/").append(str);
}
// 如果内容为空，则需要输出"/"
if (sb.length() == 0) {
sb.append("/");
}
return sb.toString();
}
}
看起来很美好，提交之后报错了。说是 stack.push(str); 这行抛出了异常 java.util.EmptyStackException ，确实，如果栈为空，依旧还是需要在最顶层的（看来还是没有把问题想全面）。让我们来优化一下代码：
class Solution {
public String simplifyPath(String path) {
// 存储路径
Stack<String> stack = new Stack<>();
// 分隔
String[] array = path.split("/");
for (String str : array) {
// 忽略
if (str.equals("") || str.equals(".")) {
continue;
}
// 后退
if (str.equals("..")) {
// 判断是否为空，不为空，才需要回退
if (!stack.empty()) {
stack.pop();
}
// 无论stack空不空，都需要结束
continue;
}
stack.push(str);
}
StringBuilder sb = new StringBuilder();
for (String str : stack) {
sb.append("/").append(str);
}
if (sb.length() == 0) {
sb.append("/");
}
return sb.toString();
}
}
OK，通过了，执行用时： 6ms ，内存消耗： 36.2MB 。
总结
以上就是这道题目我的解答过程了，不知道大家是否理解了。因为之前已经刷了一些题目了，所以会把这些解题过程都补上去，也当做复习了。我刷题都是选 medium 的，所以不会很难，主要我看外企的面试大多也是以这样的题目为主，刷 hard 的题目确实感觉太费脑子，打击积极性。希望能与大家共同进步。
有兴趣的话可以访问我的博客或者关注我的公众号、头条号，说不定会有意外的惊喜。
https://death00.github.io/
公众号：健程之道
Recommend
-
47
-
40
原题 给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。 说明：每次只能向下或者向右移动一步。 示例: 输入: [ [1,3,1], [1,5,1], [4,...
-
31
原题 给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。 不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。 ...
-
51
原题 给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。 你应当保留两个分区中每个节点的初始相对位置。 示例: 输入: head = 1->4->3->...
-
29
原题 在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。 示例 1: 输入: 4->2->1->3 输出: 1->2->3->4 示例 2: 输入: -1->5->3->4->...
-
24
这道题主要就是利用动态规划进行解答，如果要进行优化，就需要找规律了。 原题 给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。 示例 1: 输入: [2,3,-2,...
-
39
这道题主要就是找规律，基于之前142题环形链表II的规律，就能解决了。 原题 给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，...
-
39
这道题主要涉及动态规划，优化时可以考虑贪心算法和二分查找。 <!-- more --> 原题 给定一个无序的整数数组，找到其中最长上升子序列的长度。 示例: 输入: [10,9,2,5,3,7,101,18]...
-
46
本题主要和图的遍历求解最短路径相关，可以用 Dijkstra 或者 Bellman-Ford 算法进行解决。 原题 给你一个由 n 个节点（下标从 0 开始）组成的无向加权图，该图由一个描述边的列表组成，其中 edges[i] = [a, b] 表示连...
-
8
使用CDPATH简化cd命令中的路径 bash中有一个变量 CDPATH 能指定 cd 命令的搜索路径。 它的值是一个冒号分隔的目录列表，当执行 cd 命令时，bash会从这些搜索路径中查找目标目录，如果找到了...
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK