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

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