第 230 场周赛题解

Q1 5689. 统计匹配检索规则的物品数量 (opens new window)

正常的模拟即可，对于Kotlin可以使用count函数来简化代码。

class Solution5689 {
    fun countMatches(items: List<List<String>>, ruleKey: String, ruleValue: String): Int {
        return items.count {
            when (ruleKey) {
                "type" -> it[0] == ruleValue
                "color" -> it[1] == ruleValue
                else -> it[2] == ruleValue
            }
        }
    }
}

Q2 5690. 最接近目标价格的甜点成本 (opens new window)

可以看到，基料和配料的个数$n, m$的范围是$1 <= n, m <= 10$，因此直接用强搜索即可。

搜索树每个节点有3种选择，时间复杂度为$O(n * 3^m)$。

import kotlin.math.abs

class Solution5690 {
    fun closestCost(baseCosts: IntArray, toppingCosts: IntArray, target: Int): Int {
        var ans = Int.MAX_VALUE / 2
        fun dfs(cur: Int, index: Int) {
            if (abs(cur - target) < abs(ans - target)) {
                ans = cur
            } else if (abs(cur - target) == abs(ans - target) && cur < ans) {
                ans = cur
            }
            if (index !in toppingCosts.indices) return
            dfs(cur, index + 1)
            dfs(cur + toppingCosts[index], index + 1)
            dfs(cur + toppingCosts[index] * 2, index + 1)
        }
        for (i in baseCosts) {
            dfs(i, 0)
        }
        return ans
    }
}

Q3 5691 通过最少操作次数使数组的和相等 (opens new window)

直接贪心可做。两个数组的差值为$diff$，而每个操作可以减小这个差值可以有贪心的逻辑，即对于总和小的数组，可以把当前最小的值变为$6$，对于总和大的数组可以把当前最大的值变为$1$。

1. 所有的值变为6，贡献的差值为$6 - it$
2. 所有的值变为1，贡献的差值为$it - 1$

这样我们可以把每个数字的操作后的价值进行排序，当将差值$diff$变成负数或零时，则操作完成。

class Solution5691 {
    fun minOperations(nums1: IntArray, nums2: IntArray): Int {
        val a = nums1.sum()
        val b = nums2.sum()
        if (a == b) return 0
        val arr = arrayListOf<Int>()
        if (a < b) return minOperations(nums2, nums1)
        nums1.forEach { arr.add(it - 1) }
        nums2.forEach { arr.add(6 - it) }
        arr.sortDescending()
        var cur = a - b
        var i = 0
        while (cur > 0) {
            if (i !in arr.indices) return -1
            cur -= arr[i]
            i++
        }
        return i
    }
}

Q4 5692. 车队 II (opens new window)

本题可以通过之前小乌龟题目进行理解，首先两辆车相遇时，所谓的降低速度可以完全理解为后车直接消失。

每辆车只能追击到自己右侧的车，我们可以从右到左遍历数组，每次判断是否可以与右侧的车相遇。这种暴力的方法时间复杂度为$O(n^2)$，题目中给出的数据范围会超时，需要优化。

对于$a, b, c, d$来说，共有以下几种可能：

1. $c$无法追上$d$，那么$a, b$无需判断能否追上$d$，因为追上$c$时则会消失（即判断时使用栈，从左到右来判断）
2. 若$c$能追上$d$，判断$b$追击时不能简单的直接判断速度，还需要通过之前得出的$c$追击$d$的结果时间。
   1. 若在$c$追上$d$的时间点，$b$已经追上$c$了，那么就直接使用这个结果
   2. 若此时$b$还未追上$c$，那么就不用再判断$c$，直接判断$d$即可（当做c此时已经消失）
   3. 若$b$只能追到$d$，那么当$a$判断时，也就不需要判断是否能追击到$c$了，要么$a$追上$b$自己消失，要么等$a$追上$d$。这里可以用反证，若$a$追上$c$时，$b$已经追上$d$，那么$c$也已经撞到$d$并消失了。若$a$追上$c$时，b未追到$d$，则与逻辑相悖，不可能跨过$b$先追上$c$。
3. 用栈记录当前右侧车队，被后车追上之前已经消失的车可以直接弹栈。

时间复杂度为$O(n)$，栈的最大深度为$n$，且栈中元素判断一次只能有弹栈或确定一个结果两个可能。

class Solution5692 {
    fun getCollisionTimes(cars: Array<IntArray>): DoubleArray {
        val n = cars.size
        val ans = DoubleArray(cars.size) { -1.0 }
        val st = Stack<Int>()

        fun calc(i: Int): Double {
            return (cars[st.peek()][0] - cars[i][0]).toDouble() / (cars[i][1] - cars[st.peek()][1])
        }

        for (i in n - 1 downTo 0) {
            while (st.isNotEmpty() &&
                    ans[st.peek()] > 0 &&
                    (cars[i][1] <= cars[st.peek()][1] || calc(i) > ans[st.peek()])) {
                st.pop()
            }
            if (st.isEmpty() || cars[i][1] <= cars[st.peek()][1]) {
                ans[i] = -1.0
            } else {
                ans[i] = calc(i)
            }
            st.push(i)
        }
        return ans
    }
}