https://leetcode-cn.com/contest/weekly-contest-179/
第一题 5352. 生成每种字符都是奇数个的字符串
这题只用两个字母就可以，比如 'a', 'b'，n 是奇数，直接返回 n 个 'a'。如果 n 是偶数，返回 n-1 个 'a', 1 个 'b'。
class Solution:
def generateTheString(self, n: int) -> str:
if n % 2 == 1:
return n * 'a'
return (n-1) * 'a' + 'b'第二题 5353. 灯泡开关 III
https://leetcode-cn.com/contest/weekly-contest-179/problems/bulb-switcher-iii/
循环一次，记录一个值：当前打开的最大的灯的编号，如果当前开灯数量等于这个编号，那么当前所有灯就都是开的。
class Solution:
def numTimesAllBlue(self, light: List[int]) -> int:
cm = 1
cnt = 0
for i, l in enumerate(light):
cm = max(cm, l)
if i + 1 == cm:
cnt += 1
return cnt第三题 5354. 通知所有员工所需的时间
https://leetcode-cn.com/contest/weekly-contest-179/problems/time-needed-to-inform-all-employees/
层级关系是一棵树。解答的主体是层序遍历树，使用一个队列。
第一步要建树 sub 代表每个人有哪些下属，遍历一次 manager 就可以构建好 sub。
import queue
class Solution:
def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
if n == 1:
return 0
mt = 0
q = queue.Queue()
q.put((headID, 0))
sub = [[] for _ in range(n)]
for i, j in enumerate(manager):
if j != -1:
sub[j].append(i)
while not q.empty():
cid, ct = q.get()
mt = max(ct, mt)
for s in sub[cid]:
q.put((s, ct+informTime[cid]))
return mt第四题 5355. T 秒后青蛙的位置
https://leetcode-cn.com/contest/weekly-contest-179/problems/frog-position-after-t-seconds/
这个题我 wa 了好几次。踩了几个坑。
- 所谓无向树就是给的边的顺序不一定是父亲到儿子，也有儿子到父亲。
这个的解决方法有两个，可以从根开始构建树，把这个顺序理顺。
另一种就是干脆把双向的关系都保存，然后遍历树的时候记录访问过的点，防止儿子访问父亲。
我采取第二种，写着简单，但是注意 vis 中，当前节点的儿子数不一定是当前节点的边数了。（非根节点要减一）我这里直接用暴力的方法做了。 - 如果当前节点有儿子，而且还有时间，那么青蛙停在该点的概率是 0。
我因为这个 wa 了一次
如 输入：错误输出：8 [[2,1],[3,2],[4,1],[5,1],[6,4],[7,1],[8,7]] 7 7
0.25000
预期：
0.0因为时间有 7 秒，青蛙一定不会停在 7 上1 2 4 5 7 3 6 8
class Solution:
def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
children = [[] for _ in range(n+1)]
vif = [False] * (n+1)
p = [0] * (n+1)
for s, tt in edges:
children[s].append(tt)
children[tt].append(s)
p[1] = 1
def vis(i, st):
if st > t: return
vif[i] = True
cnt = 0
for c in children[i]:
if not vif[c]:
cnt += 1
f = False
for c in children[i]:
if not vif[c]:
p[c] = cnt * p[i]
f = True
vis(c, st+1)
if f and st <= t:
p[i] = 0
vis(1, 1)
return 1 / p[target] if p[target] > 0 else 0欢迎来我的博客： https://codeplot.top/
我的博客刷题分类：https://codeplot.top/categories/%E5%88%B7%E9%A2%98/
评论 (0)
