2025-05-06：移除可疑的方法用go语言，你负责维护一个包含 n 个

摘要：给定 n、k 和一个调用关系数组 invocations，其中每个元素 [ai, bi] 表示方法 ai 调用了方法 bi。只有当一组待删除的方法不被其他非该组的方法调用时，才允许将这组方法全部移除。

2025-05-06：移除可疑的方法。用go语言，你负责维护一个包含 n 个方法（编号从 0 到 n - 1）的项目。

已知方法 k 存在一个已知 bug。基于此，方法 k 以及所有被它直接或间接调用的方法都被视为有问题的方法，需要从项目中删除。

给定 n、k 和一个调用关系数组 invocations，其中每个元素 [ai, bi] 表示方法 ai 调用了方法 bi。
只有当一组待删除的方法不被其他非该组的方法调用时，才允许将这组方法全部移除。

请返回删除所有可疑方法后，项目中剩余的方法列表（顺序不限）。如果无法完成全部可疑方法的删除，则不做任何删除，返回所有原有方法。

invocations[i] == [ai, bi]。

ai != bi。

invocations[i] != invocations[j]。

输入: n = 4, k = 1, invocations = [[1,2],[0,1],[3,2]]。

输出: [0,1,2,3]。

解释:

在这里插入图片描述

方法 2 和方法 1 是可疑方法，但它们分别直接被方法 3 和方法 0 调用。由于方法 3 和方法 0 不是可疑方法，我们无法移除任何方法，故返回所有方法。

题目来自leetcode3310。

1. 构建调用图：• 首先，根据给定的调用关系数组 invocations，构建一个有向图 g，其中每个节点代表一个方法，边 a -> b 表示方法 a 调用了方法 b。这里 g 是一个邻接表，g[x] 存储所有被方法 x 直接调用的方法。2. 标记可疑方法：• 从已知的 bug 方法 k 开始，进行深度优先搜索（DFS）或类似的遍历，标记所有直接或间接被 k 调用的方法为可疑方法。具体来说：• 初始化一个布尔数组 isSuspicious，长度为 n，初始值为 false。• 从 k 开始 DFS，对于当前方法 x，标记 isSuspicious[x] = true，然后递归遍历 x 调用的所有方法 y。如果 y 未被标记为可疑，则继续 DFS。3. 检查是否可以移除可疑方法：• 遍历所有调用关系 [a, b]，检查是否存在以下情况：• 调用者 a 不是可疑方法（isSuspicious[a] == false），但被调用的 b 是可疑方法（isSuspicious[b] == true）。• 如果存在这样的调用关系，说明至少有一个非可疑方法调用了可疑方法，此时无法移除任何可疑方法，直接返回所有方法 [0, 1, ..., n-1]。4. 移除可疑方法：• 如果没有发现非可疑方法调用可疑方法的情况，则可以安全移除所有可疑方法。此时，遍历 isSuspicious 数组，将所有 isSuspicious[i] == false 的方法 i 加入结果列表。5. 返回结果：• 根据上述检查的结果，返回剩余的方法列表或所有方法。

对于输入 n = 4, k = 1, invocations = [[1,2],[0,1],[3,2]]：

1. 构建调用图：• g[1] = [2]（方法 1 调用方法 2）• g[0] = [1]（方法 0 调用方法 1）• g[3] = [2]（方法 3 调用方法 2）2. 标记可疑方法：• 从 k = 1 开始 DFS：• 标记 isSuspicious[1] = true，然后遍历 g[1] = [2]。• 标记 isSuspicious[2] = true，g[2] 为空，结束。• 最终 isSuspicious = [false, true, true, false]（方法 1 和方法 2 是可疑的）。3. 检查是否可以移除：• 检查所有调用关系：• [0,1]：0 不是可疑，1 是可疑 → 无法移除。• 因此直接返回 [0, 1, 2, 3]。• 时间复杂度：• 构建调用图：遍历 invocations，时间复杂度为 O(M)，其中 M 是 invocations 的长度。• 标记可疑方法：DFS 或 BFS 遍历，每个节点和边最多访问一次，时间复杂度为 O(N + M)。• 检查是否可以移除：遍历 invocations，时间复杂度为 O(M)。• 总时间复杂度：O(N + M)。• 空间复杂度：• 调用图 g：存储所有边，空间复杂度为 O(N + M)。• isSuspicious 数组：O(N)。• DFS 的递归栈或 BFS 的队列：最坏情况下为 O(N)。• 总空间复杂度：O(N + M)。package mainimport ( "fmt")func remainingMethods(n, k int, invocations int) (ans int) { g := make(int, n) for _, e := range invocations { g[e[0]] = append(g[e[0]], e[1]) } // 标记所有可疑方法 isSuspicious := make(bool, n) var dfs func(int) dfs = func(x int) { isSuspicious[x] = true for _, y := range g[x] { if !isSuspicious[y] { // 避免无限递归 dfs(y) } } } dfs(k) // 检查是否有【非可疑方法】->【可疑方法】的边 for _, e := range invocations { if !isSuspicious[e[0]] && isSuspicious[e[1]] { // 无法移除可疑方法 for i := range n { ans = append(ans, i) } return } } // 移除所有可疑方法 for i, b := range isSuspicious { if !b { ans = append(ans, i) } } return}func main { n := 4 k := 1 invocations := int{{1, 2}, {0, 1}, {3, 2}} result := remainingMethods(n, k, invocations) fmt.Println(result)}

Python完整代码如下：

# -*-coding:utf-8-*-from typing importListdefremaining_methods(n: int, k: int, invocations: List[List[int]]) -> List[int]:# 构建邻接表，表示调用关系g = [ for _ inrange(n)]for a, b in invocations:g[a].append(b)# 标记所有可疑方法is_suspicious = [False] * ndefdfs(x: int):is_suspicious[x] = Truefor y in g[x]:ifnot is_suspicious[y]:dfs(y)dfs(k)# 检查是否有非可疑方法调用了可疑方法for a, b in invocations:ifnot is_suspicious[a] and is_suspicious[b]:# 无法移除任何可疑方法，返回所有方法returnlist(range(n))# 移除所有可疑方法，返回剩余方法列表return [i for i, suspicious inenumerate(is_suspicious) ifnot suspicious]if __name__ == "__main__":n = 4k = 1invocations = [[1, 2], [0, 1], [3, 2]]result = remaining_methods(n, k, invocations)print(result) # 输出结果