第 256 场周赛题解

Q1 1984. 学生分数的最小差值 (opens new window)

排序后，找对应$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 大整数 (opens new window)

按长度排序，长度相同的按照字符串大小排序。

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. 完成任务的最少工作时间段 (opens new window)

这里可以看出一个贪心的逻辑，当前时间段只要能执行的任务，没有必要留到下个时间段执行。因此可以类似数组的随机顺序。对于长度只有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. 不同的好子序列数目 (opens new window)

本题的考察点主要有两个：

1. 如何求出不同的子序列
2. 如何去除其中以前导$0$开头的

首先，先来看不同的子序列。如果完全不理会重复问题，那么结果就是$2^n$个，每个字符可以选择使用和不使用两种状态。当有重复的字符出现时，之前出现该字符时所计算的所有子序列都会重复计算。

设置$dp[i]$为遍历至第$i$个字符所有的非重复序列数，若$str[i]$之前曾经出现过，则上一次命中该$char$时的序列数需要减去，防止重复计算。以$1010$为例说明（index从1开始，0表示不选取任何字符）：

1. 从0来事开始，序列为 空，总数为1
2. 遍历到1，$[null, [1]]$，总数*2
3. 遍历到0，${[null, [1], [0], [1, 0]]}$，总数为4
4. 再次遍历到1，若直接用上一个翻倍，结果为$[null, [1], [0], [1, 0], [1], [1, 1], [0, 1], [1, 0, 1]]$，可以看出其中$[1]$重复，其重复来源为上次遇到${1}$时，内部的$null$已增加了一遍，因此直接将其*2之前的值减去即可。减去上次遇到$1$之前时的dp值，得到总数为$7$。
5. 再验证遍历到$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()
    }
}