力扣第 71 题 简化路径

一、题目描述

给定一个字符串 path，表示一个由目录名和斜杠 "/" 组成的绝对路径，请简化该路径，使其变为规范路径。

在 Unix 风格的文件系统中：

• 一个点 "." 表示当前目录本身；
• 两个点 ".." 表示将目录移动到上一级；
• 多个连续的斜杠视为单个斜杠 "//" 等同于 "/"；
• 规范路径必须以单个斜杠 "/" 开头，并且两个目录之间必须只有一个斜杠 "/"；
• 规范路径不能以斜杠 "/" 结尾（除非它是根目录 "/"）。

输入：一个字符串 path，表示文件系统中的绝对路径。

输出：返回简化后的规范路径。

---

二、解题思路

核心思想

1. 使用 栈 来存储路径中的有效目录名。
2. 遍历路径，根据不同的字符处理：
   • 遇到 ".."：如果栈非空，则弹出栈顶目录（回退到上一级）。
   • 遇到 "." 或空字符：跳过，表示当前目录或无意义路径。
   • 遇到有效目录名：将其压入栈中。
3. 最后，将栈中的目录名按照斜杠拼接成最终的简化路径。

---

三、具体实现

1. 算法流程

• 初始化一个空栈，用于存储目录名。
• 以斜杠 "/" 为分隔符，将路径字符串拆分为多个部分。
• 遍历每个部分，按以下规则处理：
  • 如果是 ".." 且栈非空：弹出栈顶元素。
  • 如果是 "." 或空字符串：跳过。
  • 否则，将有效目录名压入栈。
• 将栈中所有元素用斜杠拼接，前面加上 "/"，即为结果。

2. C 语言代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* simplifyPath(char* path) {
    // 创建一个栈
    char* stack[3000]; // 假设路径中最多有 3000 个目录
    int top = -1; // 栈顶指针
    
    char* token = strtok(path, "/"); // 按 "/" 分割路径

    while (token != NULL) {
        if (strcmp(token, "..") == 0) {
            // 如果是 ".."，弹出栈顶目录
            if (top >= 0) {
                top--;
            }
        } else if (strcmp(token, ".") != 0 && strlen(token) > 0) {
            // 如果是有效目录名，压入栈
            stack[++top] = token;
        }
        token = strtok(NULL, "/"); // 继续分割下一个部分
    }
    
    // 拼接简化路径
    char* result = (char*)malloc(3000 * sizeof(char));
    result[0] = '\0';
    
    if (top == -1) {
        strcpy(result, "/");
    } else {
        for (int i = 0; i <= top; i++) {
            strcat(result, "/");
            strcat(result, stack[i]);
        }
    }
    
    return result;
}

int main() {
    char path[3000];
    printf("请输入路径：");
    scanf("%s", path);
    
    char* result = simplifyPath(path);
    printf("简化后的路径为：%s\n", result);
    
    free(result);
    return 0;
}

---

四、代码说明

核心函数

1. strtok

• strtok(path, "/") 将路径字符串按 "/" 分割。
• 每次调用返回一个路径部分，直到返回 NULL。

2. 栈操作

• 栈用数组实现，top 记录栈顶位置。
• 根据路径部分的内容执行以下操作：
  • ".."：回退到上一级，top--。
  • "." 或空字符串：跳过。
  • 其他：压入栈，stack[++top] = token。

3. 拼接路径

• 如果栈为空，返回 "/"。
• 否则，将栈中的目录名用 "/" 拼接成简化路径。

---

五、运行示例

示例 1

输入：

/home/

输出：

/home

示例 2

输入：

/../

输出：

/

示例 3

输入：

/home//foo/

输出：

/home/foo

---

六、复杂度分析

时间复杂度

• 路径分割操作和遍历每部分的时间复杂度为 $O(n)$，其中 $n$ 是路径字符串的长度。

空间复杂度

• 栈中最多存储路径中的目录部分，最坏情况占用 $O(n)$ 空间。

---

七、总结

这道题目考察了字符串操作和栈的基本应用。在实现中，strtok 和数组栈的结合使代码简单易懂。如果你对 C++ 或其他语言感兴趣，也可以尝试用 STL 或其他高级工具实现！

如果你有任何问题，欢迎在评论区留言交流！ 😊

原文地址：https://blog.csdn.net/weixin_48941116/article/details/144111795

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！