Giả sử chúng ta phải thiết kế một hệ thống tệp cung cấp hai chức năng này -
- createPath (đường dẫn, giá trị) - Thao tác này tạo một đường dẫn mới và liên kết một giá trị với nó nếu có thể và trả về True. Nó trả về False nếu đường dẫn đã tồn tại hoặc đường dẫn mẹ của nó không tồn tại.
- get (path) - Hàm này tìm giá trị được liên kết với một đường dẫn hoặc trả về -1 nếu đường dẫn không tồn tại.
Định dạng của một đường dẫn là một hoặc nhiều chuỗi được nối có dạng - (gạch chéo về phía trước) / theo sau là một hoặc nhiều chữ cái tiếng Anh viết thường. Ví dụ, / lập trình và / lập trình / các vấn đề là các đường dẫn hợp lệ trong khi một chuỗi rỗng và / thì không. Ở đây chúng ta phải triển khai hai chức năng này.
Vì vậy, với tư cách là đầu vào, nếu chúng ta tạo một hệ thống tệp, sau đó tạo một đường dẫn bằng cách sử dụng ['/ a', 1], thì sau khi sử dụng get (), với tham số ['/ a'], đầu ra sẽ là 1.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- Xác định một bản đồ d
- Phương thức createPath sẽ lấy đường dẫn và giá trị, điều này sẽ hoạt động như thế -
- p:=danh sách các thành phần của đường dẫn được phân chia bởi ‘/’
- x:=d
- cho tôi trong phạm vi từ 1 đến độ dài là p - 1
- nếu p [i] không có trong x, thì trả về false
- x:=x [p [i]] [1]
- nếu phần tử cuối cùng của p là x, thì trả về false
- x [phần tử cuối cùng của p]:=danh sách có v và bản đồ trống
- trả về true
- Phương thức get () đang sử dụng đường dẫn
- x:=d
- p:=danh sách các thành phần của đường dẫn được phân chia bởi ‘/’
- cho tôi trong phạm vi từ 1 đến độ dài là p - 1
- nếu p [i] không có trong x, thì trả về -1
- x:=x [p [i]] [1]
- nếu phần tử cuối cùng của p thuộc x, thì trả về x [phần tử cuối cùng của p] [0], nếu không thì trả về -1
Ví dụ (Python)
Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn -
class FileSystem(object):
def __init__(self):
self.d = {}
def create(self, p, v):
p = p.split("/")
x = self.d
for i in range(1,len(p)-1):
if p[i] not in x:
return False
x = x[p[i]][1]
if p[-1] in x:
return False
x[p[-1]] = [v,{}]
return True
def get(self, p):
x = self.d
p = p.split("/")
for i in range(1,len(p)-1):
if p[i] not in x:
return -1
x= x[p[i]][1]
if p[-1] in x:
return x[p[-1]][0]
else:
return -1
ob = FileSystem()
print(ob.create("/a", 1))
print(ob.get("/a")) Đầu vào
Initialize the object, then call createPath(“/a”, 1) and get(“/a”)
Đầu ra
True 1