Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

Leetcode Simplify Path

Leetcode algorithms 第 71 题:Simplify Path。

题目

Given an absolute path for a file (Unix-style), simplify it.

For example,
path = “/home/”, => “/home”
path = “/a/./b/../../c/”, => “/c”

解答

化简一个绝对路径,直接使用栈模拟,遇到普通文件夹直接入栈,遇到"."直接丢弃,遇到".."弹出栈顶元素,最后栈中的元素即为化简后的结果。

注意最后只有一个根目录的情况。

具体代码如下:

class Solution {
public:
    string simplifyPath(string path) {
        stack<string> stk;
        while (!path.empty())
        {
            if (path[0] == '/') //忽略分隔符
            {
                path = path.substr(1); continue;
            }

            int id = path.find_first_of('/');
            string tem; //下个文件名
            if (id == -1) tem = path, path = "";
            else tem = path.substr(0, id), path = path.substr(id + 1);
            
            if (tem == ".") continue; //本级目录
            else if (tem == "..")     //上级目录
            {
                if (!stk.empty()) stk.pop();
            } //下级目录
            else 
                stk.push(tem);

        }
        
        string ans;
        while (!stk.empty())
            ans = "/" + stk.top() + ans, stk.pop();
            
        return ans.empty() ? "/" : ans; //只有根目录情况
    }
};
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论