快捷導(dǎo)航

C++實(shí)現(xiàn)LeetCode(71.簡(jiǎn)化路徑)

更新時(shí)間：2021年07月17日 10:01:39 作者：Grandyang

這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(71.簡(jiǎn)化路徑),本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下

[LeetCode] 71.Simplify Path 簡(jiǎn)化路徑

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.

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".

這道題讓簡(jiǎn)化給定的路徑，光根據(jù)題目中給的那一個(gè)例子還真不太好總結(jié)出規(guī)律，應(yīng)該再加上兩個(gè)例子 path = "/a/./b/../c/", => "/a/c"和path = "/a/./b/c/", => "/a/b/c"，這樣我們就可以知道中間是"."的情況直接去掉，是".."時(shí)刪掉它上面挨著的一個(gè)路徑，而下面的邊界條件給的一些情況中可以得知，如果是空的話返回"/"，如果有多個(gè)"/"只保留一個(gè)。那么我們可以把路徑看做是由一個(gè)或多個(gè)"/"分割開(kāi)的眾多子字符串，把它們分別提取出來(lái)一一處理即可，代碼如下：

C++ 解法一:

class Solution {
public:
    string simplifyPath(string path) {
        vector<string> v;
        int i = 0;
        while (i < path.size()) {
            while (path[i] == '/' && i < path.size()) ++i;
            if (i == path.size()) break;
            int start = i;
            while (path[i] != '/' && i < path.size()) ++i;
            int end = i - 1;
            string s = path.substr(start, end - start + 1);
            if (s == "..") {
                if (!v.empty()) v.pop_back(); 
            } else if (s != ".") {
                v.push_back(s);
            }
        }
        if (v.empty()) return "/";
        string res;
        for (int i = 0; i < v.size(); ++i) {
            res += '/' + v[i];
        }
        return res;
    }
};

還有一種解法是利用了C語(yǔ)言中的函數(shù)strtok來(lái)分隔字符串，但是需要把string和char*類型相互轉(zhuǎn)換，轉(zhuǎn)換方法請(qǐng)猛戳這里。除了這塊不同，其余的思想和上面那種解法相同，代碼如下：

C 解法一:

class Solution {
public:
    string simplifyPath(string path) {
        vector<string> v;
        char *cstr = new char[path.length() + 1];
        strcpy(cstr, path.c_str());
        char *pch = strtok(cstr, "/");
        while (pch != NULL) {
            string p = string(pch);
            if (p == "..") {
                if (!v.empty()) v.pop_back();
            } else if (p != ".") {
                v.push_back(p);
            }
            pch = strtok(NULL, "/");
        }
        if (v.empty()) return "/";
        string res;
        for (int i = 0; i < v.size(); ++i) {
            res += '/' + v[i];
        }
        return res;
    }
};

C++中也有專門處理字符串的機(jī)制，我們可以使用stringstream來(lái)分隔字符串，然后對(duì)每一段分別處理，思路和上面的方法相似，參見(jiàn)代碼如下：

C++ 解法二：

class Solution {
public:
    string simplifyPath(string path) {
        string res, t;
        stringstream ss(path);
        vector<string> v;
        while (getline(ss, t, '/')) {
            if (t == "" || t == ".") continue;
            if (t == ".." && !v.empty()) v.pop_back();
            else if (t != "..") v.push_back(t);
        }
        for (string s : v) res += "/" + s;
        return res.empty() ? "/" : res;
    }
};

Java 解法二：

public class Solution {
    public String simplifyPath(String path) {
        Stack<String> s = new Stack<>();
        String[] p = path.split("/");
        for (String t : p) {
            if (!s.isEmpty() && t.equals("..")) {
                s.pop();
            } else if (!t.equals(".") && !t.equals("") && !t.equals("..")) {
                s.push(t);
            }
        }
        List<String> list = new ArrayList(s);
        return "/" + String.join("/", list);
    }
}

到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(71.簡(jiǎn)化路徑)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)簡(jiǎn)化路徑內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: