Contents

ARST打卡第227周[227/521]

Algorithm

lc207_课程表

思路: 检测路径是否无环。感觉是遍历所有依赖,然后确定遍历路径长度如果超过课程数,表示有环false. 但是感觉不太知道怎么写这种环图比较方便了,先学习一下吧,嗯嗯。

题解 发现是通过bfs/dfs处理判断拓扑排序。

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
class Solution {
private:
    vector<vector<int>> edges;
    vector<int> visited;
    bool valid = true;

public:
    void dfs(int u) {
        visited[u] = 1;
        for (int v: edges[u]) {
            if (visited[v] == 0) {
                dfs(v);
                if (!valid) {
                    return;
                }
            }
            else if (visited[v] == 1) {
                // u 课程在修的过程,v课程如果也在修,那么v依赖u的这个论证不成立
                valid = false;
                return;
            }
        }
        visited[u] = 2;
    }

    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        edges.resize(numCourses);
        visited.resize(numCourses);
        for (const auto& info: prerequisites) {
            // 把先修的课程修完,然后指向有依赖的课程
            edges[info[1]].push_back(info[0]);
        }
        for (int i = 0; i < numCourses && valid; ++i) {
            if (!visited[i]) {
                dfs(i);
            }
        }
        return valid;
    }
};

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
class Solution {
private:
    vector<vector<int>> edges;
    vector<int> indeg;

public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        edges.resize(numCourses);
        indeg.resize(numCourses);
        for (const auto& info: prerequisites) {
            edges[info[1]].push_back(info[0]);
            ++indeg[info[0]];
        }

        queue<int> q;
        for (int i = 0; i < numCourses; ++i) {
            if (indeg[i] == 0) {
                q.push(i);
            }
        }

        int visited = 0;
        while (!q.empty()) {
            ++visited;
            int u = q.front();
            q.pop();
            for (int v: edges[u]) {
                --indeg[v];
                if (indeg[v] == 0) {
                    q.push(v);
                }
            }
        }

        return visited == numCourses;
    }
};

Review

【TED演讲】好工作好公司的定义,你讨厌的不是工作,而是落后的老板

定义好工作:

  1. 员工被公正地对待。– 公正的薪资,福利和绩效。
  2. 员工有光明的发展前景。– 有职业培训和职级晋升。
  3. 员工心理感到安全。– 这样员工就敢于说话,敢于提意见,敢于指出老板和公司不正确的地方。
  4. 员工有使命感。– 员工能感觉到自己做的事情对他人,对社会有价值。

好工作比例更多的公司,会有好的发展前景,也有好的利润,因为有好的投资价值。

Tips

remote: fatal: pack exceeds maximum allowed size

Share-活着的意义思考分享

和同学多年多次讨论活着的意义。 从高中时期广泛向多人收集答案, 其中的答案有:

  • 为了快乐
  • 为了成功
  • 生物 DNA 为了繁衍,强行编码人活着

前2点相对于比较主观, 第3点相对来说又太过客观。 终究没有击中内心的完全认可的靶子。

多年思考后又得到了一个比较丧的答案。

活着并没有任何意义

《活着》 那本书也只读出了"活着只是为了活着"..

确实,从任何角度看,似乎有意义,但又换个角度就变得完全没有意义。

正是因为活着看似无意义,才让个人的选择变得有意义。

因此每个人都有选择自己活着的意义的自由。每个人都能赋予自己的活着的意义。:D

这大概也是能正中眉心的答案吧。