题目地址 https://leetcode-cn.com/problems/design-file-system/
题目描述
Youare asked to design a file system which provides two functions:
- create(path, value): Creates a new path and associates a value to it if possible and returns True. Returns False if the path already exists or its parent path doesn't exist.
- get(path): Returns the value associated with a path or returns -1 if the path doesn't exist.
Theformat of a path is one or more concatenated strings of the form: / followed by one or more lowercase English letters. For example, /leetcode and /leetcode/problems are valid paths while an empty string and / are not.
Implement the two functions.
Please refer to the examples for clarifications.
Example 1:
Input:
["FileSystem","create","get"]
[[],["/a",1],["/a"]]
Output:
[null,true,1]
Explanation:
FileSystem fileSystem = new FileSystem();
fileSystem.create("/a", 1); // return true
fileSystem.get("/a"); // return 1
Example 2:
Input:
["FileSystem","create","create","get","create","get"]
[[],["/leet",1],["/leet/code",2],["/leet/code"],["/c/d",1],["/c"]]
Output:
[null,true,true,2,false,-1]
Explanation:
FileSystem fileSystem = new FileSystem();
fileSystem.create("/leet", 1); // return true
fileSystem.create("/leet/code", 2); // return true
fileSystem.get("/leet/code"); // return 2
fileSystem.create("/c/d", 1); // return false because the parent path "/c" doesn't exist.
fileSystem.get("/c"); // return -1 because this path doesn't exist.
Constraints:
Thenumber of calls to the two functions is less than or equal to 10^4 in total. 2 <= path.length <= 100 1 <= value <= 10^9
题目大意
你需要设计一个能提供下面两个函数的文件系统：
- create(path, value): 创建一个新的路径，并尽可能将值 value 与路径 path 关联，然后返回 True。如果路径已经存在或者路径的父路径不存在，则返回 False。
- get(path): 返回与路径关联的值。如果路径不存在，则返回 -1。
解题方法
字典
总体思想：使用字典保存每一个已经创建的路径。
- create()：找出其父路径，判断是否已经存在。当父路径存在时，字典保存新路径的值，否则不保存。
- get()：判断字典中是否已经存在该路径，如果存在返回对应的值，否则返回-1.
这个做法把所有的路径保存在同一级上，没有下面的目录树科学。
由于leetcode-cn无法提交该题答案，下面的代码没有submit。
C++代码如下：
class FileSystem {
public:
FileSystem() {
}
bool create(string path, int value) {
if (path.empty() || path == "/" || path[0] != '/')
return false;
int last = path.size();
while (last >= 1 && path[last] != '/') {
last --;
}
string parent = path.substr(0, last);
if (!m_.count(parent))
return false;
m_[path] = value;
return true;
}
int get(string path) {
return m_.count(path) ? m_[path] : -1;
}
private:
unordered_map<string, int> m_;
};
/**
* Your FileSystem object will be instantiated and called as such:
* FileSystem* obj = new FileSystem();
* bool param_1 = obj->create(path,value);
* int param_2 = obj->get(path);
*/
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
目录树
是否有更好的做法？类似于我们系统文件的保存方法？
我们可以创建一个目录树，把每一个路径对应一个叶子，其保存它的所有孩子。查找的时候也依次从目录树获取路径。这个结构类似于字典树。
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发