leetcode 第179场算法比赛

零、背景

自从年前回家，到今天为止算是第一次参加比赛。
也就是有一个月没有参加比赛了，大家还好吗？

下午我也会录制视频上传到 B站，感兴趣的朋友可以去看视频（疫情期间审核速度很慢，可能要到明天才审核通过了）。

下面来看看比赛的四道题吧。

一、生成奇数字母组成的字符串

题意如标题，生成长度为 n 字符串，其中每个字母的个数都是奇数个。

签到题.

如果 n 就是奇数，那所有的字母都一样；
如果 n 是偶数，前面 n-1 的字母一样，最后一个不一样。

二、灯泡开关 III

题意：有 n 个灯泡，给一个序列来依次打开指定的灯泡。
如果当前打开了 k 个灯泡，且恰好是前 k 个灯泡打开，则可以将这 k 个灯泡变为蓝色。
问最终满足上面条件变为蓝色的次数。

分析：其实题意有点绕，我们直接改成恰好前 k 个灯泡是打开的，加一分，求最终得分数就比较好理解了。

由于要求前面的灯泡连续打开，那我们只需要统计当前已经打开的连续的最大编号是多少。

如果一次操作之后，上面的最大编号等于打开灯泡的个数，就会满足蓝灯的条件，加一分。

三、通知所有人的时间

题意：给一个公司的组织架构（有根树），每个老板只能向自己的直接下属传递信息，且不同老板花费的时间不同。
问大老板发出一个通知后，最短需要多长时间，所有员工才能全部收到这个通知。

分析：最初级的递归题。
一个老板把消息传递给直接下属后，我们先递归求出每个直接下属这个子树的最短时间，这些最短时间的最大值就是通知完所有下属的时间。
再加上老板自身的花费时间，就是当前老板需要的最短时间。

四、T 秒后青蛙的位置

题意：给一个无向树，青蛙从顶点 1 开始跳。
每次只能跳到没有跳过的相邻顶点，如果相连的顶点有多个，每个顶点的概率是一样的。
问 T 秒后，青蛙落在 target 的概率是多少。

分析：首先无向树是不是有根树题中没有介绍。
所以第一件事需要建立一个无根树。

其次，我们需要找到起点到目标的路径。
这个可以使用一个递归 dfs 做到。

PS：求路径有两种求法，一种是正向路径，一种是逆向路径，dfs 都可以做到的。

最后，我们先判断 T 秒后，青蛙能否落在 target 目标，能了再求概率，不能了，概率肯定是 0 啦。

五、最后

好了，这次的题还算比较简单，只是有两道题的题意不是很清晰，需要反复读几遍才能抓住正确的题意。

比赛试题讲解的视频已经在录制了，昨天上传的视频今天还没审核通过，那今天上传的视频估计要明天才能审核通过了。

《完》

-EOF-

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