LeetCode 题解工作台
移除可疑的方法
你正在维护一个项目，该项目有 n 个方法，编号从 0 到 n - 1 。 给你两个整数 n 和 k ，以及一个二维整数数组 invocations ，其中 invocations[i] = [a i , b i ] 表示方法 a i 调用了方法 b i 。 已知如果方法 k 存在一个已知的 bug。…
3
题型
5
代码语言
3
相关题
当前训练重点
中等 · 图·DFS·traversal
答案摘要
我们可以先从 出发，找到所有可疑方法，用数组 记录。然后再从 到 遍历，从所有不可疑方法出发，将所有可达的方法标记为不可疑方法。最后返回所有不可疑方法。 时间复杂度 $O(n + m)$，空间复杂度 $O(n + m)$。其中 和 分别表示方法数量和调用关系数量。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 图·DFS·traversal 题型思路
题目描述
你正在维护一个项目，该项目有 n 个方法，编号从 0 到 n - 1。
给你两个整数 n 和 k，以及一个二维整数数组 invocations，其中 invocations[i] = [ai, bi] 表示方法 ai 调用了方法 bi。
已知如果方法 k 存在一个已知的 bug。那么方法 k 以及它直接或间接调用的任何方法都被视为 可疑方法 ，我们需要从项目中移除这些方法。
只有当一组方法没有被这组之外的任何方法调用时，这组方法才能被移除。
返回一个数组，包含移除所有 可疑方法 后剩下的所有方法。你可以以任意顺序返回答案。如果无法移除 所有 可疑方法，则 不 移除任何方法。
示例 1:
输入: n = 4, k = 1, invocations = [[1,2],[0,1],[3,2]]
输出: [0,1,2,3]
解释:
方法 2 和方法 1 是可疑方法，但它们分别直接被方法 3 和方法 0 调用。由于方法 3 和方法 0 不是可疑方法，我们无法移除任何方法，故返回所有方法。
示例 2:
输入: n = 5, k = 0, invocations = [[1,2],[0,2],[0,1],[3,4]]
输出: [3,4]
解释:
方法 0、方法 1 和方法 2 是可疑方法，且没有被任何其他方法直接调用。我们可以移除它们。
示例 3:
输入: n = 3, k = 2, invocations = [[1,2],[0,1],[2,0]]
输出: []
解释:
所有方法都是可疑方法。我们可以移除它们。
提示:
1 <= n <= 1050 <= k <= n - 10 <= invocations.length <= 2 * 105invocations[i] == [ai, bi]0 <= ai, bi <= n - 1ai != biinvocations[i] != invocations[j]
解题思路
方法一：两次 DFS
我们可以先从 出发，找到所有可疑方法，用数组 记录。然后再从 到 遍历，从所有不可疑方法出发，将所有可达的方法标记为不可疑方法。最后返回所有不可疑方法。
时间复杂度 ，空间复杂度 。其中 和 分别表示方法数量和调用关系数量。
class Solution:
def remainingMethods(
self, n: int, k: int, invocations: List[List[int]]
) -> List[int]:
def dfs(i: int):
suspicious[i] = True
for j in g[i]:
if not suspicious[j]:
dfs(j)
def dfs2(i: int):
vis[i] = True
for j in f[i]:
if not vis[j]:
suspicious[j] = False
dfs2(j)
f = [[] for _ in range(n)]
g = [[] for _ in range(n)]
for a, b in invocations:
f[a].append(b)
f[b].append(a)
g[a].append(b)
suspicious = [False] * n
dfs(k)
vis = [False] * n
ans = []
for i in range(n):
if not suspicious[i] and not vis[i]:
dfs2(i)
return [i for i in range(n) if not suspicious[i]]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Tests the candidate's ability to apply graph traversal techniques, especially DFS.
- question_mark
Evaluates the candidate's understanding of handling large inputs efficiently.
- question_mark
Assesses problem-solving abilities with edge cases and graph traversal patterns.
常见陷阱
外企场景- error
Failing to properly traverse all indirect invocations, potentially missing some methods.
- error
Not handling the case where no invocations exist, leading to unnecessary processing.
- error
Inadequate space management when handling large graphs with many methods and invocations.
进阶变体
外企场景- arrow_right_alt
Implementing a BFS approach instead of DFS to explore the graph.
- arrow_right_alt
Handling a dynamic set of invocations that may change over time during execution.
- arrow_right_alt
Optimizing the algorithm to minimize space complexity in large projects with many methods.