2025

admin管理员组

文章数量:1436430

2025

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

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

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

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

1 <= n <= 100000。

0 <= k <= n - 1。

0 <= invocations.length <= 2 * 100000。

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

0 <= ai, bi <= n - 1。

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

示例分析：

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

1. 1. 构建调用图：
   • • g[1] = [2]（方法 1 调用方法 2）
   • • g[0] = [1]（方法 0 调用方法 1）
   • • g[3] = [2]（方法 3 调用方法 2）
2. 2. 标记可疑方法：
   • • 从 k = 1 开始 DFS：
     • • 标记 isSuspicious[1] = true，然后遍历 g[1] = [2]。
     • • 标记 isSuspicious[2] = true，g[2] 为空，结束。
   • • 最终 isSuspicious = [false, true, true, false]（方法 1 和方法 2 是可疑的）。
3. 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)。

总结：

• • 时间复杂度：O(N + M)。
• • 空间复杂度：O(N + M)。

Go完整代码如下：

代码语言：javascript代码运行次数：0运行复制

package main

import (
    "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完整代码如下：

代码语言：javascript代码运行次数：0运行复制

# -*-coding:utf-8-*-

from typing importList

defremaining_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] * n

    defdfs(x: int):
        is_suspicious[x] = True
        for 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 = 4
    k = 1
    invocations = [[1, 2], [0, 1], [3, 2]]
    result = remaining_methods(n, k, invocations)
    print(result)  # 输出结果

.

·

·

本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。原始发表：2025-05-05，如有侵权请联系 cloudcommunity@tencent 删除存储int遍历递归数组

本文标签： 2025