leetcode71. Simplify Path

darkerXi 發布于2019-08-15 10:37 / 2138人閱讀

摘要：標題文字簡化風格的絕對路徑。我們可以首先將所有的內容從中分離出來，然后分別處理。這里我們需要用到堆棧的數據結構。堆棧有很多種實現方式，中的類類都可以實現其功能。我們將讀到的路徑入棧，根據操作符出棧，最后將棧中剩余的元素組織成路徑返回即可。

標題文字

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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