第 242 场周赛题解

Q1 1869. 哪种连续子字符串更长 (opens new window)

暴力裸记录即可，需要记录当前连续的$0$和$1$的次数 及 最大长度，最后比较一次即可。

class Solution1869 {
    fun checkZeroOnes(s: String): Boolean {
        var a0 = 0
        var a1 = 0
        var b0 = 0
        var b1 = 0
        s.forEach {
            if (it == '0') {
                a0++
                a1 = 0
                b0 = maxOf(b0, a0)
            } else {
                a1++
                a0 = 0
                b1 = maxOf(b1, a1)
            }
        }
        return b1 > b0
    }
}

Q2 1870. 准时到达的列车最小时速 (opens new window)

非常标准的二分题，类似乘舟过河、运货等。

import kotlin.math.ceil

class Solution1870 {
    fun minSpeedOnTime(dist: IntArray, hour: Double): Int {
        if (hour <= dist.size - 1) return -1
        fun check(mid: Int): Boolean {
            var ans = 0.0
            dist.forEach {
                ans = ceil(ans)
                ans += it.toDouble() / mid
            }
            return ans <= hour
        }

        var left = 1
        var right = Int.MAX_VALUE / 2
        while (left + 1 < right) {
            val mid = (left + right).ushr(1)
            when {
                check(mid) -> right = mid
                else -> left = mid
            }
        }
        return if (check(left)) {
            left
        } else {
            right
        }
    }
}

Q3 1871. 跳跃游戏 VII (opens new window)

用一个队列记录当前可跳的范围列表，并遍历过程中丢弃已无效的范围组合。当前列表可跳的最右侧也无法包含当前点时，则无法继续跳下去。直至找完整个列表，整体时间复杂度为$O(n)$。

class Solution1871 {
    fun canReach(s: String, minJump: Int, maxJump: Int): Boolean {
        val l = ArrayList<Int>()
        for (i in s.indices) {
            if (s[i] == '0') l.add(i)
        }
        val list = ArrayList<Pair<Int, Int>>()
        list.add(Pair(minJump, maxJump))
        for (i in 1 until l.size) {
            if (list.isEmpty()) return false
            while (l[i] > list[0].second) {
                list.removeAt(0)
                if (list.isEmpty()) return false
            }
            if (l[i] < list[0].first) {
                continue
            } else {
                if (l[i] == s.lastIndex) {
                    return true
                }
                list.add(Pair(l[i] + minJump, l[i] + maxJump))
            }
        }
        return false
    }
}

Q4 1872. 石子游戏 VIII (opens new window)

首先分析题目，A、B拿的其实都是前缀和，且拿的$index$从$1$开始且每次都不一样。若一次拿全，则是完整和。记$f[i]$为从$i$开始拿的最优值，则拿$i$位结果$pre[i] - f[i + 1]$，不拿$i$位为$f[i + 1]$。逆序获取至$f[1]$即可。

class Solution1872 {
    fun stoneGameVIII(stones: IntArray): Int {
        val n = stones.size
        val pre = stones.preSumArray().takeLast(n).map { it.toInt() }
        val f = IntArray(n)
        f[n - 1] = pre[n - 1]
        for (i in n - 2 downTo 0) {
            f[i] = maxOf(f[i + 1], pre[i] - f[i + 1])
        }
        return f[1]
    }
}

fun IntArray.preSumArray(): LongArray {
    val preSum = LongArray(this.size + 1)
    for (i in this.indices) {
        preSum[i + 1] = preSum[i] + this[i]
    }
    return preSum
}