LeetCode Weekly Contest 179

wywwzjj

发布于 2023-05-09 14:39:52

1250

发布于 2023-05-09 14:39:52

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

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

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))
    	}
    }
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2020/03/08，如有侵权请联系 cloudcommunity@tencent.com 删除

int