文档章节

71. Simplify Path

cofama
 cofama
发布于 2017/05/31 22:41
字数 454
阅读 0
收藏 0

原题链接

Given an absolute path for a file (Unix-style), simplify it. For example, path = "/home/", => "/home" path = "/a/./b/../../c/", => "/c"

先根据'/'的位置分割路径字符串,java可以直接用split函数,C++没有这个函数,需要遍历字符串判断当前字符是否为‘/’,并用substr提取两个‘/’之间的字符。分割子串后,考虑特殊情况:1.子串为“..”,意思为返回上级目录,这个操作让人很容易联想到栈,即把最近压入的目录“弹出”,栈顶就变成了上一级目录。2.子串为空或‘.’,意思是不变动目录,不作任何操作。综合考虑,我使用栈来当作存储路径的暂时容器,每读出一个不是特殊情况的字符串,就把它压入栈,每遇到".."就弹出一个栈顶元素,最后把栈中的元素重新拼接起来。

class Solution {
public:
    string simplifyPath(string path) {
        deque<string> st;
        string tmp;
        if(path.back()!='/') path.push_back('/');
        int start=0;
        for(int i=0; i<path.length(); i++) {
            if(path[i]=='/') {
                tmp=path.substr(start, i-start);
                if(tmp=="..") {
                   if(!st.empty()) st.pop_back();
                }
                else if(tmp!="." && tmp!="") st.push_back(tmp);
                start = i+1;
            }
        }

        if(st.empty()) return "/";
        string result = "";
        while(!st.empty()) {
            result = result+"/"+st.front();
            st.pop_front();
        }
        return result;
    }
};

代码实现中有几个细节,首先如果原路径不以‘/’结尾,则在末尾加上‘/’,这是因为循环中只有碰到‘/’才有机会把分割的子串压入栈中,如果最后不以‘/’结尾,就可能直接遍历完字符串而没有把最后一个分割子串压入栈。其次,实际的栈不是用stack,而是用deque实现,这是因为stack只能先入后出,在最后拼接路径时不能按正序输出子串。使用vector去实现栈也是可以的,但我测试了一下好像deque跑的速度快些。附:deque与vector的区别

© 著作权归作者所有

共有 人打赏支持
cofama
粉丝 0
博文 24
码字总数 19162
作品 0
广州
程序员
私信 提问
Nginx服务配置综合实例

################################ 1.安装nginx,yum安装,编译安装 Nginx是一个免费,开源,高性能的HTTP服务器,同时也可以作为反向代理服务器,支持IMAP/POP3邮件代理服务器,支持模块化定...

rackie386
2017/09/09
0
0
Nginx服务配置综合实例

################################ 1.安装nginx,yum安装,编译安装 Nginx是一个免费,开源,高性能的HTTP服务器,同时也可以作为反向代理服务器,支持IMAP/POP3邮件代理服务器,支持模块化定...

rackie386
2017/09/09
0
0
Linux 安装双版本jdk(2)rpm -ivh or -Uvh?

比如我现在有个1.7版本的,想在安装1.6版本怎么办? 0. 可以先试试有1.7的时候,1.6能不能装上。因为我用Ubuntu系统,安装jdk,jdk-6u45-linux-x64.bin,jdk-7u71-linux-x64.tar.gz可以安装。...

Mr_sheng
2017/12/02
0
0
在CentOS 7中安装与配置JDK8

参考命令:http://www.jb51.net/os/RedHat/73016.html来进行安装 安装说明 系统环境:centos7 安装方式:rpm安装 软件:jdk-8u25-linux-x64.rpm 下载地址:http://www.oracle.com/technetwo...

jims
2016/02/17
1K
0
1-1 ubuntu配置 --- ubuntu adb安装与使用

一、adb介绍 android-sdk-linux_x86/tools下有一堆工具,包括Android Debug Bridge(缩写adb,有点像gcc的gdb似的),在android开发过程中,这个工具是使用得最多的。 adb start-server – ...

zhuran0822
2014/01/22
0
0

没有更多内容

加载失败,请刷新页面

加载更多

dubbo常用功能总结

准备工作: (1)启动zookeeper作为dubbo的注册中心 (2)新建一个maven的生产者web工程dubbo-provider-web和一个maven的消费者web工程dubbo-consumer-web (3)在pom.xml文件里面引入如下依...

呵呵哒灬
12分钟前
0
0
数据库技术-Mysql主从复制与数据备份

数据库技术-Mysql 主从复制的原理: MySQL中数据复制的基础是二进制日志文件(binary log file)。一台MySQL数据库一旦启用二进制日志后,其作为master,它的数据库中所有操作都会以“事件”...

须臾之余
昨天
13
0
Git远程仓库——GitHub的使用(一)

Git远程仓库——GitHub的使用(一) 一 、 Git远程仓库 由于你的本地仓库和GitHub仓库之间的传输是通过SSH加密的,所以需要一下设置: 步骤一、 创建SSH key 在用户主目录下,看看有没有.ss...

lwenhao
昨天
4
0
SpringBoot 整合

springBoot 整合模板引擎 SpringBoot 整合Mybatis SpringBoot 整合redis SpringBoot 整合定时任务 SpringBoot 整合拦截器...

细节探索者
昨天
1
0
第二个JAVA应用

第二个JAVA应用 方法一:配置文件: # cd /usr/local/tomcat/conf/# vim server.xml</Host> <Host name="www.wangzb.cc" appBase="/data/wwwroot/www.wangzb.cc" //引用所......

wzb88
昨天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部