讨论/题目交流/🏆 第 179 场力扣周赛/
🏆 第 179 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

3 分 - 生成每种字符都是奇数个的字符串
4 分 - 灯泡开关 III
5 分 - 通知所有员工所需的时间
6 分 - T 秒后青蛙的位置

展开讨论
力扣 (LeetCode)发起于 2020-03-08

各题代码和思路,python 版
https://leetcode-cn.com/contest/weekly-contest-179/

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

https://leetcode-cn.com/contest/weekly-contest-179/problems/generate-a-string-with-characters-that-have-odd-counts/

这题只用两个字母就可以,比如 '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 了好几次。踩了几个坑。

  1. 所谓无向树就是给的边的顺序不一定是父亲到儿子,也有儿子到父亲。
    这个的解决方法有两个,可以从根开始构建树,把这个顺序理顺。
    另一种就是干脆把双向的关系都保存,然后遍历树的时候记录访问过的点,防止儿子访问父亲。
    我采取第二种,写着简单,但是注意 vis 中,当前节点的儿子数不一定是当前节点的边数了。(非根节点要减一)我这里直接用暴力的方法做了。
  2. 如果当前节点有儿子,而且还有时间,那么青蛙停在该点的概率是 0。
    我因为这个 wa 了一次
    如 输入:
    8
    [[2,1],[3,2],[4,1],[5,1],[6,4],[7,1],[8,7]]
    7
    7
    
    错误输出:
    0.25000
    预期:
    0.0
            1 
       2  4   5  7  
       3  6      8
    
    因为时间有 7 秒,青蛙一定不会停在 7 上
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/

12
展开全部 25 讨论