生成每种字符都是奇数个的字符串
总感觉这题应该叫我们来验证字符是否全为奇数个，结果反过来了？
代码语言：javascript复制func generateTheString(n int) string {
if n%2 == 1 {
return strings.Repeat("w", n)
} else {
return strings.Repeat("w", n-1) "y"
}
}灯泡开关 III
模拟一下
代码语言：javascript复制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。
代码语言：javascript复制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
}通知所有员工所需的时间
求树的带权深度最大值。每个人都找下老板，记录下其中的最大值即可。
代码语言：javascript复制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))
}
}
}
