阅读 511

前端工程师的 LeetCode 之旅 -- 179周赛




01
生成每种字符都是奇数的字符串



题目描述【Easy】


给你一个整数 n,请你返回一个含 n 个字符的字符串,其中每种字符在该字符串中都恰好出现 奇数次 。
返回的字符串必须只含小写英文字母。如果存在多个满足题目要求的字符串,则返回其中任意一个即可。
示例:
输入:n = 4
输出:'pppz'
解释:'pppz' 是一个满足题目要求的字符串,因为 'p' 出现 3 次,且 'z' 出现 1 次。当然,还有很多其他字符串也满足题目要求,比如:'ohhh' 和 'love'。



理解题意之后,本质上就是考察:判断一个整数的奇偶型。




02
灯泡开关III



题目描述【Medium】


房间中有 n 枚灯泡,编号从 1 到 n,自左向右排成一排。最初,所有的灯都是关着的。
在 k 时刻( k 的取值范围是 0 到 n - 1),我们打开 light[k] 这个灯。
灯的颜色要想 变成蓝色 就必须同时满足下面两个条件:
灯处于打开状态。
排在它之前(左侧)的所有灯也都处于打开状态。
请返回能够让 所有开着的 灯都 变成蓝色 的时刻 数目 。
示例:
输入:light = [2, 1, 3, 5, 4]
输出:3
解释:所有开着的灯都变蓝的时刻分别是 1,2 和 4。



首先要理解灯泡变蓝的条件:

  • 灯处于打开状态

  • 排在它前面的所有灯都处于打开状态

如果要求某个时刻打开的灯都变蓝,那么此时开着的灯应该是一个 1 到 n 的排列。

第一种解法:如果此刻所有开着的灯是一个 1 到 n 的排列,那么此刻开着灯的最大下标应该和数量一致。

第二种解法:如果此刻所有开着的灯是一个 1 到 n 的排列,那么所有开着的灯的下标和满足前 n 项等差数列求和。




03
通知所有员工所需的时间



题目描述【Medium】


公司里有 n 名员工,每个员工的 ID 都是独一无二的,编号从 0 到 n - 1。公司的总负责人通过 headID 进行标识。
在 manager 数组中,每个员工都有一个直属负责人,其中 manager[i] 是第 i 名员工的直属负责人。对于总负责人,manager[headID] = -1。题目保证从属关系可以用树结构显示。
公司总负责人想要向公司所有员工通告一条紧急消息。他将会首先通知他的直属下属们,然后由这些下属通知他们的下属,直到所有的员工都得知这条紧急消息。
第 i 名员工需要 informTime[i] 分钟来通知它的所有直属下属(也就是说在 informTime[i] 分钟后,他的所有直属下属都可以开始传播这一消息)。
返回通知所有员工这一紧急消息所需要的 分钟数 。
示例:
输入:n = 6, headID = 2, manager = [2,2,-1,2,2,2], informTime = [0,0,1,0,0,0]
输出:1
解释:id = 2 的员工是公司的总负责人,也是其他所有员工的直属负责人,他需要 1 分钟来通知所有员工。
下图显示了公司员工的树结构。



本题主要考察搜索算法。

第一步:利用 JavaScript 中的 Map 数据结构来存储节点的树型关系。

第二步:由于每一个领导的通知时间强依赖直属下属的通知时间,所以在DFS (深度优先搜索算法)的过程中,需要向上传递当前节点所花费的通知时间。




04
T秒后青蛙的位置



题目描述【Hard】


给你一棵由 n 个顶点组成的无向树,顶点编号从 1 到 n。青蛙从 顶点 1 开始起跳。规则如下:
在一秒内,青蛙从它所在的当前顶点跳到另一个 未访问 过的顶点(如果它们直接相连)。
青蛙无法跳回已经访问过的顶点。
如果青蛙可以跳到多个不同顶点,那么它跳到其中任意一个顶点上的机率都相同。
如果青蛙不能跳到任何未访问过的顶点上,那么它每次跳跃都会停留在原地。
无向树的边用数组 edges 描述,其中 edges[i] = [fromi, toi] 意味着存在一条直接连通 fromi 和 toi 两个顶点的边。
返回青蛙在 t 秒后位于目标顶点 target 上的概率。
示例:
输入:n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 2, target = 4
输出:0.16666666666666666
解释:上图显示了青蛙的跳跃路径。青蛙从顶点 1 起跳,第 1 秒 有 1/3 的概率跳到顶点 2 ,然后第 2 秒 有 1/2 的概率跳到顶点 4,因此青蛙在 2 秒后位于顶点 4 的概率是 1/3 * 1/2 = 1/6 = 0.16666666666666666 。



本道题与上一题的解题思路有点类似。

注意本题是一棵无向树,那么在利用 Map 记录 edges 数组中的边时,需要处理双向关系,由于这是一个树型关系,可以通过判断父子节点的大小,避免后续搜索过程中判断当前节点的访问状态。

接下来,就是利用 DFS 模拟青蛙跳动的轨迹,在 DFS 过程中,需要做如下处理:

  • 向下传递选中当前节点的概率

  • 判断当前节点是否为目标节点,返回最终概率

当前节点为目标节点的场景有如下两种:

  • 正好搜索到目标节点,且时间耗尽

  • 搜索到目标节点,虽然时间未耗尽,但是无路可走




05
往期精彩回顾









关注下面的标签,发现更多相似文章
评论