wywwzjj's Blog

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