71. 简化路径（C语言实现 + 栈解法）

题目回顾给你一个字符串path表示指向某一文件或目录的Unix 风格绝对路径请将其转化为更加简洁的规范路径。规则.表示当前目录忽略。..表示上一级目录需要出栈。多个连续/当作一个/。其他字符串是合法目录名。返回的路径必须以/开头两个目录名之间只有一个/最后不能有尾/除非是根目录/示例输入: /home//foo/ 输出: /home/foo 输入: /a/./b/../../c/ 输出: /c 输入: /.../a/../b/c/../d/./ 输出: /.../b/d解题思路按/分割路径得到一段段 token。使用栈维护路径.→ 跳过..→ 出栈如果栈不空其他 → 入栈最后把栈里的目录用/拼接返回结果。核心思想栈就是文件路径的历史记录遇到..就回退遇到普通目录就记录忽略.和空目录连续/造成的空串示例分析输入: /a/./b/../../c/处理过程token栈状态a[a].[a]b[a, b]..[a]..[]c[c]最终路径/cC语言实现#include stdio.h #include stdlib.h #include string.h char* simplifyPath(char* path) { int len strlen(path); char** stack (char**)malloc(sizeof(char*) * len); int top 0; int i 0; while (i len) { while (i len path[i] /) i; // 跳过 / if (i len) break; int start i; while (i len path[i] ! /) i; // 找 token int token_len i - start; char* token (char*)malloc(token_len 1); strncpy(token, path start, token_len); token[token_len] \0; if (strcmp(token, .) 0) { free(token); // 当前目录跳过 } else if (strcmp(token, ..) 0) { if (top 0) free(stack[--top]); // 上一级 free(token); } else { stack[top] token; // 普通目录 } } if (top 0) { // 根目录 free(stack); char* res (char*)malloc(2); strcpy(res, /); return res; } int total 0; for (int j 0; j top; j) total strlen(stack[j]) 1; char* res (char*)malloc(total 1); res[0] \0; for (int j 0; j top; j) { strcat(res, /); strcat(res, stack[j]); free(stack[j]); } free(stack); return res; }复杂度分析时间复杂度O(n)每个字符最多扫描一次入栈和拼接都是线性时间。空间复杂度O(n)栈最坏情况下存储所有目录。面试易错点忽略连续/→ 空 token。...不等于..要当作合法目录名。..出栈时要判断栈是否为空。最后结果不能有尾/除根目录。使用 C 记得mallocfree避免内存泄漏。✅总结栈模拟路径操作最直观.跳过..出栈其余入栈最终拼接栈即可得到规范路径