第 238 场周赛题解

Q1 1837. K 进制表示下的各位数字总和 (opens new window)

$Kotlin$的$toString()$方法可以直接传基，直接加和即可。

class Solution1837 {
    fun sumBase(n: Int, k: Int): Int {
        return n.toString(k).sumBy { it - '0' }
    }
}

Q2 1838. 最高频元素的频数 (opens new window)

将数组排序后，通过前缀和 $+$ 双指针，可以判断以当前位置元素作为最大元素，且增加$k$时，最多可以将前面几个元素增大到当前值。

class Solution1838 {
    fun maxFrequency(nums: IntArray, k: Int): Int {
        nums.sort()
        val preSum = IntArray(nums.size + 1)
        for (i in nums.indices) {
            preSum[i + 1] = preSum[i] + nums[i]
        }
        var ans = 0
        var i = 0
        for (j in nums.indices) {
            while (nums[j] * (j - i + 1) - (preSum[j + 1] - preSum[i]) > k) {
                i++
            }
            ans = maxOf(ans, j - i + 1)
        }
        return ans
    }
}

Q3 1839. 所有元音按顺序排布的最长子字符串 (opens new window)

由于字符串中只包含元音字母，因此只需要统计元音字母数量即可。使用一个长度为$5$的数组按顺序保存元音的出现次数，若某一位无法满足填充顺序，则将当前数组计算为$ans$并清空。取最大的$ans$即可，时间复杂度为$O(n)$。

class Solution1839 {
    fun longestBeautifulSubstring(word: String): Int {
        val c = charArrayOf('a', 'e', 'i', 'o', 'u')
        var ans = 0
        var cur = IntArray(5)
        for (i in word.indices) {
            val index = c.indexOf(word[i])
            for (j in c.lastIndex downTo 0) {
                if (index == j) {
                    cur[index]++
                    break
                } else if (cur[j] != 0) {
                    if (cur.all { it != 0 }) {
                        ans = maxOf(ans, cur.sum())
                    }
                    cur = IntArray(5)
                }
            }
        }
        if (cur.all { it != 0 }) {
            ans = maxOf(ans, cur.sum())
        }
        return ans
    }
}

Q4 1840. 最高建筑高度 (opens new window)

从左到右 和 从右到左 分别算出受限制楼的可能的最大高度。由于$n$的范围较大，不能直接遍历。因此需要利用$m$进行处理，两个限制的楼的中间可能的最大高度是$(lh + rh + dist) / 2$。偏数学的一道题，时间复杂度为$O(m\lg m)$。比赛时未能推导出公式，没想出来做法...

class Solution5741 {
    fun maxBuilding(n: Int, restrictions: Array<IntArray>): Int {
        val m = restrictions.size
        if (m == 0)
            return n - 1
        restrictions.sortBy { it[0] }
        val l = IntArray(m)
        val r = IntArray(m)
        l[0] = minOf(restrictions[0][1], restrictions[0][0] - 1)
        for (i in 1 until m) {
            val left = l[i - 1]
            val dist = restrictions[i][0] - restrictions[i - 1][0]
            l[i] = minOf(restrictions[i][1], left + dist)
        }
        r[m - 1] = restrictions[m - 1][1]
        for (i in m - 2 downTo 0) {
            val right = r[i + 1]
            val dist = restrictions[i + 1][0] - restrictions[i][0]
            r[i] = minOf(restrictions[i][1], right + dist)
        }
        var ans = 0
        for (i in 0 until m - 1) {
            val lh = minOf(l[i], r[i])
            val rh = minOf(l[i + 1], r[i + 1])
            val dist = restrictions[i + 1][0] - restrictions[i][0]
            ans = maxOf(ans, (lh + rh + dist) / 2)
        }
        ans = maxOf(ans, n - restrictions[m - 1][0] + minOf(l[m - 1], r[m - 1]))
        return ans
    }
}