第 227 场周赛题解

Q1 5672. 检查数组是否经排序和轮转得到 (opens new window)

用了比较trick的方法。用两个排好序的列表连接，通过字符串查找来判断是否存在。

class Solution5672 {
    fun check(nums: IntArray): Boolean {
        val cur = ArrayList(nums.sorted())
        cur.addAll(cur)
        return nums.joinToString(",") in cur.joinToString(",")
    }
}

Q2 5673. 移除石子的最大得分 (opens new window)

观察规律，三堆石子，最优解法是每次取最大的两堆。这时只会有两种结果：

1. 一堆石子非常多，其他两堆都取完了，它还有剩余。这时的结果就是其他两堆
2. 仅可能存在一个空堆，且由于使用最优策略，该空堆最多为1个。（可以直接使用总数/2来计算）

class Solution5673 {
    fun maximumScore(a: Int, b: Int, c: Int): Int {
        val (a, b, c) = intArrayOf(a, b, c).sorted()
        if (a + b <= c)
            return a + b
        return (a + b + c) / 2
    }
}

Q3 5674. 构造字典序最大的合并字符串 (opens new window)

这道题主要麻烦在考虑当字符相等的场景，需要继续向下寻找。这里直接使用语言自带的字符串比较，每次都去拿字符串值更大的Char。

class Solution5674 {
    fun largestMerge(word1: String, word2: String): String {
        var a = word1
        var b = word2
        val c = StringBuilder()
        while (a.isNotEmpty() && b.isNotEmpty()) {
            if (a > b) {
                c.append(a[0])
                a = a.substring(1)
            } else {
                c.append(b[0])
                b = b.substring(1)
            }
        }
        c.append(a)
        c.append(b)
        return c.toString()
    }
}

Q4 5675. 最接近目标值的子序列和 (opens new window)

数据范围，nums的长度为40，直接使用暴力，时间复杂度为O(2⁴⁰)，直接超时

// TLE
class Solution5675 {
    fun minAbsDifference(nums: IntArray, goal: Int): Int {
        var ans = Int.MAX_VALUE
        fun dfs(n: Int, sum: Int) {
            ans = minOf(ans, abs(sum))
            if (n !in nums.indices) return
            dfs(n - 1, sum - nums[n])
            dfs(n - 1, sum)
        }
        dfs(nums.lastIndex, goal)
        return ans
    }
}

可以通过折半法将时间复杂度降为O(2²⁰)

将数组拆分为两部分，m 与 r，这时对每部分使用上述暴力方法，计算出所有可能的结果，分别排序后再通过二分查找相近元素即可。

通过TreeSet可以快速查找出目标元素的 ceil 和 floor，省去手写二分的麻烦。

class Solution5675 {
    fun minAbsDifference(nums: IntArray, goal: Int): Int {
        val n = nums.size
        val m = nums.size / 2
        val r = n - m
        var ans = Int.MAX_VALUE
        val left = TreeSet<Int>()
        for (i in 0..(1 shl m)) {
            var tmp = 0
            for (j in 0 until m) {
                if (i and (1 shl j) != 0) tmp += nums[j]
            }
            ans = minOf(ans, abs(tmp - goal))
            left.add(tmp)
        }
        for (i in 0..(1 shl r)) {
            var tmp = 0
            for (j in 0 until r) {
                if (i and (1 shl j) != 0) tmp += nums[j + m]
            }
            ans = minOf(ans, abs(tmp - goal))
            val k = goal - tmp
            ans = minOf(ans, abs(tmp - goal + (left.ceiling(k) ?: 0)))
            ans = minOf(ans, abs(tmp - goal + (left.floor(k) ?: 0)))
        }
        return ans
    }
}