当前位置：首页 > news >正文

力扣第 71 题简化路径

news 2025/7/27 1:00:53

一、题目描述

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

在 Unix 风格的文件系统中：

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

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

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

二、解题思路

核心思想

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

三、具体实现

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