LeetCode 71. 简化路径 (C 语言)思路:与栈的思路一致。path参数可写,直接在原串上原地分割,用一个指针数组stack保存各目录名的起始位置,最后原地拼接结果。char*simplifyPath(char*path){intlenstrlen(path);// 最多 len/2 1 个目录名,外加哨兵 \0char**stack(char**)malloc((len/22)*sizeof(char*));inttop0;char*ppath;while(*p){// 跳过多余的 /while(*p/)p;if(*p\0)break;char*startp;while(*p*p!/)p;intsegLenp-start;if(segLen1*start.){// . 跳过}elseif(segLen2start[0].start[1].){if(top0)top--;// .. 弹栈,根目录则不弹}else{stack[top]start;// 正常目录名入栈}}// 原地写回结果char*outpath;if(top0){out[0]/;out[1]\0;}else{char*qout;for(inti0;itop;i){*q/;char*sstack[i];while(*s*s!/)*q*s;}*q\0;}free(stack);returnout;}要点说明:指针数组当栈:stack[i]只记录每个目录段的起始指针,长度在遍历时自然可知(到下一个/或结尾),不用额外存长度原地分割:遍历时把每个/留在原地即可,靠p扫描判断段边界..处理:top 0才弹栈,已在根目录时忽略结果原地写回:out从path开头重写,必然不越界(结果长度 ≤ 原长度),最后补\0复杂度:时间 O(n),额外空间 O(n)(栈数组)。验证示例/home//foo/../bar:栈:home→foo→(..弹掉foo)→bar输出/home/bar✓ Kimi LeetCode 71. 简化路径 C语言实现
LeetCode 71. 简化路径 (C 语言)思路:与栈的思路一致。path参数可写,直接在原串上原地分割,用一个指针数组stack保存各目录名的起始位置,最后原地拼接结果。char*simplifyPath(char*path){intlenstrlen(path);// 最多 len/2 1 个目录名,外加哨兵 \0char**stack(char**)malloc((len/22)*sizeof(char*));inttop0;char*ppath;while(*p){// 跳过多余的 /while(*p/)p;if(*p\0)break;char*startp;while(*p*p!/)p;intsegLenp-start;if(segLen1*start.){// . 跳过}elseif(segLen2start[0].start[1].){if(top0)top--;// .. 弹栈,根目录则不弹}else{stack[top]start;// 正常目录名入栈}}// 原地写回结果char*outpath;if(top0){out[0]/;out[1]\0;}else{char*qout;for(inti0;itop;i){*q/;char*sstack[i];while(*s*s!/)*q*s;}*q\0;}free(stack);returnout;}要点说明:指针数组当栈:stack[i]只记录每个目录段的起始指针,长度在遍历时自然可知(到下一个/或结尾),不用额外存长度原地分割:遍历时把每个/留在原地即可,靠p扫描判断段边界..处理:top 0才弹栈,已在根目录时忽略结果原地写回:out从path开头重写,必然不越界(结果长度 ≤ 原长度),最后补\0复杂度:时间 O(n),额外空间 O(n)(栈数组)。验证示例/home//foo/../bar:栈:home→foo→(..弹掉foo)→bar输出/home/bar✓