第 229 场周赛题解

Q1 5685. 交替合并字符串 (opens new window)

题目直接要求从word1开始，因此不需要比较两个字符串的长度，直接取最长的即可。

class Solution5685 {
    fun mergeAlternately(word1: String, word2: String): String {
        var str = ""
        for (i in 0 until maxOf(word1.length, word2.length)) {
            if (i in word1.indices) {
                str += word1[i]
            }
            if (i in word2.indices) {
                str += word2[i]
            }
        }
        return str
    }
}

Q2 5686. 移动所有球到每个盒子所需的最小操作数 (opens new window)

先看数据范围，n最大值才2000，直接 $O(n^{2})$来计算。若数据范围更大，可以通过双指针滑动窗口来降低复杂度。

import kotlin.math.abs

class Solution5686 {
    fun minOperations(boxes: String): IntArray {
        val n = boxes.length
        val ans = IntArray(n)
        for (i in 0 until n) {
            for (j in 0 until n) {
                if (boxes[j] == '1')
                    ans[i] += abs(j - i)
            }
        }
        return ans
    }
}

Q3 5687. 执行乘法运算的最大分数 (opens new window)

记忆化搜索标准题目。这题如果用DP来做公式很绕，但是用DFS自顶向下非常好理解。由于m的最大值为$10^3$，状态总数最大为$10^6$。

设l为当前最左侧的index，r为当前最右侧的index，i为已经加完的次数（其实可以通过l和r推到出i，这里传参只是为了方便计算）。可以有

$$dfs(l, j, i) = maxOf(select(l) + dfs(l + 1, j, i + 1), select(r) + dfs(l, j + 1, i + 1))$$

需要注意记忆化使用的key的计算，最开始使用“$I$$J$”字符串拼接，可能会导致超时。

class Solution5687 {
    fun maximumScore(nums: IntArray, multipliers: IntArray): Int {
        val seen = HashMap<Int, Int>()
        fun dfs(l: Int, r: Int, i: Int): Int {
            val key = l * 1000 + r
            if (key in seen) return seen[key]!!
            if (i !in multipliers.indices) return 0
            val ans = maxOf(nums[l] * multipliers[i] + dfs(l + 1, r, i + 1),
                    nums[r] * multipliers[i] + dfs(l, r - 1, i + 1))
            return ans.also {
                seen[key] = it
            }
        }
        return dfs(0, nums.lastIndex, 0)
    }
}

Q4 5688. 由子序列构造的最长回文串的长度 (opens new window)

本题可以先看516. 最长回文子序列 (opens new window)，相比于516题，本题是新增了限制，我们把word1和word2拼接在一起，回文串的第一个字符和最后一个字符要分别属于word1和word2。之后在状态转移里判断符合规则的i、j即可，取符合条件的最大值即可。

class Solution5688 {
    fun longestPalindrome(word1: String, word2: String): Int {
        val s = "$word1$word2"
        val dp = Array(s.length) { IntArray(s.length) }
        var ans = 0
        for (i in s.lastIndex downTo 0) {
            dp[i][i] = 1
            for (j in i + 1 until s.length) {
                if (s[i] == s[j]) {
                    dp[i][j] = dp[i + 1][j - 1] + 2
                    if (i in word1.indices && j >= word1.length)
                        ans = maxOf(ans, dp[i][j])
                } else {
                    dp[i][j] = maxOf(dp[i + 1][j], dp[i][j - 1])
                }
            }
        }
        return ans
    }
}