LeetCode 71.简化路径
题目描述:
以 Unix 风格给出一个文件的绝对路径,你需要简化它。或者换句话说,将其转换为规范路径。在 Unix 风格的文件系统中,一个点(.)表示当前目录本身;此外,两个点 (..) 表示将目录切换到上一级(指向父目录);两者都可以是复杂相对路径的组成部分。更多信息请参阅:Linux / Unix中的绝对路径 vs 相对路径
请注意,返回的规范路径必须始终以斜杠 / 开头,并且两个目录名之间必须只有一个斜杠 /。最后一个目录名(如果存在)不能以 / 结尾。此外,规范路径必须是表示绝对路径的最短字符串。
思想:
可能有点复杂,我采用了两个双端队列,第一个负责对路径进行处理,去掉路径中的"/",将处理好的字符串存储在第一个队列中,每一个目录对应一个字符串,然后对一个字符串进行访问,当不是".." 或"."时,将这个路径弹出,放入第二个队列中,当是".." 且第二个队列不为空时,弹出第二个队列的队尾元素;当为其他情况时,进行下一次循环。最后第二个队列就为简化后的路径,将其分别弹出然后加上"/"就行。
代码:
class Solution {
public:
string simplifyPath(string path) {
deque<string> que1;
deque<string> que2;
for(int i = 0; i < path.size(); i++){
string temp;
while(path[i] == '/' && i < path.size()) { i++; }
while(path[i] != '/' && i < path.size()) {
temp += path[i];
i++;
}
if(!temp.empty()) {que1.push_back(temp);};
}
while(!que1.empty()){
string temp = que1.front();
que1.pop_front();
if(temp != "." && temp != "..") { que2.push_back(temp); }
else if(temp == "." ) { continue; }
else if(temp == ".." && !que2.empty()){
que2.pop_back();
}
else { continue; }
}
cout << "-------" << endl;
string res = "/";
while(!que2.empty()) {
res += que2.front();
que2.pop_front();
res += "/";
}
if(res.size() != 1) { res.erase(res.end() - 1); }
return res;
}
};