leetcode71. Simplify Path

darkerXi 发布于2019-08-15 10:37 / 2098人阅读

摘要：标题文字简化风格的绝对路径。我们可以首先将所有的内容从中分离出来，然后分别处理。这里我们需要用到堆栈的数据结构。堆栈有很多种实现方式，中的类类都可以实现其功能。我们将读到的路径入栈，根据操作符出栈，最后将栈中剩余的元素组织成路径返回即可。

标题文字

Given an absolute path for a file (Unix-style), simplify it.

For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"
click to show corner cases.

Did you consider the case where path = "/../"?
In this case, you should return "/".
Another corner case is the path might contain multiple slashes "/" together, such as "/home//foo/".
In this case, you should ignore redundant slashes and return "/home/foo".

简化unix风格的绝对路径。
这里简单说一下unix风格的路径：

.表示当前文件夹，即不进行任何操作

..表示返回上层文件夹，如果已经至根目录，则不进行任何操作

/表示路径的分割线，多个连续的/等价于/

这里我们需要将复杂的unix路径，例如/a/./b/../../c/简化成最简形式/c

思路和代码

从直观的角度思考，每当路径上我们遇到具有含义的操作符时，就对其当前的路径进行操作。我们可以首先将所有的内容从/中分离出来，然后分别处理。这里我们需要用到堆栈的数据结构。堆栈有很多种实现方式，java中的Stack类LinkedList类都可以实现其功能。我们将读到的路径入栈，根据操作符出栈，最后将栈中剩余的元素组织成String路径返回即可。
代码如下：

    public String simplifyPath(String path) {
        Stack s = new Stack();
        String[] pathDetail = path.split("/");
        for(int i = 0 ; i < pathDetail.length ; i++){
            //弹出上级目录，如果有上级目录
            if(pathDetail[i].equals("..")){
                if(s.isEmpty()){
                    continue;
                }
                s.pop();
            //不进行任何操作
            }else if(pathDetail[i].equals(".") || pathDetail[i].isEmpty()){
                continue;
            }else{
                s.push(pathDetail[i]);
            }
        }
        if(s.isEmpty()){
            return "/";
        }
        StringBuilder result = new StringBuilder();
        do{
            result.insert(0, s.pop());
            result.insert(0, "/");
        }while(!s.isEmpty());
        return result.toString();
    }

也可以使用链表实现：

    public String simplifyPath3(String path) {
        Deque stack = new LinkedList<>();
        Set skip = new HashSet<>(Arrays.asList("..",".",""));
        for (String dir : path.split("/")) {
            if (dir.equals("..") && !stack.isEmpty()) stack.pop();
            else if (!skip.contains(dir)) stack.push(dir);
        }
        String res = "";
        for (String dir : stack) res = "/" + dir + res;
        return res.isEmpty() ? "/" : res;
    }

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

云服务器 GPU云服务器 Simplify V71 Leetcod LeetCode

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/67248.html

[LeetCode] 71. Simplify Path

Problem Given an absolute path for a file (Unix-style), simplify it. For example, path = /home/, => /home path = /a/./b/../../c/, => /c path = /a/../../b/../c//.//, => /c //here: b is cancelle...

superw 2019-08-16 14:00 评论0 收藏0
71. Simplify Path

摘要：题目解答的规则如下三种需要跳过的情况当遇到时，需要向前进出来的顺序是反的，所以加的时候，把最新出来的路径加在前面题目：Given an absolute path for a file (Unix-style), simplify it. For example,path = /home/, => /homepath = /a/./b/../../c/, => /cclick to ...

EdwardUp 2019-08-14 14:23 评论0 收藏0
[Leetcode] Simplify Path 化简路径

摘要：栈法复杂度时间空间思路思路很简单，先将整个路径按照分开来，然后用一个栈，遇到时弹出一个，遇到和空字符串则不变，遇到正常路径则压入栈中。注意如果结果为空，要返回一个弹出栈时要先检查栈是否为空代码 Simplify Path Given an absolute path for a file (Unix-style), simplify it. For example, path = /...

liangzai_cool 2019-08-14 12:40 评论0 收藏0
【Leetcode】71. 简化路径

摘要：题目给定一个文档的完全路径，请进行路径简化。例如，边界情况你是否考虑了路径的情况在这种情况下，你需返回。此外，路径中也可能包含多个斜杠，如。文化和社会被恐惧所塑造，在将来这无疑也不会消失。题目给定一个文档 (Unix-style) 的完全路径，请进行路径简化。例如，path = /home/, => /homepath = /a/./b/../../c/, => /c 边界情况:...

liuchengxu 2019-08-19 11:11 评论0 收藏0
【Leetcode】71. 简化路径

摘要：题目给定一个文档的完全路径，请进行路径简化。例如，边界情况你是否考虑了路径的情况在这种情况下，你需返回。此外，路径中也可能包含多个斜杠，如。文化和社会被恐惧所塑造，在将来这无疑也不会消失。题目给定一个文档 (Unix-style) 的完全路径，请进行路径简化。例如，path = /home/, => /homepath = /a/./b/../../c/, => /c 边界情况:...

afishhhhh 2019-07-30 17:50 评论0 收藏0