第 232 场周赛题解

Q1 1790. 仅执行一次字符串交换能否使两个字符串相等 (opens new window)

硬暴力。字符串完全相等或有两个位置不相等且这两个位置交换位置是相等的。

class Solution1790 {
    fun areAlmostEqual(s1: String, s2: String): Boolean {
        if (s1 == s2) return true
        val l = arrayListOf<Int>()
        for (i in s1.indices) {
            if (s1[i] != s2[i]) {
                l.add(i)
            }
        }
        return (l.size == 2 && s1[l[0]] == s2[l[1]] && s1[l[1]] == s2[l[0]])
    }
}

Q2 1791. 找出星型图的中心节点 (opens new window)

题目保证星图有效，就不用考虑边界情况，只看前两条边即可。

class Solution1791 {
    fun findCenter(edges: Array<IntArray>): Int {
        return edges[0].toSet().intersect(edges[1].toSet()).first()
    }
}

Q3 1792. 最大平均通过率 (opens new window)

这道题开始被晃了，以为有什么数学解法... 结果发现直接优先级队列暴力即可。

class Solution1792 {
    fun maxAverageRatio(classes: Array<IntArray>, extraStudents: Int): Double {
        var ans = 0.0
        val n = classes.size
        val pq = PriorityQueue<Pair<Int, Int>>(compareByDescending {
            (it.first + 1).toDouble() / (it.second + 1).toDouble() - it.first.toDouble() / it.second.toDouble()
        })
        for (i in 0 until n) {
            val it = classes[i]
            ans += it[0].toDouble() / it[1].toDouble()
            pq.offer(Pair(it[0], it[1]))
        }
        var left = extraStudents
        while (left != 0) {
            val it = pq.poll()
            ans += (it.first + 1).toDouble() / (it.second + 1).toDouble() - it.first.toDouble() / it.second.toDouble()
            left--
            pq.offer(Pair(it.first + 1, it.second + 1))
        }
        return ans / n
    }
}

Q4 1793. 好子数组的最大分数 (opens new window)

从$k$开始向左、向右分别建立单调递减数组，记录当前经历的最小值。之后通过双指针，不断缩小范围计算结果即可。

时间复杂度：$O(n)$

class Solution1793 {
    fun maximumScore(nums: IntArray, k: Int): Int {
        val min = IntArray(nums.size)
        for (i in k downTo 0) {
            if (i == k) min[k] = nums[k]
            else min[i] = minOf(min[i + 1], nums[i])
        }
        for (i in k + 1 until nums.size) {
            min[i] = minOf(min[i - 1], nums[i])
        }
        var ans = 0
        var l = 0
        var r = nums.lastIndex
        while (k in l..r && l in min.indices && r in min.indices) {
            ans = maxOf(ans, (r - l + 1) * minOf(min[l], min[r]))
            if (min[l] < min[r]) l++
            else r--
        }
        return ans
    }
}