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;
}

You may also like...

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注