leetcode刷题日记——简化路径

[ 题目描述 ]：

[ 思路 ]：

• "…“在这个问题中是一个合法路径名字，”…"表示上一级目录，路径只能存在单’/’
• 可以先定义一个 strlen(path)+1 长度的stack，用于存储答案
• 当遇见 ’ / ’ 时，如果栈顶不是 ’ / '，则压入栈顶
• 当遇见连续 ’ … ’ 的最后一个 ’ . ’ 时，如果下一个字符是 ’ / '，或当前字符是最后一个字符
  • 判断栈中有多少个点
    • 数量大于1，则是路径，压入字符
    • 数量等于1，且前一个字符是 ’ / '，则表示返回上级目录，一直退栈到前一个 ’ / '处
    • 数量等于1，且前一个字符步数 ’ / ’ ，则说明 ‘ . ’ 是路径字符
    • 数量小于1，若 ’ . ’ 前是 ’ / ’ 则表示当前目录本身，直接判断下一个
    • 数量小于1，若 ’ . ’ 前不是 ’ / ’ 则作为路径纳入
• 运行如下：
  

char* simplifyPath(char* path) {int len=strlen(path);int top=0;char* stack=(char*)malloc(sizeof(char)*(len+1));stack[0]=path[0];for(int i=1;i<len;i++){if(path[i]=='/'){if(stack[top]=='/' || i==len-1) continue;}if(path[i]=='.' && (path[i+1]=='/' || i==len-1)){int count=0,index=top;while(stack[index]=='.'){index--;count++;}if(count<1){if(stack[top]!='/'){stack[++top]=path[i];}continue;}if(count>1){stack[++top]=path[i];continue;} if(stack[index--]=='/'){if(index>0){while(stack[index]!='/') index--;top=index;}else{top=0;}}else{stack[++top]=path[i];}}else{stack[++top]=path[i];}}if(stack[top]=='/' && top!=0) top--;stack[++top]='\0';return stack;
}

[ 官方题解 ]：

• 方法一：栈，将给定的字符串 path 根据 / 分割成一个由若干字符串组成的列表(空字符串，一个点，两个点，只包含英文字母、数字或_的目录名)，然后将字符串当作基本元素，遇见目录名则插入栈中，遇见两个点，则弹出栈顶目录，然后再通过 ’ / ’ 来拼接栈中元素得到简化后的路径

char ** split(const char * s, char delim, int * returnSize) {int n = strlen(s);char ** ans = (char **)malloc(sizeof(char *) * n);int pos = 0;int curr = 0;int len = 0;while (pos < n) {while (pos < n && s[pos] == delim) {++pos;}curr = pos;while (pos < n && s[pos] != delim) {++pos;}if (curr < n) {ans[len] = (char *)malloc(sizeof(char) * (pos - curr + 1)); strncpy(ans[len], s + curr, pos - curr);ans[len][pos - curr] = '\0';++len;}}*returnSize = len;return ans;
}char * simplifyPath(char * path){int namesSize = 0;int n = strlen(path);char ** names = split(path, '/', &namesSize);char ** stack = (char **)malloc(sizeof(char *) * namesSize);int stackSize = 0;for (int i = 0; i < namesSize; ++i) {if (!strcmp(names[i], "..")) {if (stackSize > 0) {--stackSize;} } else if (strcmp(names[i], ".")){stack[stackSize] = names[i];++stackSize;} }char * ans = (char *)malloc(sizeof(char) * (n + 1));int curr = 0;if (stackSize == 0) {ans[curr] = '/';++curr;} else {for (int i = 0; i < stackSize; ++i) {ans[curr] = '/';++curr;strcpy(ans + curr, stack[i]);curr += strlen(stack[i]);}}ans[curr] = '\0';for (int i = 0; i < namesSize; ++i) {free(names[i]);}free(names);free(stack);return ans;
}