课程大纲 第 134 课,共 148 课 · 打败你的幽灵
打败你的幽灵

不用缓存:继承的折扣

为什么重要 “它在重复工作,所以把答案记下来”是编程中最强的习惯之一,不管是人还是 AI。有时候,这项工作根本就不需要重复。

一家商店的类别构成一棵树:Garden 在 Home 下面,Tools 在 Garden 下面,以此类推。一位市场经理可以给任意一个类别设置折扣,它会应用到它下面的所有东西上,除非一个更近的类别设置了自己的折扣。结账时会一次查询成千上万个类别的有效折扣。

数据

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]

对于沿着树反复往上走,显而易见的修复办法是缓存。在这道题里,缓存是被禁止的。去找一种从一开始就不会重复工作的办法。

轮到你了

编写 effective_discounts(parents, own, queries)。parents 把每个类别映射到它的父类别,对于顶层类别则映射到 None(可能有好几个,而且字典没有特定的顺序)。own 把某些类别映射到它们自己的折扣。对于 queries 中的每一个类别,返回从它自己开始、在它通往顶层的路径上最近的那个在 own 中有折扣的类别的折扣;如果都没有,就是 0。规则:不用缓存或备忘:不用 functools 的缓存装饰器,不用任何包含 "cache" 或 "memo" 的名字,也不要在查询要求时才算出答案并把它们保存起来(那是换了个名字的备忘)。先遍历整棵树,然后再读查询。预算:对于 3,000 个类别、最深几百层的树和 20,000 次查询,最多 500,000 步(steps())。

发现这节课有问题?报告它 · 就这节课提问

这个练习即将开放

完成它前面的那一课,这一课就会解锁。整门课程免费,无需账号,而且你现在就可以阅读这节课。