Leetcode典型题解答和分析、归纳和汇总——T71（简化路径）

科技前沿 • 2025-03-29 18:09 • 阅读 50

大家好，我是讯享网，很高兴认识大家。

题目描述：

以unix风格给出的一个文件的绝对路径，你需要简化它，使之成为规范路径。

在Unix风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点(..)表示将其目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。请注意，返回的规范路径必须以斜杠‘/’开头，并且两个目录名之间必须只有一个斜杠。最后一个目录名不能以斜杠结尾。此外，规范路径都需是表示绝对路径的最短字符串。

讯享网

题目解析：对于这种字符串的处理方式，一般都涉及“栈”的基本知识。栈是一种最基本的数据结构，然后根据数据“先进后出”的进栈原则，我们可以分析得到以下解题思路：

【1】用栈来存储路径名字；

【2】当遇到“..”则将栈顶元素抛出；

【3】最后用斜杠将栈中的元素连接起来。

class Solution{ public: string simplifyPath(string path){ stack<string> s; int len = path.size(); int cnt =0; //进行计数 string tmp; //中间变量 string result; //返回结果 while(cnt<len) { if(path[cnt]=='/') //从小到大开始遍历 { if(tmp=="..") //保存的tmp是“..” { if(!s.empty()) //此时堆栈非空 s.pop(); //将栈顶元素弹出 } else if(tmp!=""&&tmp!=".") //如果保存元素为空或者不等于. s.push(tmp); //将tmp入栈 tmp.clear(); //把tmp中间变量清理干净 } else //如果不是斜杠，则将当前值保存在tmp中 { tmp+=path[cnt]; //把当前元素路径入栈 } cnt++; } if(tmp==".."&&!s.empty()) s.pop(); //当最后一个tmp保存的是..，则s进行弹出 if(tmp!="."&&tmp!=".."&&tmp!="") s.push(tmp); //如果最后一个tmp只是普通文件名，则push（入栈） while(!s.empty()) //当堆栈非空的时候 { result = '/'+s.top()+result; //把斜杠加入“/”+（连接）栈顶+上一个result。 s.pop(); //弹出这个栈顶元素 } return (int) result.size()==0?"/":result; //如果result = 0，则返回“/”，否则是result。 } };

讯享网

Leetcode典型题解答和分析、归纳和汇总——T71（简化路径）

相关推荐