seo网站沙盒期班级优化大师电脑版
一、题目描述
给定一个字符串 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;
}
四、代码说明
核心函数
1. strtok
strtok(path, "/")将路径字符串按"/"分割。- 每次调用返回一个路径部分，直到返回
NULL。
2. 栈操作
- 栈用数组实现，
top记录栈顶位置。 - 根据路径部分的内容执行以下操作：
".."：回退到上一级，top--。"."或空字符串：跳过。- 其他：压入栈，
stack[++top] = token。
3. 拼接路径
- 如果栈为空，返回
"/"。 - 否则，将栈中的目录名用
"/"拼接成简化路径。
五、运行示例
示例 1
输入：
/home/
输出：
/home
示例 2
输入：
/../
输出：
/
示例 3
输入：
/home//foo/
输出：
/home/foo
六、复杂度分析
时间复杂度
- 路径分割操作和遍历每部分的时间复杂度为 O ( n ) O(n) O(n)，其中 n n n 是路径字符串的长度。
空间复杂度
- 栈中最多存储路径中的目录部分，最坏情况占用 O ( n ) O(n) O(n) 空间。
七、总结
这道题目考察了字符串操作和栈的基本应用。在实现中，strtok 和数组栈的结合使代码简单易懂。如果你对 C++ 或其他语言感兴趣，也可以尝试用 STL 或其他高级工具实现！
如果你有任何问题，欢迎在评论区留言交流！ 😊