当前位置:网站首页>LeetCode1166.设计文件系统
LeetCode1166.设计文件系统
2022-08-11 05:16:00 【FussyCat】
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
解题思路:
使用哈希表处理,题解如注释所示。
以下用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 false;
}
if (startPos != endPos) {
/* 说明path是子路径 */
char fatherPath[MAX_PATH_LEN] = {
0};
strncpy(fatherPath, path, endPos - startPos); /* 取出父路径 */
HASH_FIND_STR(obj, fatherPath, out);
if (out == NULL) {
/* 父路径不存在,返错 */
return false;
}
}
/* path为父路径且不存在;path子路径且其父路径存在,则创建 */
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) {
/* 不存在,则返错 */
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;
}
解题总结:
需要会使用哈希的几个基本宏和步骤
0、定义
typedef struct {
char keyPath[MAX_PATH_LEN]; /* key */
int value; /* value */
UT_hash_handle hh; /* 哈希表句柄 */
} FileSystem;
1、初始化
定义一个头指针 FileSystem *head = NULL;
但本例直接在 fileSystemCreate() 函数中定义,并分配一个临时的空表,加入哈希表中。
2、表示增加,相关的宏有:
字符串:#define HASH_ADD_STR(head,strfield,add)
整型: #define HASH_ADD_INT(head,intfield,add)
指针: #define HASH_ADD_PTR(head,ptrfield,add)
本例中,哈希的key是字符串型的路径keyPath,故用 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、表示查找,相关的宏为:
字符串:#define HASH_FIND_STR(head,findstr,out)
整型: #define HASH_FIND_INT(head,findint,out)
指针: #define HASH_FIND_PTR(head,findptr,out)
本例中,函数入参path是要寻址匹配的路径,findstr即为path,out参数是匹配的结果,如果为空说明没有匹配上;非空说明匹配上了。
HASH_FIND_STR(obj, keyPath, out); /* obj为头指针,keyPath为key域,out为寻找结果键值对 */
4、表示删除,相关宏为:
#define HASH_DEL(head,delptr)
用法上结合遍历的宏:
#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、表示替换,相关的宏有(本例没有用到):
字符串:#define HASH_REPLACE_STR(head,strfield,add,replaced)
整型: #define HASH_REPLACE_INT(head,intfield,add,replaced)
指针: #define HASH_REPLACE_PTR(head,ptrfield,add,replaced)
边栏推荐
猜你喜欢
随机推荐
第4章 复合类型-1
一张图带你解读--如何从零开始学习接口自动化
task03 Pytorch模型定义
Redis - Data Types (Basic Instructions, String, List, Set, Hash, ZSet, BitMaps, HyperLogLog, GeoSpatial) / Publish and Subscribe
利用rand函数随机生成uuid
QT circle函数(图片标注)
UML基本概念——动态视图
切分字符串进行输出显示
(一)Docker安装Redis实战(一主二从三哨兵)
(1) Construction of a real-time performance monitoring platform (Grafana+Influxdb+Jmeter)
redis分布式锁
【备忘】从零开始搭建Yolo5训练环境
[转载]Verilog testbench总结
家·谱——人脸识别家谱系统
imx6 yocto编译备忘
代码在线审查(添加网页批注)的实现
开炮,开炮
C语言——函数的使用
总结:交叉验证
Keras与tensorflow 使用基础