首页 / C++ / [C++]LeetCode: 117 Simplify Path （简化Unix路径 list双向链表)

[C++]LeetCode: 117 Simplify Path （简化Unix路径 list双向链表)

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了[C++]LeetCode: 117 Simplify Path （简化Unix路径 list双向链表)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2283字，纯文字阅读大概需要4分钟。

内容图文

题目：

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

思路：这是Linux内核中较常见的一个操作，就是对一个输入的文件路径进行简化。我们先来了解一下这些符号在Unix路径中代表的意义：

  • “/.” 表示本级目录，可以忽略
  • “/..” 表示返回上一级目录，即若上一级目录存在，连同“/..”一并删除，否则只删除“/..”
  • 若去除冗余后路径为空，返回“/”
  • 若包含多个连续“/”, 删除多余的“/”
在了解了我们要做的操作后，我们想到要维护一个栈，对于每一个块（用“/”作为分隔符）进行分析，如果遇到“../”表示要回到上一层，那么就进行出栈操作（如果栈不为空），如果遇到“./”表示在当前层，则直接跳过，不作操作，其他文件的路径则直接进栈，放在栈尾部。最后根据栈中的内容转换成路径即可，注意我们这里使用list双向链表的特性，和java LinkedList类似，list也包含了栈和队列的实现。这样在还原路径时，我们就不需要再维护一个栈来解决路径的顺序问题了，直接从栈头出栈就可以了。
Attention:
1. C++ list双向链表。
获得元素函数：front(); back();
进出栈/队列函数：push_back(); pop_back(); push_front(); pop_front();
我们可以根据自己的需求，来选择合适的函数进行操作。

2. String compare函数 
int compare (const string& str) const;
如果相等，返回0；
if(tmp.compare(".") == 0)

3. 如果去除冗余后路径为空，返回“/”
if(ret.size() == 0)
            return "/";
4. 注意如何获取分隔符“/”之间的元素，并进行操作，我们遍历一遍path.
 while(i < path.size())
        {
            int index = i;
            //截取‘/’之间的字符串
            string tmp;
            while(i < path.size() && path[i] != '/')
            {
                tmp += path[i];
                i++;
            }
5. 先获取队列头的元素，再pop_front(), 转换成正常路径。
while(!stk.empty())
        {
            ret += "/" + stk.front();
            stk.pop_front();
        }

复杂度：O(N) 空间也是O(N),栈的大小
AC Code： 
class Solution {
public:
    string simplifyPath(string path) {
        if(path.size() == 0) return "";
        list<string> stk;
        string ret;
        
        int i = 0;
        while(i < path.size())
        {
            int index = i;
            //截取‘/’之间的字符串
            string tmp;
            while(i < path.size() && path[i] != '/')
            {
                tmp += path[i];
                i++;
            }
            
            if(index != i)
            {
                if(tmp.compare(".") == 0)
                {
                   continue;
                }
                else if(tmp.compare("..") == 0)
                {
                    if(!stk.empty())
                    {
                        stk.pop_back();
                    }
                }
                else
                {
                    stk.push_back(tmp);
                }
            }
            
            i++;
        }
        
        while(!stk.empty())
        {
            ret += "/" + stk.front();
            stk.pop_front();
        }
        
        if(ret.size() == 0)
            return "/";
            
        return ret; 
    }
};

这道题，我们也可以用数组来存储分隔符之间的元素，这样就可以直接通过下标来操作元素。数组也有push_back和pop_back函数。可以看下这篇博文：Simplify Path
不过通过这道题，了解到C++ list数据结构的强大和使用方便。以后要好好利用。

原文：http://blog.csdn.net/cinderella_niu/article/details/43052745

内容总结

以上是互联网集市为您收集整理的[C++]LeetCode: 117 Simplify Path （简化Unix路径 list双向链表)全部内容，希望文章能够帮你解决[C++]LeetCode: 117 Simplify Path （简化Unix路径 list双向链表)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1205596.html

来源：【匿名】