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

力扣第 71 题简化路径

article 2024/11/29 16:16:56

一、题目描述

给定一个字符串 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;
}