题目链接

题目描述：

以 Unix 风格给出一个文件的绝对路径，你需要简化它。或者换句话说，将其转换为规范路径。

在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。更多信息请参阅：Linux / Unix中的绝对路径 vs 相对路径

请注意，返回的规范路径必须始终以斜杠 / 开头，并且两个目录名之间必须只有一个斜杠 /。最后一个目录名（如果存在）不能以 / 结尾。此外，规范路径必须是表示绝对路径的最短字符串。

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

输入：”/a/./b/../../c/“
输出：”/c”

示例 5：

输入：”/a/../../b/../c//.//“
输出：”/c”

示例 6：

输入：”/a//b////c/d//././/..”
输出：”/a/b/c”

解题思路

  本题的难点在于耐心读题并且总结情况(if-else)。一开始我们要对输入路径进行预处理，在JS Array对象中有split方法，主要用于分割字符串返回为字符串数组，这里我们根据/分成输入路径的字符串数组。针对输入路径的不同情形，我总结出五种情况：

  1. 遇到 ..需要返回上一级，即弹出最近输入的文件名；
  2. 遇到.不作任何变化；
  3. 别忘了""，实例3已经告诉了我们，当分割//时，split会形成""字符串加入数组。而遇到它，也不作任何变化；
  4. 剩下的就是需要输入的文件名
  5. 此外，根据实例2，如果最终栈为空，则需要返回/。

  在JS中，Array对象提供了pop和push方法可以模拟栈。不过，对于本题，我认为实际上是用不到栈的先进后出的特点～
  对于不太理解分割完成的字符串样式(尤其是"")的同学，可以自行在Chrome浏览器进行调试(右键->检查->Sources->打断点调试)～

JS版本

  1. var simplifyPath = function (path) {
  2.     let stack = [];
  3.     const str = path.split("/");
  5.     for (let i = 0; i < str.length; i++) {
  6.         if (str[i] === ".."){
  7.             if(stack.length != 0 ){
  8.                 stack.pop();  
  9.             }      
  10.         }              
  11.         else if (str[i] === "" || str[i] === "."){
  12.             continue;   
  13.         }            
  14.         else{
  15.             stack.push(str[i]); 
  16.         }
  18.     }
  20.     if (stack.length == 0) {
  21.         return "/";
  22.     }
  24.     let result = "";
  25.     for (let i = 0; i < stack.length; i++) {
  26.         result += "/" + stack[i];
  27.     }
  29.     return result;
  30. };

关于C++

  在c++中没有类似于split的现成函数，那怎么办呢？这时候可以考虑getline()函数，关于它的操作自行百度，这里只谈它在本题的作用。getline相当于split和for循环的结合体，对于getline(ss, record, '/')，可解释为输入字符串流ss，遇到'/'就截断，而后record存储输入流信息，直到输入流无效(也就是完成整个字符串的分割)。此外，对于输入流ss的类型必须是stringsream，才能进行流的输入输出操作。注意，存储结果的数据结构并不需要stack，使用vector<string>也可实现结果且执行用时为4ms，因为通篇下来，并未使用过先进后出这一特性。

CPP

  1. class Solution {
  2. public:
  3.     string simplifyPath(string path) {
  4.         stringstream ss(path);
  5.         vector<string> records;
  6.         string record = "";
  8.         while(getline(ss, record, '/')){
  9.             if(record == ".."){
  10.                 if(records.size() != 0){
  11.                     records.pop_back();
  12.                 }
  13.             }
  14.             else if(record == "." || record == ""){
  15.                 continue;
  16.             }
  17.             else{
  18.                 records.push_back(record);
  19.             }
  20.         }
  22.         if(records.size() == 0)
  23.             return "/";
  25.         string result;
  26.         for(auto rec : records)
  27.             result += "/" + rec;
  29.         return result;
  31.     }
  32. };

如果有错误或者不严谨的地方，请务必给予指正，十分感谢。