71.简化路径

题目描述

以 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"

题解

算法描述

• 字符串遍历、栈的应用
• 字符串切割、栈的应用

个人分析

法一：

1. 逐个遍历字符串
2. 遇到.不变
3. 遇到..出栈
4. 遇到/或其他字符时进栈

​ 这是我第一次想出来的算法，后来遇到了这个测试用例："/...",其期望答案居然还是："/..."。靠，我太难了！😥看了题解之后，发现C语言也有字符串切割的函数，就在string.h这个库里，我心一横，换方法了！

法二：

1. 使用strtok()函数，将字符串进行切割
2. 因为每次切割返回的都是指针，所以我声明了一个指针数组
3. 将切割出的子字符串的指针压入指针数组中
4. 然后遍历指针数组
5. 组合出最终的字符串

C代码

法一：

char *simplifyPath(char *path)
{
    int len = strlen(path);
    char *stack = (char *)malloc(len * sizeof(char));
    int top = -1;
    stack[++top] = '/';
    int i;
    for (i = 0; i < len; i++)
    {
        if (path[i] == '.' && path[i + 1] == '.')
        {
            do
            {
                top = top == 0 ? 0 : top - 1;
            } while (stack[top] != '/');
        }
        if (path[i] == '.')
            continue;
        if (path[i] == '/' && stack[top] == '/')//防止连续的'/'
            continue;
        stack[++top] = path[i];
    }
    if (stack[top] == '/' && top > 0)
        top--;
    stack[++top] = '\0';
    printf("%s", stack);
    return stack;
}

法二：

/*
1.按照 / 切割字符串
2.遇到 . continue
3.遇到 .. 出栈
4.遇到 字母 进栈，并且进一个 /
*/
#define maxSize 1024
typedef struct stack
{
    char *data[maxSize];
    int top;
} stack;

char *simplifyPath(char *path)
{
    stack *st = (stack *)malloc(sizeof(stack));
    //初始化指针数组，这点很重要
    int u;
    for (u = 0; u < maxSize; u++)
        st->data[u] = NULL;
    st->top = -1;

    char *str = path;
    char delim[2] = "/";
    char *token = NULL;
	//切割字符串
    token = strtok(str, delim);
    st->data[++st->top] = delim;
    // . 无操作
    // .. 连出两次栈
    while (token != NULL)
    {
        if (token[0] == '.' && token[1] == '\0')
            NULL;
        else if (token[0] == '.' && token[1] == '.' && token[2] == '\0')
            if (st->top > 0)
            {
                st->data[st->top--] = NULL;
                st->data[st->top--] = NULL;
            }
            else
                st->top = 0;
        else
        {
            st->data[++st->top] = token;
            st->data[++st->top] = delim;
        }
        //得到下一个子字符串的指针
        token = strtok(NULL, delim);
    }
    //遍历指针数组所对应的字符串，将其组合成想要的字符串
    int i, j;
    char *res = (char *)malloc(maxSize * sizeof(char));
    int k = -1;
    for (i = 0; st->data[i] != NULL; i++)
        for (j = 0; j < strlen(st->data[i]); j++)
            res[++k] = st->data[i][j];
    if (k == 0)
        res[++k] = '\0';
    res[k] = '\0';
    return res;
}

代码写的稀烂，枯了😥

Python代码

anki_life

class Solution:
    def simplifyPath(self, path: str) -> str:
        stack = []
        for i in path.split('/'):
            if i not in ['', '.', '..']:
                stack.append(i)
            elif i == '..' and stack:
                stack.pop()
        return "/" + "/".join(stack)

不是我写的，真™优美，凎！

PS

使用了新的库函数：strtok()

char *strtok(char *__restrict__ _Str, const char *__restrict__ _Delim)

• char *restrict _Str: 待切割的字符串
• const char *restrict _Delim：包含分隔符的 C 字符串

使用strtok()：

菜鸟教程

#include <string.h>
#include <stdio.h>
 
int main () {
   char str[80] = "This is - www.runoob.com - website";
   const char s[2] = "-";
   char *token;
   
   /* 获取第一个子字符串 */
   token = strtok(str, s);
   
   /* 继续获取其他的子字符串 */
   while( token != NULL ) {
      printf( "%s\n", token );
    
      token = strtok(NULL, s);
   }
   
   return(0);
}