Leetcode每日一题 —— 3310. 移除可疑的方法

思路

题目挺简单的，但是要 认 真 看 题！！！

今天一看题，第一想法，把调用k的方法断掉，并查集秒了。

写完之后把案例放上去一看，天塌了，题目要求

方法 k 以及它直接或间接调用的任何方法都被视为 可疑方法

我给想成

方法 k 以及直接或间接调用它的任何方法都被视为 可疑方法

之后一直在并查集上修修补补发现好像不行。

重新梳理后改用BFS。先把可疑方法染色，然后检查是否有方法调用被染色的方法，如果没有输出没被染色的方法，否则输出所有方法。

代码

class Solution {

    public List<Integer> remainingMethods(int n, int k, int[][] invocations) {

        List<Integer>[] path = new List[n];

        for (int i = 0; i < n; i++) {

            path[i] = new ArrayList<>();

        }

        for (int[] invocation : invocations) {

            path[invocation[0]].add(invocation[1]);

        }

        boolean[] visited = new boolean[n];

        Queue<Integer> queue = new ArrayDeque<>();

        queue.add(k);

        while (!queue.isEmpty()) {

            int cur = queue.poll();

            visited[cur] = true;

            for (int next : path[cur]) {

                if (!visited[next]) {

                    queue.add(next);

                }

            }

        }

        boolean canRemove = true;

        for (int[] invocation : invocations) {

            if (!visited[invocation[0]] && visited[invocation[1]]) {

                canRemove = false;

                break;

            }

        }

        List<Integer> ans = new ArrayList<>();

        if (canRemove) {

            for (int i = 0; i < n; i++) {

                if (!visited[i]) {

                    ans.add(i);

                }

            }

        } else {

            for (int i = 0; i < n; i++) {

                ans.add(i);

            }

        }

        return ans;

    }

}

算术评级 5 第 418 场周赛 Q2 难度分 1711

写了一坨效率很低的方法

class Node:

    def __init__(self, val):

        self.val=val

        self.children=[]

        self.indegrees=0

        self.outdegrees=0

    

    def add(self, next):

        self.children.append(next)



class Solution:

    def remainingMethods(self, n: int, k: int, invocations: List[List[int]]) -> List[int]:

        node_dict = defaultdict()

        for a, b in invocations:

            if a not in node_dict:

                a_node=Node(a)

                node_dict[a]=a_node

            if b not in node_dict:

                b_node=Node(b)

                node_dict[b]=b_node

            a_node=node_dict[a]

            b_node=node_dict[b]

            a_node.add(b)

            a_node.outdegrees+=1

            b_node.indegrees+=1

        visited=[False]*n

        def dfs(i):

            if visited[i]: return

            visited[i]=True

            node_i = node_dict[i]

            for j in node_i.children:

                dfs(j)

        total_indegrees=total_outdegrees=0

        if k in node_dict:

            dfs(k)

            for i in range(n):

                if visited[i]:

                    total_indegrees+=node_dict[i].indegrees

                    total_outdegrees+=node_dict[i].outdegrees

        else:

            visited[k]=True

        if total_indegrees==total_outdegrees:

            return [i for i in range(n) if not visited[i]]

        else:

            return list(range(n))

看懂题目就是bfs/dfs就好。

class Solution {

public:

    vector<int> remainingMethods(int n, int k, vector<vector<int>>& invocations) {

        vector<bool> st(n,false);

        vector<vector<int>> g(n,vector<int>());

        for(const auto& e : invocations) {

            int u = e[0], v = e[1];

            g[u].push_back(v);

        }

        queue<int> q;

        q.push(k);

        st[k] = true;

        while(q.size()) {

            auto u = q.front();

            q.pop();

            for(const auto& v : g[u]) {

                if(!st[v]) {

                    st[v] = true;

                    q.push(v);

                }

            }

        }

        bool ok = true;

        for(int i = 0; i < n && ok; i++) {

            if(!st[i]) {

                for(const auto& j : g[i]) {

                    if(st[j]) {

                        ok = false;

                        break;

                    }

                }

            }

        }

        vector<int> res;

        for(int i = 0; i < n; i++) {

            if(ok && st[i]) continue;

            res.push_back(i);

        }

        return res;

    }

};

这题目是给人类看的吗 ^-^

impl Solution {

    pub fn remaining_methods(n: i32, k: i32, invocations: Vec<Vec<i32>>) -> Vec<i32> {

        let n = n as usize;

        let k = k as usize;

        let mut edge: Vec<Vec<usize>> = vec![vec![]; n];

        let mut sus: Vec<bool> = vec![false; n];

        for invocation in invocations.iter() {

            let (a, b) = (invocation[0] as usize, invocation[1] as usize);

            edge[a].push(b);

        }

        fn f(sus: &mut Vec<bool>, edge: &Vec<Vec<usize>>, i: usize) {

            if sus[i] { return; }

            sus[i] = true;

            for &e in edge[i].iter() {

                f(sus, edge, e);

            }

        }

不知道为啥发不出去, 老是提示Awaiting Approval, 用图片似乎可以 ^-^

感觉这题主要难点是在于阅读理解。。。

class Solution:

    def remainingMethods(self, n: int, k: int, invocations: List[List[int]]) -> List[int]:

        g = [[] for _ in range(n)]

        for u, v in invocations:

            g[u].append(v)

        

        vis = [0] * n

        def dfs(u):

            vis[u] = 1

            for v in g[u]:

                if not vis[v]:

                    dfs(v)

            

        dfs(k)

        # 无法移除 所有 可疑方法，则 不 移除任何方法

        for u, v in invocations:

            if not vis[u] and vis[v]:

                return list(range(n))

        

        ans = []

        for i in range(n):

            if not vis[i]:

                ans.append(i)

        return ans