簡(jiǎn)化路徑

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

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

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

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

始終以斜杠 '/' 開(kāi)頭。

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

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

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

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

• 示例 1：

輸入：path = "/home/"

輸出："/home"

解釋：注意，最后一個(gè)目錄名后面沒(méi)有斜杠。

• 示例 2：

輸入：path = "/../"

輸出："/"

解釋：從根目錄向上一級(jí)是不可行的，因?yàn)楦夸浭悄憧梢缘竭_(dá)的最高級(jí)。

• 示例 3：

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

輸出："/home/foo"

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

• 示例 4：

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

輸出："/c"  

提示：

1 <= path.length <= 3000

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

path 是一個(gè)有效的 Unix 風(fēng)格絕對(duì)路徑。

方法一：棧（Java）

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

對(duì)于「空字符串」以及「一個(gè)點(diǎn)」，我們實(shí)際上無(wú)需對(duì)它們進(jìn)行處理，因?yàn)椤缚兆址箾](méi)有任何含義，而「一個(gè)點(diǎn)」表示當(dāng)前目錄本身，我們無(wú)需切換目錄。

對(duì)于「兩個(gè)點(diǎn)」或者「目錄名」，我們則可以用一個(gè)棧來(lái)維護(hù)路徑中的每一個(gè)目錄名。當(dāng)我們遇到「兩個(gè)點(diǎn)」時(shí)，需要將目錄切換到上一級(jí)，因此只要棧不為空，我們就彈出棧頂?shù)哪夸洝．?dāng)我們遇到「目錄名」時(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();
    }
}

時(shí)間復(fù)雜度：O（N）

空間復(fù)雜度：O（N）

方法二：標(biāo)準(zhǔn)庫(kù)（Go）

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

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

時(shí)間復(fù)雜度：O（N）

空間復(fù)雜度：O（N）

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

最新評(píng)論