LeetCode 第179场周赛

简单难度，速度还可以再快一点。。排名 210 / 3605

Contents

1 第一题：生成每种字符都是奇数个的字符串
2 第二题：灯泡开关 III
3 第三题：通知所有员工所需的时间
4 第四题：T 秒后青蛙的位置

第一题：生成每种字符都是奇数个的字符串

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

思路：
　　n为奇数则返回全是a的字符串，否则返回n-1个a和1个b。

代码：

class Solution:
    def generateTheString(self, n: int) -> str:
        if n == 0:
            return ''
        if n % 2 == 1:
            return 'a' * n
        else:
            return 'a' * (n-1) + 'b'

class Solution:

def generateTheString(self, n: int) -> str:

if n == 0:

return ''

if n % 2 == 1:

return 'a' * n

else:

return 'a' * (n-1) + 'b'

第二题：灯泡开关 III

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

思路：
　　将从1开始连续亮的最大灯序号记为first，维护一个集合on，记录不连续的灯。
　　如当前亮的灯为[1,2,3,5,6]，则first = 3，set={5, 6}。
　　如果当前点亮的灯序号为first + 1，并且on为空，则ans += 1。

代码：

class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        on = set()
        first = 0
        ans = 0
        n = len(light)
        for i in range(n):
            if light[i] == first + 1:
                first = light[i]

                for j in range(light[i]+1, n+1):
                    if j in on:
                        first += 1
                        on.remove(j)
                    else:
                        break
                if len(on) == 0:
                    ans += 1
            else:
                on.add(light[i])

        return ans

class Solution:

def numTimesAllBlue(self, light: List[int]) -> int:

on = set()

first = 0

ans = 0

n = len(light)

for i in range(n):

if light[i] == first + 1:

first = light[i]

for j in range(light[i]+1, n+1):

if j in on:

first += 1

on.remove(j)

else:

break

if len(on) == 0:

ans += 1

else:

on.add(light[i])

return ans

第三题：通知所有员工所需的时间

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

思路：
　　dfs。
　　用ans记录全局的时间。遍历的过程中，如果某个员工收到通知的时间 + 通知下属的时间大于ans，则更新ans。

代码：

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        if n <= 1:
            return 0
        subs = {}
        for i in range(n):  # 用数组记录每个员工的下属
            mi = manager[i]
            if mi != -1:
                if mi not in subs:
                    subs[mi] = []
                subs[mi].append(i)

        ans = 0

        # print(subs)
        def dfs(m, time):
            nonlocal ans
            if m not in subs:
                return
            for i in subs[m]:
                time_ = time + informTime[m]  # 该员工收到该通知的时间 + 通知下属的时间
                ans = max(time_, ans)  # 如果某个员工通知下属的时间大于全局的ans，则更新ans
                # print(m, time_)
                dfs(i, time_)

        dfs(headID, 0)

        return ans

class Solution:

def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:

if n <= 1:

return 0

subs = {}

for i in range(n): # 用数组记录每个员工的下属

mi = manager[i]

if mi != -1:

if mi not in subs:

subs[mi] = []

subs[mi].append(i)

ans = 0

# print(subs)

def dfs(m, time):

nonlocal ans

if m not in subs:

return

for i in subs[m]:

time_ = time + informTime[m] # 该员工收到该通知的时间 + 通知下属的时间

ans = max(time_, ans) # 如果某个员工通知下属的时间大于全局的ans，则更新ans

# print(m, time_)

dfs(i, time_)

dfs(headID, 0)

return ans

第四题：T 秒后青蛙的位置

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

思路：
　　这题一开始看给的示例以为青蛙🐸必然从根节点开始跳，后来错误❌了一次发现根结点不一定是1。。
　　依然是dfs，用集合visited记录一个位置有没有走过。遍历的过程中，有两种情况会停止搜索：1. 所有相邻的位置都已经跳过了，再继续跳只能原地跳了；2. 已经达到了步数的上限。
　　用字典probs记录每个结点的概率，在搜索的过程中不断更新probs，需要注意以下两点：1. 有多个可能的新位置时，每个新位置的概率 = 原位置的概率 × (1 / 新位置数目)；2. 跳到新位置时，要将原位置的概率置0。

代码：

class Solution:
    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
        visited = set()
        subs = {}  # 记录每个结点的相邻结点(因为一开始以为必然从根结点开始跳所以叫subs)
        probs = {1: 1.}  # 初始位置在结点1，所以1的概率为0.1。
        for edge in edges:
            from_ = edge[0]
            to = edge[1]
            if from_ not in subs:
                subs[from_] = []
            subs[from_].append(to)
            if to not in subs:
                subs[to] = []
            subs[to].append(from_)

        def dfs(m, depth):
            visited.add(m)
            if m not in subs:
                return  # 往下走不了了 原地跳
            can_go = 0
            for sub in subs[m]:
                if sub not in visited:
                    can_go += 1

            if not can_go:
                return  # 相邻的都走过了 不跳了

            if depth >= t:
                return  # 步数到了 不跳了

            for sub in subs[m]:
                if sub not in visited:
                    probs[sub] = probs[m] * 1. / can_go

            probs[m] = 0.

            for sub in subs[m]:
                if sub not in visited:
                    dfs(sub, depth+1)

        visited.add(1)
        dfs(1, 0)

        # print(subs)
        # print(probs)
        if target in probs:
            return probs[target]
        else:
            return 0.

class Solution:

def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:

visited = set()

subs = {} # 记录每个结点的相邻结点(因为一开始以为必然从根结点开始跳所以叫subs)

probs = {1: 1.} # 初始位置在结点1，所以1的概率为0.1。

for edge in edges:

from_ = edge[0]

to = edge[1]

if from_ not in subs:

subs[from_] = []

subs[from_].append(to)

if to not in subs:

subs[to] = []

subs[to].append(from_)

def dfs(m, depth):

visited.add(m)

if m not in subs:

return # 往下走不了了原地跳

can_go = 0

for sub in subs[m]:

if sub not in visited:

can_go += 1

if not can_go:

return # 相邻的都走过了不跳了

if depth >= t:

return # 步数到了不跳了

for sub in subs[m]:

if sub not in visited:

probs[sub] = probs[m] * 1. / can_go

probs[m] = 0.

for sub in subs[m]:

if sub not in visited:

dfs(sub, depth+1)

visited.add(1)

dfs(1, 0)

# print(subs)

# print(probs)

if target in probs:

return probs[target]

else:

return 0.