【leecode

URL题目分析源码源码概述小结

链接：https://leetcode-cn.com/problems/simplify-path/

#include 
#include 
#include 


char ** split(const char *s , char delim , int * return_size){
    int n = strlen(s);
    
    char ** ans =  (char **)malloc(sizeof(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)); //pos->delim , curr->delim , pos-curr == str_len , +1 for endl
            strncpy(ans[len] , s + curr , pos - curr);
            ans[len][pos - curr] = ''; // 注意结束符
            ++len; //‘路径名’ 元素个数
        }
    }
    * return_size = len ;
    return ans;
}

char * simplifyPath(char * path){
    int names_size = 0;
    int n = strlen(path);
    
    char ** names = split(path,'/',&names_size);

    
    char ** stack = (char **)malloc(sizeof(char *) * names_size);
    int stack_size = 0;

    
    for(int i = 0;i < names_size ; ++i){
        if(!strcmp(names[i],"..")){//当前路径为..，则实际有效文件夹个数-1
            if(stack_size > 0){
                --stack_size;
            }
        }else if (strcmp(names[i] , ".")){//当前路径不为.，则移动分割中的元素到stack中，追加到文件stack的路径中
            stack[stack_size] = names[i];
            ++stack_size;
        }
    }

    
    char * ans = (char *)malloc(sizeof(char) * (n+1));
    int curr = 0 ;
    
    if (stack_size == 0){
        ans[curr] = '/';
        ++curr;
    }else{
        
        for (int i = 0; i < stack_size; ++i){
            ans[curr] = '/';
            ++curr;
            strcpy(ans + curr, stack[i]); //start_offset of ans
            curr += strlen(stack[i]);// total_length of stack[xx]
        }
    }

    
    ans[curr] = '';
    
    for(int i = 0;i 
before : /home/
after  : /home

before : /../
after  : /

before : /home//foo/
after  : /home/foo

before : /a/./b/../../c/
after  : /c

 
 
源码概述 
 
 
以‘/’为分隔符，切分原始path，并将每个元素存储到names[]字符串列表中，并记录总“文件夹”个数。遍历上述列表，if为…，则总文件夹个数-1，else if为.，则将当前列表中的元素赋值给最终存储的空间中ans[]。为ans的每个元素中间添加一个’/’done.
 
 
 
 
将原始路径按“/”划分并存储在列表中，
 申请stack空间存储最终有效的文件夹名称，通过判断上述列表中每个元素的操作逻辑，如… 或者 不为. --因为情况是限定的，只能是“.”、“…”、“文件名”三种情况。–来判断当前空间的元素赋值情况，为…表示当前上一元素值无效，做自减操作，后续赋值会覆盖当前位置；不为.则表示当前列表中的元素为文件夹，存储到申请的stack元素中。
 申请新空间ans，存储完整且合法的路径。为每个stack元素之间添加“/”字符，使其表达方式合法。
 
 
 
小结 
 
 
PS：
 利用入栈出栈的机制，在遍历时确保当前元素始终为最终的操作目录，最后再合法化字符串即可。
 三次申请内存空间。