算法力扣刷题三十四【71.简化路径】

前言

栈和队列篇。
记录三十四【71.简化路径】

一、题目阅读

给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 ‘/’ 开头），请你将其转化为更加简洁的规范路径。

在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点（…）表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠（即，‘//’）都被视为单个斜杠 ‘/’ 。对于此问题，任何其他格式的点（例如，‘…’）均被视为文件/目录名称。

请注意，返回的规范路径必须遵循下述格式：

始终以斜杠 ‘/’ 开头。
两个目录名之间必须只有一个斜杠 ‘/’ 。
最后一个目录名（如果存在）不能以 ‘/’ 结尾。
此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 ‘.’ 或 ‘…’）。返回简化后得到的规范路径。

示例 1：

输入：path = "/home/"
输出："/home"
解释：注意，最后一个目录名后面没有斜杠。

示例 2：

输入：path = "/../"
输出："/"
解释：从根目录向上一级是不可行的，因为根目录是你可以到达的最高级。

示例 3：

输入：path = "/home//foo/"
输出："/home/foo"
解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。

示例 4：

输入：path = "/a/./b/../../c/"
输出："/c"

提示：

1 <= path.length <= 3000
path 由英文字母，数字，'.'，'/' 或 '_' 组成。
path 是一个有效的 Unix 风格绝对路径。

二、尝试实现

思路

（1）遍历path，遇到不是“/”，开始找该文件名称。两层for循环；
（2）定义一个栈，先把根目录“/”，放进去。
（3）push文件名还想直接处理间隔斜杠“/”。
（4）获取文件名，如果path最后不是“/”结尾，还要额外处理最后的文件名。
（5）最后，希望直接弹出栈的内容，包含间隔斜杠“/”，能够return result。
总结：思路没问题，但是操作上很麻烦。修改很多次，总有用例无法测试。

代码

不完善的代码

class Solution {
public:
    string simplifyPath(string path) {
        string result;//返回值
        stack<string> st;//最高层是根目录
        string substr;
        //先在st里面放上根目录“/”
        st.push("/");	
        //从下标1开始遍历，跳过根目录。
        for(int i = 1;i < path.size();i++){
            if(path[i] == '/'){	
                continue;
            }else{	//遇到不是斜杠，开始找文件名
                int j = i+1;	//从下一位开始。
                //本应该看什么时候遇到“/”，break循环；但是如果不是以“/”结尾，还得处理（细节一）；
                for(;j < path.size();j++){
                    if(path[j] == '/'){	
                        substr = path.substr(i,j-i);
                        break;
                    }else if(j == path.size()-1 && path[j] != '/'){	//还有漏洞：如果i==path.size-1，j超出范围无法进去循环，substr还是上一次文件名，会重复放入。
                        substr = path.substr(i,j-i+1);
                    }
                }
                //放入substr。
                if(!substr.empty()&& substr == ".." && st.size() > 1){	//为了不让根目录pop，需要size>1。每次情况，可能访问空字符串，所以!substr.empty()。
                    st.pop();
                }else if(!substr.empty()&& substr != ".." && substr != "."){
                    if(j < path.size()-1){	//检查要不要加“/”
                        substr += "/";
                    }
                    st.push(substr);
                }
                i = j;
                substr.clear();//每次得substr清空。对应上面的漏洞，需要清空。
            }
        }
        
        while(!st.empty()){
            if(result.empty() && st.size() > 1 && st.top().back() == '/'){
                int pos  = st.top().size()-1;
                st.top().erase(pos);
            }
            string temp = st.top();
            result = temp + result;
            st.pop();
        }
        return result;

    }
};

所以：拆东墙补西墙的，始终完善不好。

三、更新思路

正确处理

（1）st只记录有效文件名，先不处理间隔斜杠“/”，等循环pop时再加上“/”。
（2）先对path后面加上“/”，这样无需额外处理最后字段，统一判断是否遇到“/”。统一了判断标准。
（3）for循环只用一个i下标。

代码实现

正确代码：

class Solution {
public:
string simplifyPath(string path) {
        
        string result;//返回值
        stack<string> st;
        string substr = "";//放有效文件名
        path += "/";	//path最后都先加上“/”

        //只记录文件名，放到st中。斜杠暂时不处理
        for(int i = 0;i < path.size();i++){
            if(path[i] != '/'){		//遇到不是“/”，开始统计，用substr放
                substr += path[i];
                continue;
            }else if(substr == ".." && !st.empty()){	
                st.pop();
            }else if(substr != ".." && substr != "." && substr != ""){	//如果path[i] == ""，此处会把空字符串放到st里面，结果不对。不等于空也是必要条件
                st.push(substr);
            }
            substr.clear();	//每一个有效文件名处理之后，都要清空
        }
        
        while(!st.empty()){	//倒着往前连接有效文件名。在这里处理“/”
            string temp = st.top();
            result = temp+result;
            result = "/"+result;
            st.pop();
        }
		return result.empty()? "/":result;	//如果st是空，没有有效文件名，返回根目录。

    }
    
};