ARST打卡第252周

2024-03-02 1121 words 3 minutes

Contents

lc2368_受限条件下可到达节点的数目【TED演讲】如何规划自己的未来职业独立开发者出海技术栈和工具 Supervisor管理程序后无法打印coredump和jemalloc报告排查

Algorithm

lc2368_受限条件下可到达节点的数目

思路: 建立图，然后进行bfs或者dfs遍历搜索。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


class Solution {
public:
    int reachableNodes(int n, vector<vector<int>>& edges, vector<int>& restricted) {
        vector<vector<int>> nodes(n);
        for (auto& edge : edges) {
            nodes[edge[0]].push_back(edge[1]);
            nodes[edge[1]].push_back(edge[0]);
        }
        unordered_set<int> restricted_set(restricted.begin(), restricted.end());

        queue<int> Q;
        Q.push(0);
        int ans = 0;
        vector<bool> visited(n, false);
        while(!Q.empty()) {
            int q = Q.front();
            Q.pop();
            visited[q] = true;
            ans ++;

            for (auto node : nodes[q]) {
                if (restricted_set.find(node) != restricted_set.end() || 
                    visited[node]) {
                    continue;
                }
                Q.push(node);
            }
        }
        return ans;
    }
};

题解写的dfs的方式，通过巧妙使用dfs不能访问上一个节点，而巧妙取消掉了 visited 的数组的使用。

并且使用了 restricted 数组而不是 hash_table , 减少了数据结构的复杂性。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


class Solution {
public:
    int reachableNodes(int n, vector<vector<int>>& edges, vector<int>& restricted) {
        vector<int> isrestricted(n);
        for (auto x : restricted) {
            isrestricted[x] = 1;
        }

        vector<vector<int>> g(n);
        for (auto &v : edges) {
            g[v[0]].push_back(v[1]);
            g[v[1]].push_back(v[0]);
        }
        int cnt = 0;
        function<void(int, int)> dfs = [&](int x, int f) {
            cnt++;
            for (auto &y : g[x]) {
                if (y != f && !isrestricted[y]) {
                    dfs(y, x);
                }
            }
        };
        dfs(0, -1);
        return cnt;
    }
};

题解还写了连通图法: 如果忽略受限的点，树就会变成若干个连通块，我们要计算的就是 0 号点所在连通块的大小。

因此，我们可以用并查集来不断地将点集进行合并，依次考虑每一条边，如果边上两个点都没有受限，那么合并这两个点的所在集合，否则跳过该边。最终查询 0 号点所在连通块的大小即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63


class UnionFind {
public:
    UnionFind(int n):f(n), rank(n) {
        for (int i = 0; i < n; i++) {
            f[i] = i;
        }
    }

    void merge(int x, int y) {
        int rx = find(x);
        int ry = find(y);
        if (rx != ry) {
            if (rank[rx] > rank[ry]) {
                f[ry] = rx;
            } else if (rank[rx] < rank[ry]) {
                f[rx] = ry;
            } else {
                f[ry] = rx;
                rank[rx]++;
            }
        }
    }

    int find(int x) {
        if (x != f[x]) {
            x = find(f[x]);
        }
        return f[x];
    }

    int count() {
        int cnt = 0;
        int rt = find(0);
        for (int i = 0; i < f.size(); i++) {
            // 和0同一个root根，也就是同一个连通图的。
            if (rt == find(i)) {
                cnt++;
            }
        }
        return cnt;
    }
private:
    vector<int> f;
    vector<int> rank;
};
class Solution {
public:
    int reachableNodes(int n, vector<vector<int>>& edges, vector<int>& restricted) {
        vector<int> isrestricted(n);
        for (auto &x : restricted) {
            isrestricted[x] = 1;
        }
        
        UnionFind uf = UnionFind(n);
        for (auto &v : edges) {
            if (isrestricted[v[0]] || isrestricted[v[1]]) {
                continue;
            }
            uf.merge(v[0], v[1]);
        }
        return uf.count();
    }
};

Review

【TED演讲】如何规划自己的未来职业

建立一个长期职业规划，让自己的每一份工作都去培养自己需要培养的相应技能，慢慢转化成自己dream work所需要的所有技能。

Tips

独立开发者出海技术栈和工具

Supervisor管理程序后无法打印coredump和jemalloc报告排查

这两个问题的根本原因都是相同的，就是Supervisor管理启动的时候，使用的不是二进制程序直接启动，而是用shell脚本封装了一层。

通过shell脚本封装了一层的启动脚本，因此会导致二进制程序获取到的不是系统的环境变量，而是一个新的环境变量。

解决方案:

在封装的shell脚本里面重新设置成需要的环境变量 (优选这个，因为可能还可以添加一些其他初始化操作。)
通过二进制启动程序

Contents

ARST打卡第252周

Algorithm

Review

Tips

Share