簡化路徑

給你一個字符串 path ，表示指向某一文件或目錄的 Unix 風格 絕對路徑 （以 '/' 開頭），請你將其轉(zhuǎn)化為更加簡潔的規(guī)范路徑。

在 Unix 風格的文件系統(tǒng)中，一個點（.）表示當前目錄本身；此外，兩個點 （..） 表示將目錄切換到上一級（指向父目錄）；兩者都可以是復雜相對路徑的組成部分。

任意多個連續(xù)的斜杠（即，'//'）都被視為單個斜杠 '/' 。 對于此問題，任何其他格式的點（例如，'...'）均被視為文件/目錄名稱。

請注意，返回的 規(guī)范路徑 必須遵循下述格式：

始終以斜杠 '/' 開頭。

兩個目錄名之間必須只有一個斜杠 '/' 。

最后一個目錄名（如果存在）不能 以 '/' 結(jié)尾。

此外，路徑僅包含從根目錄到目標文件或目錄的路徑上的目錄（即，不含 '.' 或 '..'）。

返回簡化后得到的 規(guī)范路徑 。

• 示例 1：

輸入：path = "/home/"

輸出："/home"

解釋：注意，最后一個目錄名后面沒有斜杠。

• 示例 2：

輸入：path = "/../"

輸出："/"

解釋：從根目錄向上一級是不可行的，因為根目錄是你可以到達的最高級。

• 示例 3：

輸入：path = "/home//foo/"

輸出："/home/foo"

解釋：在規(guī)范路徑中，多個連續(xù)斜杠需要用一個斜杠替換。

• 示例 4：

輸入：path = "/a/./b/../../c/"

輸出："/c"  

提示：

1 <= path.length <= 3000

path 由英文字母，數(shù)字，'.'，'/' 或 '_' 組成。

path 是一個有效的 Unix 風格絕對路徑。

方法一：棧（Java）

我們首先將給定的字符串 path 根據(jù) / 分割成一個由若干字符串組成的列表，記為 names。

對于「空字符串」以及「一個點」，我們實際上無需對它們進行處理，因為「空字符串」沒有任何含義，而「一個點」表示當前目錄本身，我們無需切換目錄。

對于「兩個點」或者「目錄名」，我們則可以用一個棧來維護路徑中的每一個目錄名。當我們遇到「兩個點」時，需要將目錄切換到上一級，因此只要棧不為空，我們就彈出棧頂?shù)哪夸?。當我們遇到「目錄名」時，就把它放入棧。

class Solution {
    public String simplifyPath(String path) {
        String[] names = path.split("/");
        Deque<String> stack = new ArrayDeque<String>();
        for (String name : names) {
            if ("..".equals(name)) {
                if (!stack.isEmpty()) {
                    stack.pollLast();
                }
            } else if (name.length() > 0 && !".".equals(name)) {
                stack.offerLast(name);
            }
        }
        StringBuffer ans = new StringBuffer();
        if (stack.isEmpty()) {
            ans.append('/');
        } else {
            while (!stack.isEmpty()) {
                ans.append('/');
                ans.append(stack.pollFirst());
            }
        }
        return ans.toString();
    }
}

時間復雜度：O（N）

空間復雜度：O（N）

方法二：標準庫（Go）

具體的方法思路請看上文中的表述。由于Go本身的標準庫已經(jīng)具備該能力，所以只需調(diào)用標準庫即可完成。

import (
	path2 "path"
)
func simplifyPath(path string) string {
	return path2.Clean(path)
}

時間復雜度：O（N）

空間復雜度：O（N）

以上就是Go Java算法之簡化路徑實例詳解的詳細內(nèi)容，更多關(guān)于Go Java算法簡化路徑的資料請關(guān)注腳本之家其它相關(guān)文章！

最新評論