LeetCode-中等-71-简化路径-栈/双指针/原地解决(C)

LeetCode题解目录

题目

给你一个字符串 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 风格绝对路径。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/simplify-path
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

• 我是先弄了一个栈结构体，然后做完发现直接用path也能，于是改了改，用双指针原地解决，还排名双百，妙啊。
• 用双指针的方式实现栈来解决：
  • 左指针是top，右指针是pos。
    • top表示栈顶的位置，这里的栈顶是有元素的栈顶。
    • pos表示当前匹配的path位置。
  • 入栈操作：
    • 将path[top] = 入栈元素，再将top自增。
  • 退栈操作：
    • 直接top自减即可。
  • 题目说长度至少为1，那么path[0]必然有元素，且是'/'：
    • 因此将栈顶top设0，此时栈内仅一个元素'/'。
  • pos开始循环，从下标1开始，到终止符'\0'，在循环中：
    • 只要判断path[pos]是否为'/'即可：
      • 如果是'/'，有四种可能：
        • 前面的路径是 '.' ，即当前路径：
          • 那么将top左移，即执行退栈操作，把'.'退栈，且'/'不入栈。
        • 前面的路径是.. ，即上层路径：
          • 先退栈两次，top指向".."前的'/'
          • 如果此时top==0，那么已经到根目录了，不能再退了，直接继续下一次循环。
          • 否则就继续退栈，退到再前一个/
        • 前面的路径是正常名称，如folder1，那么直接将'/'入栈即可。
        • 最后一种情况，前面是'/'，因为当前也是'/'，所以只要'/'不入栈，避免出现"//"出现即可。
      • 如果不是'/'，直接将元素入栈即可。
  • 循环结束后，有两种可能：
    • 末尾是.或者..：
      • 要进行切换当前目录，或切换上层目录的操作。
  • 再进行一次判断，结尾是否为/，是的话要退栈一次。
  • 然后将'\0'入栈即可。
• 这个代码中，switch的case '.'可以去掉，这样switch就只剩两个条件，直接if就好。
  • 但我这个双百的得分是现在的代码刷出来的，所以不改了，在后面放个简化的代码。

代码

char * simplifyPath(char * path){
    int top = 0, pos;
    for(pos = 1;    path[pos] != '\0';  pos++){
        switch(path[pos]){
            case '/':
                if(path[top] == '.' && path[top - 1] == '/') 
                    // 处理/./
                    top--;
                else if(path[top] == '.' && path[top - 1] == '.' && path[top - 2] == '/'){
                    //处理 /../
                    top -= 2;
                    if(top != 0) for(top -= 1; path[top] != '/';    top--);    
                }
                else if(path[top] != '/'){
                    //处理正常文件名
                    top++;
                    path[top] = '/';
                }
                break;
            case '.':
                top++;
                path[top] = '.';
                break;
            default:
                top++;
                path[top] = path[pos];
        }
    }
    if(path[top] == '.' && path[top - 1] == '/') 
        // 处理/.
        top--;
    else if(path[top] == '.' && path[top - 1] == '.' && path[top - 2] == '/'){
        // 处理/..
        top -= 2;
        if(top != 0) for(top -= 1; path[top] != '/';    top--);
    }
    if(top>0 && path[top] == '/') 
        //去除path中最后的/
        top--;
    top++;
    path[top] = '\0';
    return path;
}

去掉冗余代码后

char * simplifyPath(char * path){
    int top = 0, pos;
    for(pos = 1;    path[pos] != '\0';  pos++){
        if(path[pos] == '/'){
            if(path[top] == '.' && path[top - 1] == '/') 
                // 处理/./
                top--;
            else if(path[top] == '.' && path[top - 1] == '.' && path[top - 2] == '/'){
                //处理 /../
                top -= 2;
                if(top != 0) for(top -= 1; path[top] != '/';    top--);    
            }
            else if(path[top] != '/'){
                //处理正常文件名
                top++;
                path[top] = '/';
            }
        }
        else{
            top++;
            path[top] = path[pos];
        }
    }
    if(path[top] == '.' && path[top - 1] == '/') 
        // 处理/.
        top--;
    else if(path[top] == '.' && path[top - 1] == '.' && path[top - 2] == '/'){
        // 处理/..
        top -= 2;
        if(top != 0) for(top -= 1; path[top] != '/';    top--);
    }
    if(top>0 && path[top] == '/') 
        //去除path中最后的/
        top--;
    top++;
    path[top] = '\0';
    return path;
}