大厂违约金汇总一览表～
程序员老鬼约 4 分钟刚看到个贴子，说是“大厂违约金汇总一览表”，数额一个比一个吓人。怎么说呢，我觉得这事吧，本质不是钱的问题，而是成年人该不该守诺的问题。
从我的角度看，签了协议、拿了资源、享了待遇，最后又想拍拍屁股走人，不愿承担后果，这就有点像点外卖吃了半份再说不想要退款——耍赖谁都会，但不体面。
网友们的回帖我也看了，有人觉得大厂太狠，有人觉得合同本来就该遵守。我更认同后者，规则就是规则，双方都得按来。
违约金看着扎眼，是因为它把“代价”摆明了。说到底还是那句话：选择之前要想清楚，选择之后要担得起。成年人的世界，没有“我反悔了你得理解我”这种好事。
不过话说回来，公司也应该做到信息透明、流程合理，别搞阴阳合同、别藏坑。规则对等，承诺才有意义。【备注:文末可领最新资料】
面试题：课程表
“课程表”这题，大概意思就是：
有 numCourses 门课，从 0 ~ numCourses-1 编号。 有一堆先修关系，比如 [a, b] 表示：想上课 a，得先把 b 上完。
现在问你一句：这些课能不能都上完？其实潜台词就是：先修关系会不会绕来绕去形成一个“死循环”。
你脑子里可以想象成： 每门课是一点，b -> a 是一条有向边。 如果这个有向图里有环，比如 0 -> 1 -> 2 -> 0，那肯定完蛋，永远有人在等别人先上完。
所以，问题直接变成：
给你一张有向图，问图里有没有环。 没有环 ⇒ 能上完，返回 true；有环 ⇒ 上不完，返回 false。
思路一：BFS 拓扑排序（队列那一套）
这个是我平时最常写的版本，也好讲一点。
简单说就是： 看每门课“被依赖了多少次”，也就是入度 inDegree。
入度为 0 的课，说明谁都不指望它先修，它可以立刻开干，先学了不吃亏。 每学完一门课，就相当于把它这条边删掉，被它指向的那些课入度 -1。 哪门课入度变成 0 了，就也可以学了，丢进队列里。 最后数一数自己“成功学了几门”，如果数量 == 总课程数，说明没有死循环。
上代码（Java）：
publicclassSolution{
publicbooleancanFinish(int numCourses, int[][] prerequisites){
// 每门课的入度
int[] inDegree = newint[numCourses];
// 邻接表：从一门课出发，能到哪些课
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < numCourses; i++) {
graph.add(new ArrayList<>());
}
// 建图 + 统计入度
for (int[] edge : prerequisites) {
int course = edge[0];
int pre = edge[1];
graph.get(pre).add(course);
inDegree[course]++;
}
// 把所有入度为 0 的课先丢进队列
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
if (inDegree[i] == 0) {
queue.offer(i);
}
}
int learned = 0; // 学完的课数量
while (!queue.isEmpty()) {
int cur = queue.poll();
learned++;
// 学完 cur，相当于把 cur 指向的边“删掉”
for (int next : graph.get(cur)) {
inDegree[next]--;
if (inDegree[next] == 0) {
queue.offer(next);
}
}
}
return learned == numCourses;
}
}
大概的节奏就是： “谁不依赖别人，就先上谁的课，顺带清一波别人对它的依赖”。
复杂度也很稳：
每条边看一眼， O(E)每个点最多进一次队列， O(V)合在一起就是O(V + E)，空间也差不多这个级别。
思路二：DFS 深度优先搜一圈，看会不会兜回来
有时候你不想搞队列，DFS 也挺自然的： 我们给每个节点一个“状态”：
0：还没开始看这门课 1：正在这条链路上访问（递归栈里） 2：这门课已经看完，确认没问题
当你从某门课开始 DFS 的时候：
如果走着走着，又走回了一个状态是 1 的课，说明你在当前路径上绕圈了，存在环，直接 GG。 如果走到的是 2，说明它以前检查过没问题，可以放心复用结果，不用再递归一遍。
来一版 Java：
publicclassSolutionDFS{
// 0 = 未访问, 1 = 访问中, 2 = 已完成
privateint[] state;
private List<List<Integer>> graph;
privateboolean hasCycle = false;
publicbooleancanFinish(int numCourses, int[][] prerequisites){
state = newint[numCourses];
graph = new ArrayList<>();
for (int i = 0; i < numCourses; i++) {
graph.add(new ArrayList<>());
}
// pre -> course
for (int[] edge : prerequisites) {
int course = edge[0];
int pre = edge[1];
graph.get(pre).add(course);
}
// 每个点都试着当一次起点
for (int i = 0; i < numCourses; i++) {
if (state[i] == 0) {
dfs(i);
if (hasCycle) {
returnfalse;
}
}
}
returntrue;
}
privatevoiddfs(int course){
if (hasCycle) {
return; // 提前剪枝
}
state[course] = 1; // 标记为“访问中”
for (int next : graph.get(course)) {
if (state[next] == 0) {
dfs(next);
if (hasCycle) return;
} elseif (state[next] == 1) {
// 在递归栈里又遇到自己人，说明成环了
hasCycle = true;
return;
}
}
state[course] = 2; // 这个点检查完毕，没问题
}
}
这个思路更像是： “我顺着先修链一路往下走，如果哪天转了一圈又回到了正在走的那条路上，那肯定是死循环”。
时间、空间复杂度跟 BFS 版一样，也是 O(V + E) 级别。
-END-
我为大家打造了一份RPA教程，完全免费：songshuhezi.com/rpa.html