普通人进大厂的难度有多大？

将 脚本之家 设为“星标⭐”

之前我一直以为双非院校的学生进大厂要难一些，92院校的想进大厂应该会容易很多。今天在网上看了一个900多人的投票，除了52%的是观望以外，211投票最高的是11.9%，也就是20%以下的人能够进大厂，这个确实有点离谱，我觉得应该不至于这么低，可能也和专业有关。985投票最高的是7.1%，80%以上都能进大厂，不过投票第二的是6.8%，20%以下能够进大厂，这个确实有点悬殊。不过有一点可以肯定，学历越高进大厂的机率就会越大。

--------------下面是今天的算法题--------------

来看下今天的算法题，这题是LeetCode的第2368题：受限条件下可到达节点的数目。

现有一棵由 n 个节点组成的无向树，节点编号从 0 到 n - 1 ，共有 n - 1 条边。给你一个二维整数数组 edges ，长度为 n - 1 ，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条边。另给你一个整数数组 restricted 表示受限节点。

在不访问受限节点的前提下，返回你可以从节点 0 到达的最多节点数目。注意，节点 0 不会标记为受限节点。

输入：n = 7, edges = [[0,1],[1,2],[3,1],[4,0],[0,5],[5,6]], restricted = [4,5]

输出：4

解释：上图所示正是这棵树。

在不访问受限节点的前提下，只有节点 [0,1,2,3] 可以从节点 0 到达。

输入：n = 7, edges = [[0,1],[0,2],[0,5],[0,4],[3,2],[6,5]], restricted = [4,2,1]

输出：3

解释：上图所示正是这棵树。

在不访问受限节点的前提下，只有节点 [0,5,6] 可以从节点 0 到达。

public int reachableNodes(int n, int[][] edges, int[] restricted) {
    // n个集合，记录与每一个节点相连的所有节点
    List<Integer>[] lists = new List[n];
    for (int i = 0; i < n; i++)// 初始化集合
        lists[i] = new ArrayList();
    for (int[] edge : edges) {
        // 因为是无向图，所以如果a和b相连，那么b也和a相连。
        lists[edge[0]].add(edge[1]);
        lists[edge[1]].add(edge[0]);
    }
    // 记录受限的节点和已经访问过的节点
    boolean[] isRestricted = new boolean[n];
    for (int restrict : restricted)
        isRestricted[restrict] = true;

    return dfs(0, lists, isRestricted);
}

private int dfs(int start, List<Integer>[] lists, boolean[] isRestricted) {
    if (isRestricted[start])// 如果是受限的节点或者是已经访问过的节点，直接跳过
        return 0;
    isRestricted[start] = true;// 标记为已访问
    int res = 1;
    for (int num : lists[start])// 递归和当前节点相连的所有节点。
        res += dfs(num, lists, isRestricted);
    return res;
}

public:
    int reachableNodes(int n, vector<vector<int>> &edges, vector<int> &restricted) {
        vector<vector<int>> lists(n); // n个集合，记录与每一个节点相连的所有节点
        for (auto &edge: edges) {
            // 因为是无向图，所以如果a和b相连，那么b也和a相连。
            lists[edge[0]].push_back(edge[1]);
            lists[edge[1]].push_back(edge[0]);
        }
        // 记录受限的节点和已经访问过的节点
        vector<bool> isRestricted(n);
        for (int restrict: restricted)
            isRestricted[restrict] = true;
        return dfs(0, lists, isRestricted);
    }

    int dfs(int start, vector<vector<int>> &lists, vector<bool> &isRestricted) {
        if (isRestricted[start])// 如果是受限的节点或者是已经访问过的节点，直接跳过
            return 0;
        isRestricted[start] = true;// 标记为已访问
        int res = 1;
        for (int num: lists[start])// 递归和当前节点相连的所有节点。
            res += dfs(num, lists, isRestricted);
        return res;
    }

def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:
    def dfs(start: int, lists: List[List[int]], isRestricted: List[bool]):
        if isRestricted[start]:  # 如果是受限的节点或者是已经访问过的节点，直接跳过
            return 0
        isRestricted[start] = True  # 标记为已访问
        res = 1
        for num in lists[start]:  # 递归和当前节点相连的所有节点。
            res += dfs(num, lists, isRestricted)
        return res

    # n个集合，记录与每一个节点相连的所有节点
    lists = [[] for _ in range(n)]
    # 因为是无向图，所以如果a和b相连，那么b也和a相连。
    for edge in edges:
        lists[edge[0]].append(edge[1])
        lists[edge[1]].append(edge[0])
    # 记录受限的节点和已经访问过的节点
    isRestricted = [0] * n
    for restrict in restricted:
        isRestricted[restrict] = True
    return dfs(0, lists, isRestricted)