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) { 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
这大概也是能正中眉心的答案吧。