LeetCode Weekly Contest 179

算法

字数统计: 594阅读时长: 2 min

 2020/03/08   Share

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

总感觉这题应该叫我们来验证字符是否全为奇数个，结果反过来了？

func generateTheString(n int) string {
    if n%2 == 1 {
    	return strings.Repeat("w", n)
    } else {
    	return strings.Repeat("w", n-1) + "y"
    }
}

灯泡开关 III

模拟一下

func numTimesAllBlue(light []int) int {
    ans := 0
    ok := make([]bool, len(light)+1)     // 这个灯被点亮了
    isBlue := make([]bool, len(light)+1) // 这个灯是否为蓝色
    isBlue[0] = true

    maxLight := 0 // 所有点亮灯中最右的那个

    for i := range light {
    	now := light[i]
    	if maxLight < now {
    		maxLight = now
    	}
    	ok[now] = true
    	if isBlue[now-1] {
    		isBlue[now] = true
    		for j := now + 1; j <= len(light) && ok[j]; j++ { // 右边的已点亮，将蓝色传递下去
    			isBlue[j] = true
    		}
    	}
    	if isBlue[maxLight] { // 点亮的灯中最右的都蓝色了，说明亮的灯全蓝了
    		ans++
    	}
    }
    return ans
}

简单方法

比上面那种快了 4 ms。

func numTimesAllBlue(light []int) int {
    ans, maxLight := 0, 0
    for i := range light {
    	now := light[i]
    	if maxLight < now {
    		maxLight = now
    	}
    	if maxLight <= i + 1 {
    		ans++	
    	}
    }
    return ans
}

通知所有员工所需的时间

求树的带权深度最大值。每个人都找下老板，记录下其中的最大值即可。

func numOfMinutes(n int, headID int, manager []int, informTime []int) int {
    ans := 0
    for i := n-1; i >= 0; i-- {
    	if informTime[i] != 0 {  // 非叶节点
    		continue
    	}
    	cnt, j := 0, i
    	for manager[j] != -1 {
    		j = manager[j]
    		cnt += informTime[j]
    	}
    	if cnt > ans {
    		ans = cnt
    	}
    }
    return ans
}

T 秒后青蛙的位置

总的来说，就是把父结点处的概率往子结点传。

有概率跳到 target 的只有两种情况：

跳到 target，时间刚好用完；
跳到 target，时间没用完，但 target 是个叶节点，可以停留至时间消耗完。

var m [][]int
var ans float64

func frogPosition(n int, edges [][]int, t int, target int) float64 {
    m = make([][]int, n+1)
    ans = 0
    for i := range edges {
    	m[edges[i][0]] = append(m[edges[i][0]], edges[i][1])
    	m[edges[i][1]] = append(m[edges[i][1]], edges[i][0])
    }
    m[1] = append(m[1], 0) // 加条假边，根结点就不用另外判断了
    dfs(1, t, target, 0, 1)
    return ans
}

func dfs(n, t, target, pre int, probability float64) {
    if n == target && (t == 0 || (t > 0 && len(m[n]) == 1)) {
    	ans = probability
    	return
    }
    for i := range m[n] {
    	now := m[n][i]
    	if now != pre { // 不能往回走
    		dfs(now, t-1, target, n, probability/float64(len(m[n])-1))
    	}
    }
}

原文作者：wywwzjj

原文链接：https://wywwzjj.top/2020/03/08/LeetCode-Weekly-Contest-179/

发表日期：March 8th 2020, 12:20:39 pm

更新日期：May 15th 2021, 11:53:20 am

Next Post

LeetCode 数据库专题
Previous Post

LeetCode Weekly Contest 21（双周赛）

CATALOG

1. 生成每种字符都是奇数个的字符串
2. 灯泡开关 III
1. 2.1. 模拟一下
2. 2.2. 简单方法
3. 通知所有员工所需的时间
4. T 秒后青蛙的位置

