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演讲】好工作好公司的定义，你讨厌的不是工作，而是落后的老板
定义好工作:
- 员工被公正地对待。– 公正的薪资，福利和绩效。
- 员工有光明的发展前景。– 有职业培训和职级晋升。
- 员工心理感到安全。– 这样员工就敢于说话，敢于提意见，敢于指出老板和公司不正确的地方。
- 员工有使命感。– 员工能感觉到自己做的事情对他人，对社会有价值。
好工作比例更多的公司，会有好的发展前景，也有好的利润，因为有好的投资价值。
Tips
remote: fatal: pack exceeds maximum allowed size
Share-活着的意义思考分享
源
和同学多年多次讨论活着的意义。
从高中时期广泛向多人收集答案, 其中的答案有:
- 为了快乐
- 为了成功
- 生物 DNA 为了繁衍，强行编码人活着
前2点相对于比较主观，
第3点相对来说又太过客观。
终究没有击中内心的完全认可的靶子。
丧
多年思考后又得到了一个比较丧的答案。
活着并没有任何意义
《活着》 那本书也只读出了"活着只是为了活着"..
确实，从任何角度看，似乎有意义，但又换个角度就变得完全没有意义。
悟
正是因为活着看似无意义，才让个人的选择变得有意义。
因此每个人都有选择自己活着的意义的自由。每个人都能赋予自己的活着的意义。:D
这大概也是能正中眉心的答案吧。