Design Underground System (LeetCode 1396)

Nguồn: LeetCode 1396 Độ khó: Trung bình Cấu trúc dữ liệu Thiết kế Map

Đề bài

🇻🇳 Tiếng Việt🇬🇧 English (đề gốc)

LeetCode 1396 – Design Underground System (Thiết kế hệ thống tàu điện ngầm) – độ khó Medium.

Một hệ thống tàu điện ngầm đang theo dõi thời gian di chuyển của khách hàng giữa các ga khác nhau. Họ dùng dữ liệu này để tính thời gian trung bình để đi từ một ga tới một ga khác.

Hãy cài đặt lớp UndergroundSystem:

void checkIn(int id, string stationName, int t)
- Một khách hàng có mã thẻ là id quẹt thẻ vào (check in) tại ga stationName ở thời điểm t.
- Tại mỗi thời điểm, một khách hàng chỉ có thể đang check in ở một nơi.
void checkOut(int id, string stationName, int t)
- Một khách hàng có mã thẻ là id quẹt thẻ ra (check out) tại ga stationName ở thời điểm t.
double getAverageTime(string startStation, string endStation)
- Trả về thời gian trung bình để đi từ ga startStation tới ga endStation.
- Thời gian trung bình được tính từ tất cả các lần di chuyển trước đó từ startStation tới endStation diễn ra trực tiếp, nghĩa là check in tại startStation rồi check out tại endStation.
- Thời gian đi từ startStation tới endStation có thể khác thời gian đi từ endStation tới startStation.
- Đảm bảo đã có ít nhất một khách hàng đi từ startStation tới endStation trước khi getAverageTime được gọi.

Bạn có thể giả sử mọi lời gọi checkIn và checkOut đều hợp lệ. Nếu một khách hàng check in tại thời điểm $t_1$ rồi check out tại thời điểm $t_2$ thì $t_1 \lt t_2$. Mọi sự kiện diễn ra theo thứ tự thời gian.

Ràng buộc:

$1 \le$ id, t $\le 10^6$
$1 \le$ stationName.length, startStation.length, endStation.length $\le 10$
Mọi xâu chỉ gồm chữ cái tiếng Anh in hoa, in thường và chữ số.
Có tổng cộng nhiều nhất $2 \cdot 10^4$ lời gọi tới checkIn, checkOut và getAverageTime.
Đáp án sai khác giá trị thật không quá $10^{-5}$ được chấp nhận.

Ví dụ 1:

Input
["UndergroundSystem","checkIn","checkIn","checkIn","checkOut","checkOut","checkOut","getAverageTime","getAverageTime","checkIn","getAverageTime","checkOut","getAverageTime"]
[[],[45,"Leyton",3],[32,"Paradise",8],[27,"Leyton",10],[45,"Waterloo",15],[27,"Waterloo",20],[32,"Cambridge",22],["Paradise","Cambridge"],["Leyton","Waterloo"],[10,"Leyton",24],["Leyton","Waterloo"],[10,"Waterloo",38],["Leyton","Waterloo"]]

Output
[null,null,null,null,null,null,null,14.00000,11.00000,null,11.00000,null,12.00000]

Giải thích:

UndergroundSystem undergroundSystem = new UndergroundSystem();
undergroundSystem.checkIn(45, "Leyton", 3);
undergroundSystem.checkIn(32, "Paradise", 8);
undergroundSystem.checkIn(27, "Leyton", 10);
undergroundSystem.checkOut(45, "Waterloo", 15);  // Khách 45: "Leyton" -> "Waterloo" mất 15-3 = 12
undergroundSystem.checkOut(27, "Waterloo", 20);  // Khách 27: "Leyton" -> "Waterloo" mất 20-10 = 10
undergroundSystem.checkOut(32, "Cambridge", 22); // Khách 32: "Paradise" -> "Cambridge" mất 22-8 = 14
undergroundSystem.getAverageTime("Paradise", "Cambridge"); // trả về 14.00000. Một chuyến "Paradise" -> "Cambridge", (14) / 1 = 14
undergroundSystem.getAverageTime("Leyton", "Waterloo");    // trả về 11.00000. Hai chuyến "Leyton" -> "Waterloo", (10 + 12) / 2 = 11
undergroundSystem.checkIn(10, "Leyton", 24);
undergroundSystem.getAverageTime("Leyton", "Waterloo");    // trả về 11.00000
undergroundSystem.checkOut(10, "Waterloo", 38);  // Khách 10: "Leyton" -> "Waterloo" mất 38-24 = 14
undergroundSystem.getAverageTime("Leyton", "Waterloo");    // trả về 12.00000. Ba chuyến "Leyton" -> "Waterloo", (10 + 12 + 14) / 3 = 12

Ví dụ 2:

Input
["UndergroundSystem","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime"]
[[],[10,"Leyton",3],[10,"Paradise",8],["Leyton","Paradise"],[5,"Leyton",10],[5,"Paradise",16],["Leyton","Paradise"],[2,"Leyton",21],[2,"Paradise",30],["Leyton","Paradise"]]

Output
[null,null,null,5.00000,null,null,5.50000,null,null,6.66667]

Giải thích:

UndergroundSystem undergroundSystem = new UndergroundSystem();
undergroundSystem.checkIn(10, "Leyton", 3);
undergroundSystem.checkOut(10, "Paradise", 8); // Khách 10: "Leyton" -> "Paradise" mất 8-3 = 5
undergroundSystem.getAverageTime("Leyton", "Paradise"); // trả về 5.00000, (5) / 1 = 5
undergroundSystem.checkIn(5, "Leyton", 10);
undergroundSystem.checkOut(5, "Paradise", 16); // Khách 5: "Leyton" -> "Paradise" mất 16-10 = 6
undergroundSystem.getAverageTime("Leyton", "Paradise"); // trả về 5.50000, (5 + 6) / 2 = 5.5
undergroundSystem.checkIn(2, "Leyton", 21);
undergroundSystem.checkOut(2, "Paradise", 30); // Khách 2: "Leyton" -> "Paradise" mất 30-21 = 9
undergroundSystem.getAverageTime("Leyton", "Paradise"); // trả về 6.66667, (5 + 6 + 9) / 3 = 6.66667

1396. Design Underground System – Medium.

An underground railway system is keeping track of customer travel times between different stations. They are using this data to calculate the average time it takes to travel from one station to another.

Implement the UndergroundSystem class:

void checkIn(int id, string stationName, int t)
- A customer with a card ID equal to id, checks in at the station stationName at time t.
- A customer can only be checked into one place at a time.
void checkOut(int id, string stationName, int t)
- A customer with a card ID equal to id, checks out from the station stationName at time t.
double getAverageTime(string startStation, string endStation)
- Returns the average time it takes to travel from startStation to endStation.
- The average time is computed from all the previous traveling times from startStation to endStation that happened directly, meaning a check in at startStation followed by a check out from endStation.
- The time it takes to travel from startStation to endStation may be different from the time it takes to travel from endStation to startStation.
- There will be at least one customer that has traveled from startStation to endStation before getAverageTime is called.

You may assume all calls to the checkIn and checkOut methods are consistent. If a customer checks in at time $t_1$ then checks out at time $t_2$, then $t_1 \lt t_2$. All events happen in chronological order.

Constraints:

1 <= id, t <= 10^6
1 <= stationName.length, startStation.length, endStation.length <= 10
All strings consist of uppercase and lowercase English letters and digits.
There will be at most 2 * 10^4 calls in total to checkIn, checkOut, and getAverageTime.
Answers within 10^-5 of the actual value will be accepted.

Example 1:

Input
["UndergroundSystem","checkIn","checkIn","checkIn","checkOut","checkOut","checkOut","getAverageTime","getAverageTime","checkIn","getAverageTime","checkOut","getAverageTime"]
[[],[45,"Leyton",3],[32,"Paradise",8],[27,"Leyton",10],[45,"Waterloo",15],[27,"Waterloo",20],[32,"Cambridge",22],["Paradise","Cambridge"],["Leyton","Waterloo"],[10,"Leyton",24],["Leyton","Waterloo"],[10,"Waterloo",38],["Leyton","Waterloo"]]

Output
[null,null,null,null,null,null,null,14.00000,11.00000,null,11.00000,null,12.00000]

Explanation:

UndergroundSystem undergroundSystem = new UndergroundSystem();
undergroundSystem.checkIn(45, "Leyton", 3);
undergroundSystem.checkIn(32, "Paradise", 8);
undergroundSystem.checkIn(27, "Leyton", 10);
undergroundSystem.checkOut(45, "Waterloo", 15);  // Customer 45 "Leyton" -> "Waterloo" in 15-3 = 12
undergroundSystem.checkOut(27, "Waterloo", 20);  // Customer 27 "Leyton" -> "Waterloo" in 20-10 = 10
undergroundSystem.checkOut(32, "Cambridge", 22); // Customer 32 "Paradise" -> "Cambridge" in 22-8 = 14
undergroundSystem.getAverageTime("Paradise", "Cambridge"); // return 14.00000. One trip "Paradise" -> "Cambridge", (14) / 1 = 14
undergroundSystem.getAverageTime("Leyton", "Waterloo");    // return 11.00000. Two trips "Leyton" -> "Waterloo", (10 + 12) / 2 = 11
undergroundSystem.checkIn(10, "Leyton", 24);
undergroundSystem.getAverageTime("Leyton", "Waterloo");    // return 11.00000
undergroundSystem.checkOut(10, "Waterloo", 38);  // Customer 10 "Leyton" -> "Waterloo" in 38-24 = 14
undergroundSystem.getAverageTime("Leyton", "Waterloo");    // return 12.00000. Three trips "Leyton" -> "Waterloo", (10 + 12 + 14) / 3 = 12

Example 2:

Input
["UndergroundSystem","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime"]
[[],[10,"Leyton",3],[10,"Paradise",8],["Leyton","Paradise"],[5,"Leyton",10],[5,"Paradise",16],["Leyton","Paradise"],[2,"Leyton",21],[2,"Paradise",30],["Leyton","Paradise"]]

Output
[null,null,null,5.00000,null,null,5.50000,null,null,6.66667]

Explanation:

UndergroundSystem undergroundSystem = new UndergroundSystem();
undergroundSystem.checkIn(10, "Leyton", 3);
undergroundSystem.checkOut(10, "Paradise", 8); // Customer 10 "Leyton" -> "Paradise" in 8-3 = 5
undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 5.00000, (5) / 1 = 5
undergroundSystem.checkIn(5, "Leyton", 10);
undergroundSystem.checkOut(5, "Paradise", 16); // Customer 5 "Leyton" -> "Paradise" in 16-10 = 6
undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 5.50000, (5 + 6) / 2 = 5.5
undergroundSystem.checkIn(2, "Leyton", 21);
undergroundSystem.checkOut(2, "Paradise", 30); // Customer 2 "Leyton" -> "Paradise" in 30-21 = 9
undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 6.66667, (5 + 6 + 9) / 3 = 6.66667

Lời mở đầu

Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇.

Tóm tắt đề bài: ta cần thiết kế một hệ thống Checkin – Checkout cho các khách hàng. Có một danh sách các sự kiện, mỗi sự kiện thuộc 1 trong 3 loại:

checkIn(id, stationName, t): vị khách có số hiệu id đã đến ga stationName tại thời điểm t.
checkOut(id, stationName, t): vị khách có số hiệu id đã rời đi tại ga stationName tại thời điểm t.
getAverageTime(startStation, endStation): tính trung bình cộng khoảng thời gian của các vị khách đã checkin tại startStation và checkout tại endStation.

Mình giải thích lại Ví dụ 1 cho bạn nào chưa hiểu: khách 45 vào ở Leyton lúc 3, ra ở Waterloo lúc 15 ⇒ chuyến Leyton → Waterloo mất 12. Khách 27 cũng đi Leyton → Waterloo, mất $20 - 10 = 10$. Nên khi hỏi trung bình Leyton → Waterloo ta có $(12 + 10) / 2 = 11$. Lúc khách 10 mới check in ở Leyton (thời điểm 24) thì chưa có chuyến mới nào hoàn thành, nên hỏi lại vẫn ra 11. Khách 10 check out ở Waterloo lúc 38 (mất 14) thì trung bình thành $(12 + 10 + 14) / 3 = 12$. Chú ý chiều đi là quan trọng: Leyton → Waterloo khác Waterloo → Leyton.

Về dữ liệu vào / ra của code trong bài

Trên LeetCode các bạn chỉ cần nộp phần class UndergroundSystem (cùng các biến toàn cục phía trên nó). Để các bạn chạy thử được trên máy (hoặc trang Chạy code online), code trong bài có thêm hàm main đọc từ bàn phím theo định dạng: dòng đầu là số thao tác $q$ (không tính lời gọi khởi tạo), mỗi dòng sau là một thao tác dạng checkIn id tên_ga t, checkOut id tên_ga t hoặc getAverageTime ga_đi ga_đến. Với mỗi lệnh getAverageTime, chương trình in kết quả trên một dòng, lấy 5 chữ số sau dấu phẩy. Ví dụ 2 sẽ nhập là:

9
checkIn 10 Leyton 3
checkOut 10 Paradise 8
getAverageTime Leyton Paradise
checkIn 5 Leyton 10
checkOut 5 Paradise 16
getAverageTime Leyton Paradise
checkIn 2 Leyton 21
checkOut 2 Paradise 30
getAverageTime Leyton Paradise

và in ra 5.00000, 5.50000, 6.66667 trên 3 dòng.

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào để nhảy tới:

Cách 1Số hoá tên ga + cộng dồn tổng thời gian và số chuyến bằng map · O(Q log Q)

Cách 1Số hoá tên ga + cộng dồn bằng map – O(Q log Q)

Phương pháp giải: cấu trúc dữ liệu. Độ phức tạp $O(Q \log Q)$ với $Q$ là số lời gọi hàm.

Bước 1: "số hoá" tên ga

Ta cần gán cho những nơi ta checkin và checkout những id (số hiệu) nhằm mục đích "số hoá" những giá trị chuỗi, chứ không nên để nguyên chuỗi để tính toán. Ta tạo một ánh xạ string → int (biến ID): lần đầu gặp một tên ga thì cấp cho nó số hiệu tiếp theo $1, 2, 3, \ldots$, các lần sau chỉ việc tra lại. Đó là hàm getID trong code.

Ví dụ 1: Leyton → 1, Paradise → 2, Waterloo → 3, Cambridge → 4 (theo thứ tự xuất hiện lần đầu).

Bước 2: hai bảng cộng dồn

Gọi totalTime[idStart][idEnd] là tổng thời gian của những người checkin tại ga có số hiệu idStart và checkout tại ga có số hiệu idEnd; numb[idStart][idEnd] là số lượng người checkin tại idStart và checkout tại idEnd.

Hàm checkIn: ta dùng in[id] lưu số hiệu của ga mà vị khách id đang checkin, và lưu thêm thời điểm t checkin của vị khách đó.
Hàm checkOut: truy cập tới in[id] để lấy số hiệu ga đã checkin (gọi là id1) và thời điểm checkin. Ga đang checkout gọi là id2. Ta cộng vào totalTime[id1][id2] một khoảng thời gian là t - in[id].second, tức thời gian checkout trừ thời gian checkin, đồng thời tăng numb[id1][id2] lên 1 đơn vị.
Hàm getAverageTime: tìm số hiệu ga checkin và ga checkout, lấy totalTime[id1][id2] / numb[id1][id2] và trả về kết quả.

Ý chính

Trung bình cộng = tổng ÷ số lượng. Nên với mỗi cặp ga (có thứ tự) ta chỉ cần giữ 2 con số: tổng thời gian và số chuyến. Mỗi lần có khách check out ta cập nhật 2 con số này trong $O(\log)$, hỏi lúc nào cũng trả lời ngay được bằng 1 phép chia – không cần lưu lại từng chuyến đi.

Vì phải xử lý với chuỗi, nên sumTime, cnt (ở đây là totalTime, numb) có thể dùng map, unordered_map (hashmap) hoặc dict trong Python. Trong code của mình, totalTime[i] là một mảng các map<int, long long>: chỉ số thứ nhất là ga đi (tra trực tiếp), ga đến là khoá của map.

Minh hoạ từng thao tác

Em nhập danh sách thao tác (cách nhau dấu ;, viết tắt in id ga t, out id ga t, avg ga_đi ga_đến) rồi bấm Tiếp để xem các bảng thay đổi ra sao:

Thao tác

Ví dụ nhanh:

Code dưới đây của mình đã AC với tư tưởng đã trình bày ở trên, anh em có thể tham khảo nhé (phần main chỉ để chạy thử trên máy, nộp LeetCode thì bỏ đi):

#include <bits/stdc++.h>
using namespace std;

map <int, long long> totalTime[20005];
map <int, int> numb[20005];
map <string, int> ID;
pair <int, int> in[1000005];

class UndergroundSystem {
public:
    UndergroundSystem() {
        for (int i = 1; i <= 20000; i++) {
            totalTime[i].clear();
            numb[i].clear();
        }
        ID.clear();
    }

    int getID(const string &s) {
        if (ID.find(s) == ID.end()) {
            int sz = (int) ID.size();
            ID[s] = sz + 1;
        }
        return ID[s];
    }

    void checkIn(int id, string stationName, int t) {
        int idStation = getID(stationName);
        in[id] = make_pair(idStation, t);
    }

    void checkOut(int id, string stationName, int t) {
        int id2 = getID(stationName);
        int id1 = in[id].first;
        totalTime[id1][id2] += t - in[id].second;
        numb[id1][id2]++;
    }

    double getAverageTime(string startStation, string endStation) {
        int idStart = getID(startStation);
        int idEnd = getID(endStation);
        return 1.0 * totalTime[idStart][idEnd] / numb[idStart][idEnd];
    }
};

int main() {
    int q;
    cin >> q;
    UndergroundSystem obj;
    cout << fixed << setprecision(5);
    while (q--) {
        string type;
        cin >> type;
        if (type == "checkIn") {
            int id, t;
            string name;
            cin >> id >> name >> t;
            obj.checkIn(id, name, t);
        } else if (type == "checkOut") {
            int id, t;
            string name;
            cin >> id >> name >> t;
            obj.checkOut(id, name, t);
        } else {
            string s, e;
            cin >> s >> e;
            cout << obj.getAverageTime(s, e) << "\n";
        }
    }
    return 0;
}

import sys

class UndergroundSystem:
    def __init__(self):
        self.ID = {}             # tên ga -> số hiệu 1, 2, 3...
        self.inp = {}            # id khách -> (số hiệu ga checkin, thời điểm)
        self.totalTime = {}      # (id1, id2) -> tổng thời gian
        self.numb = {}           # (id1, id2) -> số chuyến

    def getID(self, s: str) -> int:
        if s not in self.ID:
            self.ID[s] = len(self.ID) + 1
        return self.ID[s]

    def checkIn(self, id: int, stationName: str, t: int) -> None:
        self.inp[id] = (self.getID(stationName), t)

    def checkOut(self, id: int, stationName: str, t: int) -> None:
        id2 = self.getID(stationName)
        id1, t1 = self.inp[id]
        key = (id1, id2)
        self.totalTime[key] = self.totalTime.get(key, 0) + t - t1
        self.numb[key] = self.numb.get(key, 0) + 1

    def getAverageTime(self, startStation: str, endStation: str) -> float:
        key = (self.getID(startStation), self.getID(endStation))
        return self.totalTime[key] / self.numb[key]

def main():
    data = sys.stdin.read().split()
    q = int(data[0])
    p = 1
    obj = UndergroundSystem()
    out = []
    for _ in range(q):
        typ = data[p]
        if typ == "checkIn":
            obj.checkIn(int(data[p + 1]), data[p + 2], int(data[p + 3]))
            p += 4
        elif typ == "checkOut":
            obj.checkOut(int(data[p + 1]), data[p + 2], int(data[p + 3]))
            p += 4
        else:
            out.append("%.5f" % obj.getAverageTime(data[p + 1], data[p + 2]))
            p += 3
    if out:
        print("\n".join(out))

main()

Giải thích một số chỗ trong code:

Các bảng totalTime, numb, ID, in khai báo toàn cục. LeetCode chạy nhiều test trên cùng một chương trình (mỗi test tạo một đối tượng mới), nên trong hàm khởi tạo UndergroundSystem() mình clear lại hết cho sạch.
Kích thước mảng totalTime[20005] đủ dùng vì tổng số lời gọi tối đa $2 \cdot 10^4$, mỗi lời gọi checkIn/checkOut thêm tối đa 1 tên ga mới ⇒ không quá $2 \cdot 10^4$ ga khác nhau. Còn in[1000005] thì đánh chỉ số thẳng bằng id (vì $id \le 10^6$).
Không cần xoá in[id] khi khách check out: lần check in sau của khách đó sẽ ghi đè lên.
1.0 * totalTime[...] / numb[...]: nhân với 1.0 để phép chia là chia số thực chứ không phải chia nguyên.

Chú ý chiều đi

Cặp (đi, đến) là cặp có thứ tự: chuyến A → B và B → A phải cộng vào 2 ô khác nhau (totalTime[1][2] khác totalTime[2][1]). Bạn nào ghép khoá kiểu "sắp xếp 2 tên ga cho gọn" là sai ngay. Em bấm nút "Hai chiều khác nhau" ở khung minh hoạ phía trên để thấy.

Cách "ngây thơ" để so sánh

Nếu lưu lại toàn bộ các chuyến đi (ga đi, ga đến, thời gian) rồi mỗi lần hỏi lại duyệt hết danh sách để tính trung bình thì mỗi câu hỏi tốn $O(Q)$, cả bài $O(Q^2)$. Với $Q = 2 \cdot 10^4$ có thể vẫn qua, nhưng cách cộng dồn ở trên vừa gọn vừa nhanh hơn hẳn. Mình dùng chính cách ngây thơ này làm code vét cạn để kiểm tra code ở trên.

Em có thể chạy tay từng dòng code C++ ở khung dưới đây (mỗi dòng của stdin là một thao tác như mình mô tả ở phần Lời mở đầu):

C++▶ Chạy tay từng dòng codeSố hoá tên ga bằng map ID, cộng dồn totalTime và numb theo cặp (ga đi, ga đến).

Dữ liệu vào (stdin) – sửa thoải mái

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

4map <int, long long> totalTime[20005];

5map <int, int> numb[20005];

6map <string, int> ID;

7pair <int, int> in[1000005];

9class UndergroundSystem {

10public:

11 UndergroundSystem() {

12 for (int i = 1; i <= 20000; i++) {

13 totalTime[i].clear();

14 numb[i].clear();

15 }

16 ID.clear();

17 }

19 int getID(const string &s) {

20 if (ID.find(s) == ID.end()) {

21 int sz = (int) ID.size();

22 ID[s] = sz + 1;

23 }

24 return ID[s];

25 }

27 void checkIn(int id, string stationName, int t) {

28 int idStation = getID(stationName);

29 in[id] = make_pair(idStation, t);

30 }

32 void checkOut(int id, string stationName, int t) {

33 int id2 = getID(stationName);

34 int id1 = in[id].first;

35 totalTime[id1][id2] += t - in[id].second;

36 numb[id1][id2]++;

37 }

39 double getAverageTime(string startStation, string endStation) {

40 int idStart = getID(startStation);

41 int idEnd = getID(endStation);

42 return 1.0 * totalTime[idStart][idEnd] / numb[idStart][idEnd];

43 }

44};

46int main() {

47 int q;

48 cin >> q;

49 UndergroundSystem obj;

50 cout << fixed << setprecision(5);

51 while (q--) {

52 string type;

53 cin >> type;

54 if (type == "checkIn") {

55 int id, t;

56 string name;

57 cin >> id >> name >> t;

58 obj.checkIn(id, name, t);

59 } else if (type == "checkOut") {

60 int id, t;

61 string name;

62 cin >> id >> name >> t;

63 obj.checkOut(id, name, t);

64 } else {

65 string s, e;

66 cin >> s >> e;

67 cout << obj.getAverageTime(s, e) << "\n";

68 }

69 }

70 return 0;

71}

Đánh giá độ phức tạp của cách làm này:

Thời gian: mỗi lời gọi chỉ làm vài thao tác trên map (tra/thêm tên ga, cộng vào ô totalTime[id1][id2]), mỗi thao tác $O(\log Q)$ (so sánh xâu dài tối đa 10 ký tự) ⇒ tổng $O(Q \log Q)$. Hàm khởi tạo có thêm vòng lặp $2 \cdot 10^4$ lần để clear, không đáng kể.
Không gian: $O(Q)$ cho các map, cộng thêm mảng in cỡ $10^6$ phần tử.

Không gian$O(Q + \max id)$

Thời gian$O(Q \log Q)$

Ghi chú của mình: code C++ và Python ở trên đã chạy đúng 2 ví dụ của đề, và được kiểm tra với 500 bộ test ngẫu nhiên nhỏ, so với code vét cạn (lưu lại mọi chuyến đi, hỏi thì duyệt lại) – khớp hết. Với $2 \cdot 10^4$ thao tác (id tới $10^6$, gần 4000 tên ga khác nhau), cả hai bản đều chạy dưới 0.3 giây.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇

Lập Trình Thuật Toán

Design Underground System (LeetCode 1396)

Đề bài

Lời mở đầu

Cách 1Số hoá tên ga + cộng dồn bằng map – O(Q log Q)

Bước 1: "số hoá" tên ga

Bước 2: hai bảng cộng dồn

Minh hoạ từng thao tác

Nhận xét

Đăng nhận xét

Dữ liệu trang web (tự động – không xoá)

Hướng dẫn tham gia Thi thử HSG Tin học hàng tuần trên ClueOJ (từ đăng ký tài khoản đến lúc vào phòng thi)

Khóa học luyện thi chuyên Tin, HSG Tin học – lập trình thuật toán C++