LeetCode 题解工作台
统计为蚁群构筑房间的不同顺序
你是一只蚂蚁，负责为蚁群构筑 n 间编号从 0 到 n-1 的新房间。给你一个 下标从 0 开始 且长度为 n 的整数数组 prevRoom 作为扩建计划。其中， prevRoom[i] 表示在构筑房间 i 之前，你必须先构筑房间 prevRoom[i] ，并且这两个房间必须 直接 相连。房间 0 …
6
题型
1
代码语言
3
相关题
当前训练重点
困难 · 动态·规划
答案摘要
class Solution: def waysToBuildRooms(self, prevRoom: List[int]) -> int:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 动态·规划 题型思路
题目描述
你是一只蚂蚁，负责为蚁群构筑 n 间编号从 0 到 n-1 的新房间。给你一个 下标从 0 开始 且长度为 n 的整数数组 prevRoom 作为扩建计划。其中，prevRoom[i] 表示在构筑房间 i 之前，你必须先构筑房间 prevRoom[i] ，并且这两个房间必须 直接 相连。房间 0 已经构筑完成，所以 prevRoom[0] = -1 。扩建计划中还有一条硬性要求，在完成所有房间的构筑之后，从房间 0 可以访问到每个房间。
你一次只能构筑 一个 房间。你可以在 已经构筑好的 房间之间自由穿行，只要这些房间是 相连的 。如果房间 prevRoom[i] 已经构筑完成，那么你就可以构筑房间 i。
返回你构筑所有房间的 不同顺序的数目 。由于答案可能很大，请返回对 109 + 7 取余 的结果。
示例 1：
输入：prevRoom = [-1,0,1]
输出：1
解释：仅有一种方案可以完成所有房间的构筑：0 → 1 → 2
示例 2：
输入：prevRoom = [-1,0,0,1,2]
输出：6
解释：
有 6 种不同顺序：
0 → 1 → 3 → 2 → 4
0 → 2 → 4 → 1 → 3
0 → 1 → 2 → 3 → 4
0 → 1 → 2 → 4 → 3
0 → 2 → 1 → 3 → 4
0 → 2 → 1 → 4 → 3
提示：
n == prevRoom.length2 <= n <= 105prevRoom[0] == -1- 对于所有的
1 <= i < n，都有0 <= prevRoom[i] < n - 题目保证所有房间都构筑完成后，从房间
0可以访问到每个房间
解题思路
方法一
class Solution:
def waysToBuildRooms(self, prevRoom: List[int]) -> int:
modulo = 10**9 + 7
ingoing = defaultdict(set)
outgoing = defaultdict(set)
for i in range(1, len(prevRoom)):
ingoing[i].add(prevRoom[i])
outgoing[prevRoom[i]].add(i)
ans = [1]
def recurse(i):
if len(outgoing[i]) == 0:
return 1
nodes_in_tree = 0
for v in outgoing[i]:
cn = recurse(v)
if nodes_in_tree != 0:
ans[0] *= comb(nodes_in_tree + cn, cn)
ans[0] %= modulo
nodes_in_tree += cn
return nodes_in_tree + 1
recurse(0)
return ans[0] % modulo
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidate understands how to apply topological sorting to a graph problem.
- question_mark
The solution efficiently handles modular arithmetic, especially when working with large numbers.
- question_mark
Candidate demonstrates the ability to optimize the solution for large inputs.
常见陷阱
外企场景- error
Forgetting to handle modular arithmetic can lead to integer overflow or incorrect results.
- error
Mistaking the topological order for a random order, which could lead to incorrect build sequences.
- error
Not efficiently calculating the number of ways to build rooms, leading to excessive time or space complexity.
进阶变体
外企场景- arrow_right_alt
Consider cases where some rooms are isolated or have different dependencies.
- arrow_right_alt
Introduce additional constraints, such as room limits or restricted building times, to add complexity.
- arrow_right_alt
What if there are multiple paths with different costs to build rooms?