第 256 场周赛题解
2025/8/31大约 4 分钟
第 256 场周赛题解
Q1 1984. 学生分数的最小差值
排序后,找对应$k$个人的最左最右做差。
class Solution5854 {
fun minimumDifference(nums: IntArray, k: Int): Int {
nums.sort()
var ans = Int.MAX_VALUE
for (i in k - 1 until nums.size) {
ans = minOf(ans, nums[i] - nums[i - k + 1])
}
return ans
}
}
Q2 1985. 找出数组中的第 K 大整数
按长度排序,长度相同的按照字符串大小排序。
class Solution5855 {
fun kthLargestNumber(nums: Array<String>, k: Int): String {
val sorted = nums.sortedWith(compareBy({ it.length }, { it }))
return sorted[nums.size - k]
}
}
Q3 1986. 完成任务的最少工作时间段
这里可以看出一个贪心的逻辑,当前时间段只要能执行的任务,没有必要留到下个时间段执行。因此可以类似数组的随机顺序。对于长度只有14的数组来说,可以玄学退火~
普通直接$mask$处理状态压缩即可。
class Solution5856 {
fun minSessions(tasks: IntArray, sessionTime: Int): Int {
val n = tasks.size
// 与计算出所有合法组合状态
val valid = BooleanArray(1 shl n)
for (mask in 1 until valid.size) {
var needTime = 0
// 该状态下需要的总sessionTime
for (i in 0 until n) {
if (mask and (1 shl i) != 0) {
needTime += tasks[i]
}
}
if (needTime <= sessionTime) {
valid[mask] = true
}
}
val dp = IntArray(1 shl n) { Int.MAX_VALUE / 2 }
dp[0] = 0
for (mask in 1 until dp.size) {
// 所有1的组合
var subSet = mask
while (subSet != 0) {
if (valid[subSet]) {
// subSet作为单独一次处理,获取其余部分的最小值
dp[mask] = minOf(dp[mask], dp[mask xor subSet] + 1)
}
subSet = (subSet - 1) and mask
}
}
return dp.last()
}
}
Q4 1987. 不同的好子序列数目
本题的考察点主要有两个:
- 如何求出不同的子序列
- 如何去除其中以前导$0$开头的
首先,先来看不同的子序列。如果完全不理会重复问题,那么结果就是$2^n$个,每个字符可以选择使用和不使用两种状态。当有重复的字符出现时,之前出现该字符时所计算的所有子序列都会重复计算。
设置$dp[i]$为遍历至第$i$个字符所有的非重复序列数,若$str[i]$之前曾经出现过,则上一次命中该$char$时的序列数需要减去,防止重复计算。以$1010$为例说明(index从1开始,0表示不选取任何字符):
- 从0来事开始,序列为 空,总数为1
- 遍历到1,$[null, [1]]$,总数*2
- 遍历到0,${[null, [1], [0], [1, 0]]}$,总数为4
- 再次遍历到1,若直接用上一个翻倍,结果为$[null, [1], [0], [1, 0], [1], [1, 1], [0, 1], [1, 0, 1]]$,可以看出其中$[1]$重复,其重复来源为上次遇到${1}$时,内部的$null$已增加了一遍,因此直接将其*2之前的值减去即可。减去上次遇到$1$之前时的dp值,得到总数为$7$。
- 再验证遍历到$0$,当前序列为$[null, [1], [0], [1, 0], [1, 1], [0, 1], [1, 0, 1]]$,分别再次追加$0$后得到$[null, [1], [0], [1, 0], [1, 1], [0, 1], [1, 0, 1], [0], [1, 0], [0, 0], [1, 0, 0], [1, 1, 0], [0, 1, 0], [1, 0, 1, 0]]$,其中重复内容是上次遍历到$0$时$[null, [1]]$所生成的,减去$2$即可,总数记为$12$。
同时,可以看出$dp[last[0]]$即以0为结尾产生的序列数,而题意需要我们去除以$0$为开头的,则直接将字符串逆序求即可。
注:题意中保留单个的$0$而不计算空序列,刚好抵消,不用在额外计算加减$1$。全$0$和全$1$在最开始额外讨论,规避边界条件。
class Solution5857 {
// 去除重复序列
fun numberOfUniqueGoodSubsequences(binary: String): Int {
if (binary.all { it == '0' }) return 1
if (binary.all { it == '1' }) return binary.length
val mod = 1000000007L
// Returns count of distinct subsequences of str.
fun countSub(str: String): Pair<Long, Long> {
// 长度为 序列包含的字符数,存储上一次包含的index
val last = IntArray(2) { -1 }
val n = str.length
// 共有不同的序列数
val dp = LongArray(n + 1)
// 0为空,不选取任何字符
dp[0] = 1L
for (i in 1..n) {
// 不考虑去重情况,可选子序列应该翻倍
dp[i] = 2 * dp[i - 1]
// 该字符之前出现过,那么需要去掉重复序列
// 即上一次的序列完全删除
if (last[str[i - 1] - '0'] != -1)
dp[i] = (dp[i] - dp[last[str[i - 1] - '0']] + mod) % mod
// 将当前字符的index存入历史数组中
last[str[i - 1] - '0'] = i - 1
dp[i] %= mod
}
return Pair(dp[n], dp[last[0]])
}
// 全部的子序列 减去 以0开头的子序列
val ans = countSub(binary.reversed()).let { it.first - it.second }
return ((ans + mod) % mod).toInt()
}
}