Leetcode 71 简化路径simplify-path（栈）

发布时间：2020-12-15 18:17:47 所属栏目：安全来源：网络整理

导读：给定一个文档 (Unix-style) 的完全路径，请进行路径简化。例如， path?=? "/home/" ,=? "/home" path?=? "/a/./b/../../c/" ,=? "/c" 边界情况: 你是否考虑了路径 =? "/../" ?的情况？在这种情况下，你需返回? "/" ?。此外，路径中也可能包含多个斜杠?

给定一个文档 (Unix-style) 的完全路径，请进行路径简化。

例如，
path?=?"/home/",=>?"/home"
path?=?"/a/./b/../../c/",=>?"/c"

边界情况:

你是否考虑了路径 =?"/../"?的情况？
在这种情况下，你需返回?"/"?。
此外，路径中也可能包含多个斜杠?‘/‘?，如?"/home//foo/"?。
在这种情况下，你可忽略多余的斜杠，返回?"/home/foo"?。

=============================================================

可得到路径简化规则：

末尾‘/’删除；
不重复出现‘/’；
‘/./’删除；
‘/../’连并前个路径一起删除；

思路：可以根据‘/‘把路径分割成多个元素，根据规则压入栈中，最后用‘/’拼接；

首先是分割，不想python等的高级语言有split可以直接分割；但是可以用stringstream+getline实现分割功能；

按规则压入栈中：遇到‘.’不处理，遇到‘..’? pop；其他元素push；

下面是AC代码：

class Solution {
public:
    
    string simplifyPath(string path) {
        vector <string> mark;
        string s;
        stringstream ss(path);
        string result;
        while(getline(ss,s,‘/‘)){     //使用stringstream和getline 实现分割功能。
            if(s=="."||s=="")         //如果不加入 ""会出错，存在空字符？！ 
                continue;
            else if(s==".." &&  !mark.empty())     //注意空栈的情况！
                mark.pop_back();
            else if(s!="..") mark.push_back(s);    
        }

        for(string sss:mark){
            result+="/"+sss;
        }
        if(mark.empty())return "/";
        return result;
            
    }
};
                //用stack不能用cpp11标准的for（：）
                 //vector却可以。。。                  //why？？求大神解答

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!