LeetCode1166. Designing File Systems

leecode题链接：LeetCode1166.设计文件系统

题目描述：

你需要设计一个能提供下面两个函数的文件系统：

create(path, value): 创建一个新的路径,并尽可能将值 value 与路径 path 关联,然后返回 True.如果路径已经存在或者路径的父路径不存在,则返回 False.
get(path): 返回与路径关联的值.如果路径不存在,则返回 -1.
“路径” 是由一个或多个符合下述格式的字符串连接起来形成的：在 / 后跟着一个或多个小写英文字母.

例如 /leetcode 和 /leetcode/problems 都是有效的路径,但空字符串和 / 不是有效的路径.

示例 1：
输入：
[“FileSystem”,“create”,“get”]
[[],["/a",1],["/a"]]
输出：
[null,true,1]
解释：
FileSystem fileSystem = new FileSystem();
fileSystem.create("/a", 1); // 返回 true
fileSystem.get("/a"); // 返回 1

示例 2：
输入：
[“FileSystem”,“create”,“create”,“get”,“create”,“get”]
[[],["/leet",1],["/leet/code",2],["/leet/code"],["/c/d",1],["/c"]]
输出：
[null,true,true,2,false,-1]
解释：
FileSystem fileSystem = new FileSystem();
fileSystem.create("/leet", 1); // 返回 true
fileSystem.create("/leet/code", 2); // 返回 true
fileSystem.get("/leet/code"); // 返回 2
fileSystem.create("/c/d", 1); // 返回 false 因为父路径 “/c” 不存在.
fileSystem.get("/c"); // 返回 -1 因为该路径不存在.

提示：
对两个函数的调用次数加起来小于等于 10^4
2 <= path.length <= 100
1 <= value <= 10^9

解题思路：
Use hash table processing,题解如注释所示.
以下用C语言实现：

#define MAX_PATH_LEN 101

typedef struct {
    
    char keyPath[MAX_PATH_LEN];
    int value;
    UT_hash_handle hh;
} FileSystem;

FileSystem* fileSystemCreate() {
    
    FileSystem *obj = NULL;
    FileSystem* sys = (FileSystem*)malloc(sizeof(FileSystem));
    memset(sys, 0, 1 * sizeof(FileSystem));
    HASH_ADD_STR(obj, keyPath, sys);
    return obj;
}

/* ADD */
bool fileSystemCreatePath(FileSystem* obj, char * path, int value) {
    
    char* startPos = strchr(path, '/'); /* */
    char* endPos = strrchr(path, '/');

    FileSystem *out = NULL;
    HASH_FIND_STR(obj, path, out);
    if (out != NULL) {
     /* 路径存在,return error */
        return false;
    }
    if (startPos != endPos) {
     /* 说明pathis the subpath */
        char fatherPath[MAX_PATH_LEN] = {
    0};
        strncpy(fatherPath, path, endPos - startPos); /* Take out the parent path */
        HASH_FIND_STR(obj, fatherPath, out);
        if (out == NULL) {
     /* 父路径不存在,return error */
            return false;
        }
    }
    /* pathis the parent path and does not exist;pathchild path and its parent path exists,则创建 */
    FileSystem *newSys = (FileSystem *)malloc(1 * sizeof(FileSystem));
    strcpy(newSys->keyPath, path);
    newSys->value = value;
    HASH_ADD_STR(obj, keyPath, newSys);
    return true;
}

int fileSystemGet(FileSystem* obj, char * path) {
    
    FileSystem *out = NULL;
    HASH_FIND_STR(obj, path, out);
    if (out == NULL) {
     /* 不存在,returns an error */
        return -1;
    }
    return out->value;
}

void fileSystemFree(FileSystem* obj) {
    
    FileSystem *cur = NULL;
    FileSystem *tmp = NULL;
    HASH_ITER(hh, obj, cur, tmp) {
    
        HASH_DEL(obj, cur);
        free(cur);
    }
    return;
}

解题总结：

A few basic macros and steps that will use hashing are required

0、定义

typedef struct {
    
    char keyPath[MAX_PATH_LEN]; /* key */
    int value;                  /* value */
    UT_hash_handle hh;          /* Hash table handle */
} FileSystem;

1、初始化
定义一个头指针 FileSystem *head = NULL;
But in this case directly fileSystemCreate() 函数中定义,and allocate a temporary empty table,加入哈希表中.

2、表示增加,There are related macros：
字符串：#define HASH_ADD_STR(head,strfield,add)
整型： #define HASH_ADD_INT(head,intfield,add)
指针： #define HASH_ADD_PTR(head,ptrfield,add)
本例中,哈希的keyis a string pathkeyPath,故用 HASH_ADD_STR,且strfield即为keyPath,add应为 FileSystem add,add是一对(keyPath, value)键值.
HASH_ADD_STR(obj, keyPath, sys); / obj为头指针,keyPath为key域,sys为add键值对 */
注意,add需要malloc.

3、表示查找,The associated macro is ：
字符串：#define HASH_FIND_STR(head,findstr,out)
整型： #define HASH_FIND_INT(head,findint,out)
指针： #define HASH_FIND_PTR(head,findptr,out)
本例中,函数入参pathis the path to address matching,findstr即为path,outThe argument is the result of the match,If it is empty, there is no match;A non-empty description matched.
HASH_FIND_STR(obj, keyPath, out); /* obj为头指针,keyPath为key域,outFor finding result key-value pairs */

4、表示删除,The relevant macro is ：
#define HASH_DEL(head,delptr)
A macro that is used in conjunction with traversal：
#define HASH_ITER(hh,head,el,tmp)
如本例中,

    FileSystem *cur = NULL;
    FileSystem *tmp = NULL;
    HASH_ITER(hh, obj, cur, tmp) {
    
        HASH_DEL(obj, cur);
        free(cur);
    }

5、表示替换,There are related macros（本例没有用到）：
字符串：#define HASH_REPLACE_STR(head,strfield,add,replaced)
整型： #define HASH_REPLACE_INT(head,intfield,add,replaced)
指针： #define HASH_REPLACE_PTR(head,ptrfield,add,replaced)