注册一亩三分地论坛,查看更多干货!
您需要 登录 才可以下载或查看附件。没有帐号?注册账号 
x
Part 1: 单位转换 (LC)
【题目类型】 Graph / Tree Traversal (图/树遍历)
【题目描述】
给定一系列单位之间的转换关系,要求计算出所有相连单位相对于某个起始单位的等效数值。
如果单位 A 可以转换为单位 B,转换系数为 x,且 A 的数值为 v,那么 B 的数值就是 v * x。
【解题思路】
非常经典的带权图遍历题。可以将转换关系看作是一个带权重的无向图(或有向树)。
从基础单位(Base Unit)开始,使用 DFS 或 BFS 进行遍历。在遍历的过程中,将累乘的转换系数(accumulated magnitude)沿着每一条边传递下去即可。
时间复杂度:O(N),N 为单位的数量。
空间复杂度:O(ticket not found"
【核心 Debug 洞察 / 坑点】
这道题极其考验多层级(DB、生命周期、库存、Redis)的一致性。最容易漏掉的 Bug 是:Redis helper 函数虽然构建了 hold key,但并没有真正执行删除操作。另外要注意状态判断的先后顺序(比如先判断找不到,再判断是不是过期)。 |