LeetCode 71：简化 Unix 路径（Simplify Path）——栈 / vector

LeetCode 71：简化 Unix 路径（Simplify Path）——栈 / vector

1. 题目描述

给定一个 Unix 风格的绝对路径path，请将其化简为规范路径。规则如下：

• 多个连续的/视为一个/
• .表示当前目录，忽略
• ..表示返回上一级目录（若已在根目录/，则保持/）
• 其他字符串视为目录名，保留

输出要求：

• 必须以/开头
• 目录之间用单个/分隔
• 末尾不能多一个/（除非输出就是根目录/）

2. 解题思路（用栈保存目录）

把路径按/切成一个个目录片段（token），用vector<string>充当“栈”：

• token 为空：说明是开头的/或出现//→ 跳过
• token ==.：当前目录 → 跳过
• token ==..：返回上级 → 栈非空则pop_back()
• 其他：正常目录名 →push_back()

最后把栈中的目录按顺序拼接回去：

• 栈空 → 返回/
• 否则 →/" + dir1 + "/" + dir2 + ...

3. 示例

• 输入：/home/
  输出：/home

• 输入：/a/./b/../../c/
  输出：/c

• 输入：/../
  输出：/

• 输入：/home//foo/
  输出：/home/foo

4. 代码实现

#include<string>#include<vector>usingnamespacestd;classSolution{public:stringsimplifyPath(string path){vector<string>st;string name;intlen=static_cast<int>(path.size());for(inti=0;i<=len;++i){charc=(i==len)?'/':path[i];if(c=='/'){//name为空有2种情况，一种就是开始就是 '/'//另一种就是连续的 '/'(因为上次name被clear了)if(name.empty())continue;if(name=="."){}elseif(name==".."){if(!st.empty())st.pop_back();}else{st.emplace_back(name);}name.clear();}else{name.push_back(c);}}if(st.empty())return"/";string res;for(constauto&s:st){res.push_back('/');res+=s;}returnres;}};