LeetCode 71.简化路径

LeetCode 71.简化路径

题目描述:

以 Unix 风格给出一个文件的绝对路径,你需要简化它。或者换句话说,将其转换为规范路径。在 Unix 风格的文件系统中,一个点(.)表示当前目录本身;此外,两个点 (..) 表示将目录切换到上一级(指向父目录);两者都可以是复杂相对路径的组成部分。更多信息请参阅:Linux / Unix中的绝对路径 vs 相对路径

请注意,返回的规范路径必须始终以斜杠 / 开头,并且两个目录名之间必须只有一个斜杠 /。最后一个目录名(如果存在)不能以 / 结尾。此外,规范路径必须是表示绝对路径的最短字符串。

思想:

可能有点复杂,我采用了两个双端队列,第一个负责对路径进行处理,去掉路径中的"/",将处理好的字符串存储在第一个队列中,每一个目录对应一个字符串,然后对一个字符串进行访问,当不是".." 或"."时,将这个路径弹出,放入第二个队列中,当是".." 且第二个队列不为空时,弹出第二个队列的队尾元素;当为其他情况时,进行下一次循环。最后第二个队列就为简化后的路径,将其分别弹出然后加上"/"就行。

代码:

class Solution {
public:
    string simplifyPath(string path) {
        deque<string> que1;
        deque<string> que2;
        for(int i = 0; i < path.size(); i++){
            string temp;
            while(path[i] == '/' && i < path.size()) { i++; }
            while(path[i] != '/' && i < path.size()) {
                temp += path[i];
                i++;
            }
            if(!temp.empty()) {que1.push_back(temp);};
        }
        while(!que1.empty()){
            string temp = que1.front();
            que1.pop_front();
            if(temp != "." && temp != "..") { que2.push_back(temp); }
            else if(temp == "." ) { continue; }
            else if(temp == ".." && !que2.empty()){
                que2.pop_back();
            }
            else { continue; }
            
        }
        cout << "-------" << endl;
        string res = "/";
        while(!que2.empty()) {
            res += que2.front();
            que2.pop_front();
            res += "/";
        }
        if(res.size() != 1) { res.erase(res.end() - 1); }
        return res;
    }
};
上一篇: 150 71 388


下一篇:【Leetcode周赛】从contest-71开始。(一般是10个contest写一篇文章)