Đề bài
Ứng dụng việc cần làm lưu công việc trong một collection có kiểu như List<T>. Mỗi công việc có tiêu đề và cờ đã xong.
Bắt đầu với danh sách rỗng và xử lý các thao tác, mỗi thao tác gồm lệnh và tiêu đề (tiêu đề là toàn bộ phần sau khoảng trắng đầu tiên):
add <title>: thêm một việc chưa xong vào cuối, trừ khi đã có việc cùng tiêu đề.done <title>: đánh dấu việc đó là xong (không có tác dụng nếu không tồn tại).remove <title>: xóa việc đó (không có tác dụng nếu không tồn tại).
Hãy viết todo_list(operations).
Đầu vào
operations: Các thao tác. Tiêu đề có thể chứa khoảng trắng và được so sánh chính xác.
Đầu ra
Trả về tiêu đề các việc chưa xong, theo thứ tự được thêm.
Ràng buộc
0 ≤ số thao tác ≤ 10,000
Tiêu đề dài 1 đến 50 ký tự
Ví dụ
Đầu vào:
operations = ["add Buy milk", "add Write report", "done Buy milk", "add Call Ada"]
Kết quả mong đợi:
expected = ["Write report", "Call Ada"]
Đầu vào:
std::vector<std::string> operations = {"add Buy milk", "add Write report", "done Buy milk", "add Call Ada"};
Kết quả mong đợi:
std::vector<std::string> expected = {"Write report", "Call Ada"};
Đầu vào:
string[] operations = new string[] {"add Buy milk", "add Write report", "done Buy milk", "add Call Ada"};
Kết quả mong đợi:
string[] expected = new string[] {"Write report", "Call Ada"};
Giải thích
Buy milk đã xong nên chỉ còn hai việc kia, theo thứ tự thêm vào: ["Write report", "Call Ada"].
Đầu vào:
operations = ["add Gym", "add Gym", "remove Gym", "done Gym"]
Kết quả mong đợi:
expected = []
Đầu vào:
std::vector<std::string> operations = {"add Gym", "add Gym", "remove Gym", "done Gym"};
Kết quả mong đợi:
std::vector<std::string> expected = {};
Đầu vào:
string[] operations = new string[] {"add Gym", "add Gym", "remove Gym", "done Gym"};
Kết quả mong đợi:
string[] expected = new string[] {};
Giải thích
Lệnh add thứ hai bị bỏ qua vì Gym đã có; xóa nó thì không còn gì, và done với việc không tồn tại không có tác dụng: [].
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Lưu mỗi công việc thành một record nhỏ gồm tiêu đề và trạng thái xong.
Gợi ý 2
Tìm công việc theo đúng tiêu đề trước khi thêm, đánh dấu xong hoặc xóa.
Gợi ý 3
Cuối cùng chỉ giữ các việc chưa xong, theo thứ tự thêm vào.
Độ phức tạp mong đợi
thời gian O(n²), bộ nhớ phụ O(n)
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.