1. 将数字变成 0 的操作次数

这道题其实是道送分题，我一开始以为有什么坑，就先跳过了，最后才回来做，然后就按照题目的题意写就可以了：

[[email protected]]#  cat Q1.go
func numberOfSteps(num int) (rst int) {
    for num != 0 {
        if num&1 == 0 {
            num >>= 1
        } else {
            num -= 1
        }
        rst++
    }
    return rst
}

2. 大小为 K 且平均值大于等于阈值的子数组数目

这道题我想应该是考察的滑动窗口的思想，也就是保持 K 个元素的窗口，然后不断得往后移动，对于每个新的窗口，只需要做： sum = sum - old + new 即可，所以整个下来也没有啥问题，需要注意的就是题目是 ≥ threshold，我这里载了一次：

[[email protected]]# cat Q2.go
func numOfSubarrays(arr []int, k int, threshold int) int {
    var (
        i, sum, count int
        length        = len(arr)
    )

    for i = 0; i < k; i++ {
        sum += arr[i]
    }

    for {
        if threshold*k <= sum {
            count++
        }
        if i >= length {
            break
        }
        sum = sum - arr[i-k] + arr[i]
        i++
    }
    return count
}

3. 时钟指针的夹角

这道题目看上去是个数学题，但其实我觉得倒有点像是考验细心的题目，一个难点就在于定位时针的位置，因为时针的位置还和分针有关，所以这里我的解决方式就是分别求出时针和分针相对于 12:00 的角度，然后再一减就是他们之间的夹角了。其中

所以最终的结果就是：时针的角度 - 分针的角度，再换算成 180 以内即可：

[[email protected]]# cat Q3.go
func angleClock(hour int, minutes int) float64 {
    var (
        locaH, locaM, diff float64
    )

    locaM = float64(6 * minutes)
    locaH = float64(30*hour%360) + float64(minutes)*30.0/60.0

    diff = max(locaH, locaM) - min(locaH, locaM)
    if diff > 180.0 {
        diff = 360 - diff
    }
    return diff
}

4. 跳跃游戏 IV

这道题我一看以为是 DP，但是推不出来表达式，然后一想应该是个 BFS，然后写了一版正向 BFS（从 0 开始，找 N-1），OOM 了，看了一下数据，全是同一个数字，一共有 50002 个 7，好奇怪。于是就换种思路，写了一版反向 BFS（从 N-1 开始，找 0），然后就过了，没看出来复杂度有多大区别。

这里有个优化的点就是，对相同值的索引要做个反向索引，这样可以保证 BFS 不会 Timeout：

[[email protected]]# cat Q4.go
import "container/list"

func minJumps(arr []int) int {
    var (
        length = len(arr)
        // steps[i]: 从 i 到 end 的最小步数
        steps = make([]int, length)
        // 反向索引
        valIdx = map[int][]int{}
        i      int
        // 剪枝
        visitedMap = map[int]bool{}
    )

    if length == 0 || length == 1 {
        return 0
    }

    visitedMap[0] = true
    visitedMap[-1] = true
    visitedMap[length] = true
    valIdx[arr[0]] = append(valIdx[arr[0]], i)
    for i = 0; i < length; i++ {
        steps[i] = -1
        valIdx[arr[i]] = append(valIdx[arr[i]], i)
    }

    var q = list.New()
    steps[length-1] = 0
    q.PushBack(length - 1)
    for q.Len() > 0 {
        i = q.Remove(q.Front()).(int)
        if i-1 >= 0 && steps[i-1] == -1 {
            if i-1 == 0 {
                return steps[i] + 1
            }
            q.PushBack(i - 1)
            steps[i-1] = steps[i] + 1
        }
        if i+1 < length && steps[i+1] == -1 {
            q.PushBack(i + 1)
            steps[i+1] = steps[i] + 1
        }
        for _, idx := range valIdx[arr[i]] {
            if idx == 0 {
                return steps[i] + 1
            }
            if steps[idx] == -1 {
                q.PushBack(idx)
                steps[idx] = steps[i] + 1
            }
        }
    }
    return steps[0]
}

5. 小结

感觉双周赛的题目比较简单，玩家也稍微快一些，1小时加 5 分钟刷完的情况下，也只能到 100 多名。