Không bộ đệm: giảm giá kế thừa
Vì sao điều này quan trọng "Nó lặp lại công việc, nên hãy nhớ các câu trả lời" là một trong những thói quen mạnh nhất trong lập trình, của người hay của AI. Đôi khi công việc hoàn toàn không cần lặp lại.
Các danh mục của một cửa hàng tạo thành một cây: Vườn nằm dưới Nhà, Dụng cụ dưới Vườn, và cứ thế. Một người quản lý tiếp thị có thể đặt giảm giá cho bất kỳ danh mục nào, và nó áp dụng cho mọi thứ bên dưới trừ khi một danh mục gần hơn đặt giảm giá riêng. Trang thanh toán tra giảm giá thực tế cho hàng nghìn danh mục mỗi lần.
Dữ liệu
parents = {"home": None, "garden": "home", "tools": "garden", "seeds": "garden"}
own = {"garden": 10, "seeds": 25} # discounts set directly, in percent
queries = ["tools", "seeds", "home"]
# effective_discounts(parents, own, queries) -> [10, 25, 0]Cách sửa hiển nhiên cho những lần đi ngược lên cây lặp lại là một bộ đệm. Trong bài toán này bộ đệm bị cấm. Hãy tìm một cách mà ngay từ đầu không bao giờ lặp lại công việc.
Viết effective_discounts(parents, own, queries). parents ánh xạ mỗi danh mục tới danh mục cha của nó, hoặc None cho một danh mục cấp cao nhất (có thể có vài cái, và dict không theo thứ tự cụ thể nào). own ánh xạ một số danh mục tới giảm giá riêng của chúng. Với mỗi danh mục trong queries, trả về giảm giá của danh mục gần nhất trên đường đi của nó lên đỉnh, bắt đầu từ chính nó, có giảm giá trong own; 0 nếu không có cái nào. Quy tắc: không bộ đệm hay memo: không decorator bộ đệm của functools, không tên nào chứa "cache" hay "memo", và không tính câu trả lời khi các truy vấn hỏi tới rồi giữ chúng lại (một memo dưới tên khác). Hãy đi qua cả cây trước, rồi mới đọc các truy vấn. Ngân sách: nhiều nhất 500.000 bước (steps()) cho 3.000 danh mục, các cây sâu tới vài trăm tầng, và 20.000 lượt tra.
Bạn thấy vấn đề gì trong bài học này? Hãy báo cáo nó · Hỏi về bài học này
Bài tập này sẽ sớm mở.
Hoàn thành bài học trước đó để mở khóa bài này. Toàn bộ khóa học là miễn phí, không cần tài khoản, và bạn có thể đọc bài học này ngay bây giờ.
Trình duyệt này đang chặn cookie cho learn.floati.life, nên các bài học bạn đã hoàn thành tại đây không thể mở theo thứ tự. Hãy cho phép cookie cho trang web này và tải lại trang.