移除可疑的方法

3310. 移除可疑的方法

你正在维护一个项目，该项目有 n 个方法，编号从 0 到 n - 1。

给你两个整数 n 和 k，以及一个二维整数数组 invocations，其中 invocations[i] = [a_i, b_i] 表示方法 a_i 调用了方法 b_i。

已知如果方法 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 <= 10⁵
0 <= k <= n - 1
0 <= invocations.length <= 2 * 10⁵
invocations[i] == [a_i, b_i]
0 <= a_i, b_i <= n - 1
a_i != b_i
invocations[i] != invocations[j]

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: vector<int> remainingMethods(int n, int k, vector<vector<int>>& invocations) { } };

python3 解法, 执行用时: 585 ms, 内存消耗: 104.7 MB, 提交时间: 2024-10-09 22:01:05

class Solution:
    def remainingMethods(self, n: int, k: int, invocations: List[List[int]]) -> List[int]:
        g = [[] for _ in range(n)]
        for x, y in invocations:
            g[x].append(y)

        # 收集所有可疑方法
        suspicious = set()
        def dfs(x: int) -> None:
            suspicious.add(x)
            for y in g[x]:
                if y not in suspicious:  # 避免无限递归
                    dfs(y)
        dfs(k)

        # 检查是否有【非可疑方法】->【可疑方法】的边
        for x, y in invocations:
            if x not in suspicious and y in suspicious:
                # 无法移除可疑方法
                return list(range(n))

        # 移除所有可疑方法
        return list(set(range(n)) - suspicious)

    # 数组
    def remainingMethods2(self, n: int, k: int, invocations: List[List[int]]) -> List[int]:
        g = [[] for _ in range(n)]
        for x, y in invocations:
            g[x].append(y)

        # 标记所有可疑方法
        is_suspicious = [False] * n
        def dfs(x: int) -> None:
            is_suspicious[x] = True
            for y in g[x]:
                if not is_suspicious[y]:  # 避免无限递归
                    dfs(y)
        dfs(k)

        # 检查是否有【非可疑方法】->【可疑方法】的边
        for x, y in invocations:
            if not is_suspicious[x] and is_suspicious[y]:
                # 无法移除可疑方法
                return list(range(n))

        # 移除所有可疑方法
        return [i for i, b in enumerate(is_suspicious) if not b]

golang 解法, 执行用时: 479 ms, 内存消耗: 33.9 MB, 提交时间: 2024-10-09 22:00:22

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
}

java 解法, 执行用时: 65 ms, 内存消耗: 136.6 MB, 提交时间: 2024-10-09 22:00:05

class Solution {
    public List<Integer> remainingMethods(int n, int k, int[][] invocations) {
        List<Integer>[] g = new ArrayList[n];
        Arrays.setAll(g, i -> new ArrayList<>());
        for (int[] e : invocations) {
            g[e[0]].add(e[1]);
        }

        // 标记所有可疑方法
        boolean[] isSuspicious = new boolean[n];
        dfs(k, g, isSuspicious);

        // 检查是否有【非可疑方法】->【可疑方法】的边
        for (int[] e : invocations) {
            if (!isSuspicious[e[0]] && isSuspicious[e[1]]) {
                // 无法移除可疑方法
                List<Integer> ans = new ArrayList<>(n);
                for (int i = 0; i < n; i++) {
                    ans.add(i);
                }
                return ans;
            }
        }

        // 移除所有可疑方法
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (!isSuspicious[i]) {
                ans.add(i);
            }
        }
        return ans;
    }

    private void dfs(int x, List<Integer>[] g, boolean[] isSuspicious) {
        isSuspicious[x] = true;
        for (int y : g[x]) {
            if (!isSuspicious[y]) { // 避免无限递归
                dfs(y, g, isSuspicious);
            }
        }
    }
}

cpp 解法, 执行用时: 935 ms, 内存消耗: 298.3 MB, 提交时间: 2024-10-09 21:59:48

class Solution {
public:
    vector<int> remainingMethods(int n, int k, vector<vector<int>>& invocations) {
        vector<vector<int>> g(n);
        for (auto& e : invocations) {
            g[e[0]].push_back(e[1]);
        }

        // 标记所有可疑方法
        vector<int> is_suspicious(n);
        auto dfs = [&](auto&& dfs, int x) -> void {
            is_suspicious[x] = true;
            for (int y : g[x]) {
                if (!is_suspicious[y]) { // 避免无限递归
                    dfs(dfs, y);
                }
            }
        };
        dfs(dfs, k);

        // 检查是否有【非可疑方法】->【可疑方法】的边
        for (auto& e : invocations) {
            if (!is_suspicious[e[0]] && is_suspicious[e[1]]) {
                // 无法移除可疑方法
                vector<int> ans(n);
                iota(ans.begin(), ans.end(), 0);
                return ans;
            }
        }

        // 移除所有可疑方法
        vector<int> ans;
        for (int i = 0; i < n; i++) {
            if (!is_suspicious[i]) {
                ans.push_back(i);
            }
        }
        return ans;
    }
};

上一题

下一题

详情