Leetcode算法Java全解答--71. 简化路径.md

Posted by lizhao on 07-09,2019

Leetcode算法Java全解答-- 71. 简化路径

[toc]

题目

给定一个文档 (Unix-style) 的完全路径,请进行路径简化。

例如, path = "/home/", => "/home" path = "/a/./b/../../c/", => "/c"

边界情况:

你是否考虑了 路径 = "/../" 的情况? 在这种情况下,你需返回 "/" 。 此外,路径中也可能包含多个斜杠 '/' ,如 "/home//foo/" 。 在这种情况下,你可忽略多余的斜杠,返回 "/home/foo" 。

例如

path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"

想法

使用一个栈对象

1、如果是空或者“.”,那么当前没有什么地址变动,地址栈不需要变动

2、如果是“..” 则需要出栈(如果栈为空则不操作)因为这是返回上级目录的符号

3、其他情况压栈

结果

超过66%的测试案例

时间复杂度/空间复杂度:n/n

总结

代码

我的答案

public String simplifyPath(String path) {
        Stack<String>  stack=new Stack<String> ();
        while(path.length()>0){
            int start=path.indexOf("/"); //第一个斜杠的位置
            path=path.substring(start+1); //Path一进被截取
            int end=path.indexOf("/");//第二个斜杠的位置
            if(end==-1)
                end=path.length();

            String part=path.substring(0,end);
            path=path.substring(end);

           // System.out.println(part+"  "+path);
            if(part.equals(".") || part.equals(""))
                continue;
            if(part.equals("..")){
                if(stack.isEmpty()==false)
                    stack.pop();
            }

            else stack.push("/"+part);
        }
        String result="";
        while(stack.isEmpty()==false){
            result=stack.pop()+result;
        }
        if(result.length()==0)
            result="/";
        return result;

    }

大佬们的答案

public String simplifyPath(String path) {
        String[] arr = path.split("/");
        List<String> list = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            String s = arr[i];
            if (i != 0 && s.length() == 0 || s.equals(".")) {
                continue;
            }
            if (s.equals("..")) {
                int a = list.size();
                if (a > 0 && !list.get(a - 1).equals(""))
                    list.remove(a - 1);
            } else {
                list.add(s);
            }
        }
        if (list.isEmpty())
            return "/";
        StringBuilder stringBuilder = new StringBuilder();
        for (String s : list) {
            stringBuilder.append(s).append("/");
        }
        int a = stringBuilder.length();
        return  a > 1 ? stringBuilder.substring(0, a - 1) : stringBuilder.toString();
    }

测试用例

 

其他

代码托管码云地址:https://gitee.com/lizhaoandroid/LeetCodeAll.git

查看其他内容可以点击专栏或者我的博客哈:https://blog.csdn.net/cmqwan

“大佬们的答案” 标签来自leetcode,侵权请联系我进行删改

如有疑问请联系,联系方式:QQ3060507060