LeetCode Weekly Contest 179

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

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
}

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
}

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