leetcode 第 304 场算法比赛 97/7372

零、背景

这次比赛题目比较简单，拼手速的时候到了，由于就会败北。

一、使数组中所有元素都等于零

题意：给一个非负数数组，每一次操作可以选择一个不大于数组中最小值的非0正整数，所有正整数减去这个数字。
问操作多少次后，数字的所有数字全部是 0。

思路：显然，每次操作的最小数字就是最小的正整数。

这样就可以推导出答案是不同的正整数个数。

二、分组的最大数量

题意：给 n 个学生的成绩，问可以组成多少个子数组。
要求：后面子数组里总成绩和学生的个数都需要大于前面的子数组。

思路：由于学生的成绩没有顺序要求，显然可以先按成绩排序，然后再划分子数组。

题目要求不同子数组的个数是升序，成绩已经排序，总成绩也必然是升序的。

所以可以贪心，第一个子数组分一个学生，第二个子数组分二个学生，依次递推。

剩余的学生如果不满足要求，就都放在最后一个子数组即可。

复杂度：O(srqt(n))

三、找到离给定两个节点最近的节点

题目：给一个有向图，每个节点至多有一个出边。
给两个顶点，如果都可以到达某个点，这个点的得分是到两个起点中较大的那个距离。
求所有得分里的最小得分的顶点编号，如果有多个，输出编号最小的那个。

思路：最多只有一个出边意味着图至多有 n 条边。

可以分别以两个顶点为起点，遍历整个图，标记可以到达的顶点以及对应的距离。

最后遍历所有顶点，判断是否都可以到达，按规则可以了更新最新答案。

复杂度：O(n)

四、图中的最长环

题目：给一个有向图，每个节点至多有一个出边。
求图中的最长环大小。

思路：最多只有一个出边意味着图至多有 n 条边。

这意味着，一个连通图只有三种可能。
1）呈现一条链的形状，即无环。
2）呈现一个圆圈的形状，即有环，且所有点都在环上。
3）呈现一个 6 字的形状，即有环，且部分点不在环上，但是都走向环。

因此，可以通过递归编号的方式，快读判断是否有环。
如果有环，通过编号求差即可求出环的大小。

数据范围是 10^5，所以每个顶点需要做标记，之前递归遍历过了，后面就不能遍历了。

可以证明，只要得到一个连通图上的任意一点，连通图上的环必然可以遍历到。

实际编码的过程中，发现有一个问题：第一次遍历连通图时，环可以保证被遍历，但部分尾巴可能还没有遍历。
之后，再次遍历尾巴的时候，必然会与之前遍历的标记相遇。

此时，该如何识别出这个连通图的环之前已经处理了，当前遍历的是尾巴呢？

对于这个问题，我的方法是分配唯一的连续递增编号。

首先记录当前递归时的起始编号。
之后递归遇到标记时，代表下个点之前遍历过了。
遇到的标记的编号与起始编号做比较，即可判断这次相遇的标记是真实的环，还是环外的尾巴。

复杂度：O(n)

五、最后

这次比赛题目不难，环的处理我稍微犹豫了一下，排名就到 97 名了。

加油，算法人。

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号ID：tiankonguse-code