第 243 场周赛题解

Q1 1880. 检查某单词是否等于两单词之和 (opens new window)

给定的字符范围保证在$a..j$之间，因此不用考虑大于$10$的情况，直接映射到两个$Int$值即可。

class Solution1880 {
    fun isSumEqual(firstWord: String, secondWord: String, targetWord: String): Boolean {
        val a = firstWord.map { it - 'a' }.joinToString("").toInt()
        val b = secondWord.map { it - 'a' }.joinToString("").toInt()
        val c = targetWord.map { it - 'a' }.joinToString("").toInt()
        return a + b == c
    }
}

Q2 1881. 插入后的最大值 (opens new window)

贪心的做法，分两种情况讨论。

1. 第一位是'-'，整体数字是负数，将数字插入到第一个比插入字符大的数字前面
2. 整体数字是正数，将数字插入到第一个比插入字符小的数字前面
3. 若一直没有插入，则将数字插入到最后面即可。

class Solution1881 {
    fun maxValue(n: String, x: Int): String {
        val sb = StringBuilder(n)
        var isNeg = false
        for (i in sb.indices) {
            if (sb[i] == '-') {
                isNeg = true
                continue
            }
            if (isNeg) {
                if (x < sb[i] - '0') {
                    sb.insert(i, x)
                    return sb.toString()
                }
            } else {
                if (x > sb[i] - '0') {
                    sb.insert(i, x)
                    return sb.toString()
                }
            }
        }
        return sb.append(x).toString()
    }
}

Q3 1882. 使用服务器处理任务 (opens new window)

比赛时被卡常卡死了，需要增加一个时间优化让队列中的内容提前出队，否则后续的入队操作会较为耗时。

分别用两个优先级队列记录当前正在执行任务的服务器和等待执行任务的服务器。需要注意的是记录当前已到达的时间点，让队列尽量的短。

class Solution5774 {
    fun assignTasks(servers: IntArray, tasks: IntArray): IntArray {
        val ready = PriorityQueue<Triple<Int, Int, Int>>(compareBy({ it.first }, { it.second }))
        for (i in servers.indices) {
            ready.offer(Triple(servers[i], i, 0))
        }
        val doing = PriorityQueue<Triple<Int, Int, Int>>(compareBy({ it.third }, { it.first }, { it.second }))
        val ans = ArrayList<Int>()
        var ts = 0
        for (i in tasks.indices) {
            // 记录当前已到达的时间
            ts = maxOf(ts, i)
            // 能出队的尽量都出队
            while (doing.isNotEmpty() && doing.peek().third <= ts) {
                val it = doing.poll()
                ready.offer(Triple(it.first, it.second, 0))
            }
            val item = ready.poll() ?: doing.poll()
            ans.add(item.second)
            if (item.third != 0) {
                ts = item.third
            }
            doing.offer(Triple(item.first, item.second, ts + tasks[i]))
        }
        return ans.toIntArray()
    }
}

Q4 1883. 准时抵达会议现场的最小跳过休息次数 (opens new window)

二维$DP$，维度分别是$n$当前的站数，$j$当前选择跳过的次数，次数最大为$n$。其值为到达当前站点的最短时间。注意要用个$eps$来处理精度问题...

import kotlin.math.ceil

class Solution {
    fun minSkips(dist: IntArray, speed: Int, hoursBefore: Int): Int {
        val eps = 1e-9
        val n = dist.size
        val dp = Array<DoubleArray>(n + 1) { DoubleArray(n + 1) { Double.MAX_VALUE } }
        dp[0][0] = 0.0
        for (i in 1 until n + 1) {
            for (j in 0..i) {
                if (i != j) {
                    dp[i][j] = minOf(dp[i][j], ceil(dp[i - 1][j] + dist[i - 1].toDouble() / speed - eps))
                }
                if (j != 0) {
                    dp[i][j] = minOf(dp[i][j], dp[i - 1][j - 1] + dist[i - 1].toDouble() / speed)
                }
            }
        }
        for (j in 0..n) {
            if (dp[n][j] < hoursBefore + eps) {
                return j
            }
        }
        return -1
    }
}