第 236 场周赛题解

Q1 1822. 数组元素积的符号 (opens new window)

只用考虑符号，所以不用真计算结果，只乘$±1$即可

class Solution1822 {
    fun arraySign(nums: IntArray): Int {
        var a = 1
        nums.forEach {
            if (it < 0) a = -a
            if (it == 0) return 0
        }
        return a
    }
}

Q2 1823. 找出游戏的获胜者 (opens new window)

约瑟夫环问题，数据范围$1 <= k <= n <= 500$，可直接模拟。

class Solution1823 {
    fun findTheWinner(n: Int, k: Int): Int {
        val l = ArrayList<Int>()
        for (i in 1..n) {
            l.add(i)
        }
        var cur = 0
        while (l.size != 1) {
            cur = (cur + k - 1) % l.size
            l.removeAt(cur)
        }
        return l.first()
    }
}

使用约瑟夫环的公式，可以将时间复杂度从$O(n^2)$降低为$O(n)$

class Solution1823 {
    fun findTheWinner(n: Int, k: Int): Int {
        var p = 0
        for (i in 2..n) {
            p = (p + k) % i
        }
        return p + 1
    }
}

Q3 1824. 最少侧跳次数 (opens new window)

正常DP即可，需要注意侧跳和前进并不是同时进行的。初始化用较大的值，然后跳跃时，先将能顺序跳跃过来的赋值，再赋值可侧跳的值。这里还有个技巧，方便数据处理，使用$(j + 1)\%3$可以使代码更简洁。

class Solution1824 {
    fun minSideJumps(obstacles: IntArray): Int {
        val dp = Array<IntArray>(3) { IntArray(obstacles.size) { Int.MAX_VALUE / 2 } }
        dp[1][0] = 0
        dp[0][0] = 1
        dp[2][0] = 1
        for (i in 1 until obstacles.size) {
            for (j in 0 until 3) {
                if (obstacles[i] != j + 1) {
                    dp[j][i] = dp[j][i - 1]
                }
            }
            for (j in 0 until 3) {
                if (obstacles[i] != j + 1) {
                    dp[j][i] = minOf(dp[j][i], dp[(j + 1) % 3][i] + 1, dp[(j + 2) % 3][i] + 1)
                }
            }
        }
        return minOf(dp[0].last(), dp[1].last(), dp[2].last())
    }
}

Q4 1825. 求出 MK 平均值 (opens new window)

试了一下暴力... 结果直接过了...

class MKAverage(val m: Int, val k: Int) {

    val l = ArrayList<Int>()

    fun addElement(num: Int) {
        l.add(num)
        if (l.size > m) {
            l.removeAt(0)
        }
    }

    fun calculateMKAverage(): Int {
        if (l.size < m) return -1
        val c = l.clone() as ArrayList<Int>
        c.sort()
        return c.drop(k).dropLast(k).average().toInt()
    }
}

更好的方案是通过实现三个排序的集合，从低到高塞入数据，当删除数据时，也可以用二分方式删除所在数据。该方案可以降低删除过程的复杂度，从$O(n)$降低为$O(lgn)$。

class MKAverage(val m: Int, val k: Int) {

    val left = MultiSet<Int> { it }
    val mid = MultiSet<Int> { it }
    val right = MultiSet<Int> { it }
    val all = arrayListOf<Int>()

    fun addElement(num: Int) {
        if (all.size == m) {
            val it = all.removeAt(0)
            when {
                it <= left.max -> {
                    left.remove(it)
                }
                it <= mid.max -> {
                    mid.remove(it)
                }
                else -> {
                    right.remove(it)
                }
            }
            if (left.size < k) {
                left.add(mid.popLeft())
            }
            if (mid.size < m - 2 * k) {
                mid.add(right.popLeft())
            }
        }

        all.add(num)
        left.add(num)
        if (left.size > k) {
            mid.add(left.popRight())
        }
        if (mid.size > m - 2 * k) {
            right.add(mid.popRight())
        }
    }

    fun calculateMKAverage(): Int {
        if (all.size != m) return -1
        return (mid.sum / mid.size).toInt()
    }
}

class MultiSet<T : Comparable<T>>(private val sumBy: (T) -> Int = { 0 }) {

    private val valueList = ArrayList<T>()
    private val countMap = HashMap<T, Int>()
    var size = 0
    var sum = 0L
    val min: T
        get() = valueList.first()
    val max: T
        get() {
            return valueList.last()
        }

    fun add(value: T) {
        val index = valueList.binarySearch(value)
        if (index < 0) {
            valueList.add(-index - 1, value)
            countMap[value] = 1
        } else {
            countMap[value] = countMap[value]!! + 1
        }
        size++
        sum += sumBy(value)
    }

    fun remove(value: T): Boolean {
        if (value !in countMap.keys) return false
        val index = valueList.binarySearch(value)
        if (countMap[value] == 1) {
            countMap.remove(value)
            valueList.removeAt(index)
        } else {
            countMap[value] = countMap[value]!! - 1
        }
        size--
        sum -= sumBy(value)
        return true
    }

    fun popLeft(): T {
        return valueList.first().also {
            remove(it)
        }
    }

    fun popRight(): T {
        return valueList.last().also {
            remove(it)
        }
    }
}