ARST打卡第254周

Linmin.Shan included in ARST

2024-03-17 1664 words 4 minutes

Contents

lc310_最小高度树【TED演讲】过度疲劳使我们失去创造力 Figma怎么导入字体爱护身体，及时就医

Algorithm

lc310_最小高度树

思路: 以前都是做的树的最长边，先dfs最远再dfs回来。

这里最小高度应该就是: (之前最长边 + 1) / 2.

反向遍历的时候还要记录路径，拿出中间一个(最长长度为奇数)或者两个节点(最长长度为偶数)。

 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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85


class Solution {
    int max_depth;
    int far_node;
    int far_node1;
    int far_node2;
    vector<int> ans_path;
public:
    // void dfs2(int node, int parent, vector<int> path, const vector<vector<int>>& nodes) {
    //     if (nodes[node].size() == 1 && node == far_node2) {
    //         path.push_back(far_node2);
    //         ans_path.assign(path.begin(), path.end());
    //         return ;
    //     }
        
    //     path.push_back(node);
    //     for (auto nxt : nodes[node]) {
    //         // 注意 parent 要使用
    //         if (nxt != parent) {
    //             dfs2(nxt, node, path, nodes);
    //         }
    //     }
    // }


    void dfs(int node, int parent, int depth, vector<int>& parent_path, 
            const vector<vector<int>>& nodes) {
        if (nodes[node].size() == 1 && depth > max_depth) {
            max_depth = depth;
            far_node = node;
            return ;
        }
        
        for (auto nxt : nodes[node]) {
            // 注意parent使用
            if (nxt != parent) {
                parent_path[nxt] = node;
                dfs(nxt, node, depth + 1, parent_path, nodes);
            }
        }
    }

    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        // 特例要考虑
        if (n == 1) {
            return {0};
        }
        // vector<vector<int>> nodes(n, vector<int>(n)); 不能一开始声明值。
        vector<vector<int>> nodes(n);
        for (auto& edge : edges) {
            nodes[edge[0]].push_back(edge[1]);
            nodes[edge[1]].push_back(edge[0]);
        }
        max_depth = 0;
        far_node = -1;
        far_node1 = -1;
        far_node2 = -1;
        vector<int> parent_path(n, -1);
        dfs(0, -1, 0, parent_path, nodes);
        far_node1 = far_node;
        max_depth = 0;
        dfs(far_node1, -1, 0, parent_path, nodes);
        far_node2 = far_node;
        
        // ans_path.clear();
        // // 超出内存限制 70 / 71 个通过的测试用例
        // vector<int> path;
        // dfs2(far_node1, -1, path, nodes);

        ans_path.clear();
        parent_path[far_node1] = -1;
        int y = far_node2;
        while (y != -1) {
            ans_path.emplace_back(y);
            y = parent_path[y];
        }

        vector<int> ans;
        int length = (max_depth + 1) / 2;
        ans.push_back(ans_path[length]);
        if (max_depth & 1) {
            ans.push_back(ans_path[length - 1]);
        }
        return ans;
    }
};

得了流感，38.9度发烧。写出来是错的（MLE），还是看看题解吧。

题解也是dfs，bfs，思路和我的一样，但是实现了一个比较精妙的parents数组，所以比较好一点。

学习其中 parents 的精髓，其实就是把dfs的起始节点当成根。

看完病，发现在公司密闭环境得了流感痛苦3天…回家吃药后就借鉴题解AC出来了..

bfs,dfs

bfs

 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


class Solution {
public:
    int findLongestNode(int u, vector<int> & parent, vector<vector<int>>& adj) {
        int n = adj.size();
        queue<int> qu;
        vector<bool> visit(n);
        qu.emplace(u);
        visit[u] = true;
        int node = -1;
  
        while (!qu.empty()) {
            int curr = qu.front();
            qu.pop();
            node = curr;
            for (auto & v : adj[curr]) {
                if (!visit[v]) {
                    visit[v] = true;
                    parent[v] = curr;
                    qu.emplace(v);
                }
            }
        }
        return node;
    }

    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        if (n == 1) {
            return {0};
        }
        vector<vector<int>> adj(n);
        for (auto & edge : edges) {
            adj[edge[0]].emplace_back(edge[1]);
            adj[edge[1]].emplace_back(edge[0]);
        }
        
        vector<int> parent(n, -1);
        /* 找到与节点 0 最远的节点 x */
        int x = findLongestNode(0, parent, adj);
        /* 找到与节点 x 最远的节点 y */
        int y = findLongestNode(x, parent, adj);
        /* 求出节点 x 到节点 y 的路径 */
        vector<int> path;
        parent[x] = -1;
        while (y != -1) {
            path.emplace_back(y);
            y = parent[y];
        }
        int m = path.size();
        if (m % 2 == 0) {
            return {path[m / 2 - 1], path[m / 2]};
        } else {
            return {path[m / 2]};
        }
    }
};

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
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


class Solution {
public:
    void dfs(int u, vector<int> & dist, vector<int> & parent, const vector<vector<int>> & adj) {
        for (auto & v : adj[u]) {
            if (dist[v] < 0) {
                dist[v] = dist[u] + 1;
                parent[v] = u;
                dfs(v, dist, parent, adj); 
            }
        }
    }

    int findLongestNode(int u, vector<int> & parent, const vector<vector<int>> & adj) {
        int n = adj.size();
        vector<int> dist(n, -1);
        dist[u] = 0;
        dfs(u, dist, parent, adj);
        int maxdist = 0;
        int node = -1;
        for (int i = 0; i < n; i++) {
            if (dist[i] > maxdist) {
                maxdist = dist[i];
                node = i;
            }
        }
        return node;
    }

    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        if (n == 1) {
            return {0};
        }
        vector<vector<int>> adj(n);
        for (auto & edge : edges) {
            adj[edge[0]].emplace_back(edge[1]);
            adj[edge[1]].emplace_back(edge[0]);
        }
        vector<int> parent(n, -1);
        /* 找到距离节点 0 最远的节点  x */
        int x = findLongestNode(0, parent, adj);
        /* 找到距离节点 x 最远的节点  y */
        int y = findLongestNode(x, parent, adj);
        /* 找到节点 x 到节点 y 的路径 */
        vector<int> path;
        parent[x] = -1;
        while (y != -1) {
            path.emplace_back(y);
            y = parent[y];
        }
        int m = path.size();
        if (m % 2 == 0) {
            return {path[m / 2 - 1], path[m / 2]};
        } else {
            return {path[m / 2]};
        }
    }
};

拓扑法

然后题解中的拓扑法不断删除度为1的节点则是惊艳

 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


class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        if (n == 1) {
            return {0};
        }
        vector<int> degree(n);
        vector<vector<int>> adj(n);
        for (auto & edge : edges){
            adj[edge[0]].emplace_back(edge[1]);
            adj[edge[1]].emplace_back(edge[0]);
            degree[edge[0]]++;
            degree[edge[1]]++;
        }
        queue<int> qu;
        vector<int> ans;
        for (int i = 0; i < n; i++) {
            if (degree[i] == 1) {
                qu.emplace(i);
            }
        }
        int remainNodes = n;
        while (remainNodes > 2) {
            int sz = qu.size();
            remainNodes -= sz;
            for (int i = 0; i < sz; i++) {
                int curr = qu.front();
                qu.pop();
                for (auto & v : adj[curr]) {
                    if (--degree[v] == 1) {
                        qu.emplace(v);
                    }
                }
            }
        }
        while (!qu.empty()) {
            ans.emplace_back(qu.front());
            qu.pop();
        }
        return ans;
    }
};

Review

【TED演讲】过度疲劳使我们失去创造力

我们不是机器，不会一直高效率，不要强求自己一直高效率，不要强求自己不会犯错。

不成功并不是因为你不努力，很可能是运气不好。

合理安排工作，及时休息，让自己变回有创造力的自己。

Tips

Figma怎么导入字体

爱护身体，及时就医

最近在密闭办公室得了流感，痛了2.5天，实在扛不住了才去了医院，结果发现一直发烧38.9度..

所以希望大家在流感季节注意防止传染病，然后身体不适及时就医。

否则会浪费好几天时间感到痛苦。并且可能会让自己的生活一团糟，搞错很多很多东西，以及投资损失等等。