力扣面试经典——71题

💡 参考代码：

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

/**
 * 简化Unix风格的绝对路径
 * 
 * @param path 输入的Unix风格路径
 * @return 简化后的规范路径
 * 
 * 解题思路:
 * 1. 使用栈来处理目录名
 * 2. 按'/'分割路径字符串
 * 3. 遇到"."或空字符串则忽略
 * 4. 遇到".."则弹出栈顶元素(如果栈不为空)
 * 5. 其他情况将目录名压入栈中
 * 6. 最后将栈中元素按顺序组合成结果路径
 */
char* simplifyPath(char* path) {
    int len = strlen(path);
    // 创建栈用于存储目录名
    char** stack = (char**)malloc(len * sizeof(char*));
    int top = 0; // 栈顶指针
    
    // 使用strtok按'/'分割字符串
    char* token = strtok(path, "/");
    
    // 遍历所有分割后的子串
    while (token != NULL) {
        if (strcmp(token, ".") == 0) {
            // "."表示当前目录，直接忽略
        } else if (strcmp(token, "..") == 0) {
            // ".."表示返回上级目录，弹出栈顶元素(如果存在)
            if (top > 0) {
                top--;
            }
        } else {
            // 普通目录名，压入栈中
            stack[top] = token;
            top++;
        }
        token = strtok(NULL, "/");
    }
    
    // 构建结果字符串
    char* result = (char*)malloc((len + 1) * sizeof(char));
    result[0] = '/'; // 路径以'/'开头
    int idx = 1; // 结果字符串的索引
    
    // 将栈中目录名依次拼接
    for (int i = 0; i < top; i++) {
        for (int j = 0; j < strlen(stack[i]); j++) {
            result[idx++] = stack[i][j];
        }
        if (i < top - 1) {
            result[idx++] = '/'; // 目录间用'/'分隔
        }
    }
    
    result[idx] = '\0'; // 字符串结束符
    
    // 释放栈内存
    free(stack);
    
    return result;
}

📖 总结：

点击展开题目总结

🤔 简化路径

---

1️⃣ 题目核心信息

🎯 功能描述：将Unix风格的绝对路径转换为规范路径，处理目录切换操作

📥 输入输出：

• 输入：/.../a/../b/c/../d/./Unix风格的绝对路径字符串
• 输出：简化后的规范路径字符串

---

2️⃣ 实现原理

💡 核心思路：使用栈数据结构处理路径组件，根据目录操作规则进行相应处理

📋 实现步骤：

1. 按'/'分割路径字符串得到各个组件
2. 遍历组件，根据组件内容执行不同操作：
   • "."：表示当前目录，忽略处理
   • ".."：表示上级目录，从栈中弹出元素（如果栈非空）
   • 其他：普通目录名，压入栈中
3. 将栈中剩余目录按顺序组合成结果路径

---

3️⃣ 关键点解析

🎯 代码技巧

• 使用 strtok 函数按分隔符分割字符串
• 利用栈的特性处理目录的层级关系
• 特殊处理根目录无法向上跳转的情况

4️⃣ 使用场景

✅ 适用情况：

• 文件系统路径规范化
• URL路径处理
• 相对路径与绝对路径转换

⚠️ 前提条件：

• 输入是有效的Unix风格绝对路径
• 路径以'/'开头

5️⃣ 复杂度分析

• ⏱️ 时间复杂度：O(n)，其中n是路径字符串的长度，需要遍历一次字符串
• 💾 空间复杂度：O(n)，需要额外空间存储分割后的组件和结果

6️⃣ 注意事项

🚩 边界情况：

• 路径只有根目录 "/"
• 连续多个斜杠 "//"
• 根目录下使用 ".." 操作
• 包含 "..." 等特殊目录名

💥 易错点：

• 忘记处理空字符串情况
• 未正确处理结果路径的格式（开头斜杠、结尾无斜杠）
• 没有考虑栈为空时执行 ".." 操作的情况

7️⃣ 补充说明

以输入路径 /a/./b/../../c/ 为例，逐步跟踪函数执行过程：

步骤 1: 初始化

int len = strlen(path);  // len = 13
char** stack = (char**)malloc(len * sizeof(char*));  // 创建栈
int top = 0;  // 栈顶指针初始化为0

步骤 2: 分割路径

使用 strtok 按 '/' 分割字符串:

char* token = strtok(path, "/");

分割后的子串依次为: "a", ".", "b", "..", "..", "c"

步骤 3: 处理每个子串

1. 处理 "a":

   • 不是 "." 也不是 ".."
   • 压入栈中: stack[0] = "a", top = 1

2. 处理 ".":

   • 表示当前目录，忽略
   • 栈保持不变: top = 1

3. 处理 "b":

   • 不是 "." 也不是 ".."
   • 压入栈中: stack[1] = "b", top = 2

4. 处理 "..":

   • 表示返回上级目录
   • 弹出栈顶元素: top = 1 (移除了 "b")

5. 处理 "..":

   • 表示返回上级目录
   • 弹出栈顶元素: top = 0 (移除了 "a")

6. 处理 "c":

   • 不是 "." 也不是 ".."
   • 压入栈中: stack[0] = "c", top = 1

步骤 4: 构建结果路径

char* result = (char*)malloc((len + 1) * sizeof(char));
result[0] = '/';  // 路径以'/'开头
int idx = 1;      // 结果字符串索引

将栈中元素依次拼接:

• 从栈中取出 "c"
• 添加到结果中: /c

步骤 5: 返回结果

最终返回简化后的路径: /c

关键点总结

1. 栈的使用: 用栈来维护当前的目录结构，便于处理 ".." 操作
2. 字符串分割: 使用 strtok 按 '/' 分割路径
3. 特殊处理:
   • "." 被忽略
   • ".." 弹出栈顶元素(如果栈不为空)
4. 结果构建: 按顺序将栈中目录名用 '/' 连接

这个算法的时间复杂度是 O(n)，其中 n 是路径字符串的长度

加载评论中...