跳到主要内容

第 229 场周赛

Problem A - 交替合并字符串​

按要求模拟即可。

  • 时间复杂度O(∣word1∣+∣word2∣)\mathcal{O}(|word1|+|word2|)。
  • 空间复杂度O(∣word1∣+∣word2∣)\mathcal{O}(|word1|+|word2|)。
参考代码（C++）
class Solution {
public:
    string mergeAlternately(string word1, string word2) {
        int l1 = word1.size(), l2 = word2.size();
        string ans;
        int p1 = 0, p2 = 0;
        while (p1 < l1 || p2 < l2) {
            if (p1 < l1)
                ans.push_back(word1[p1++]);
            if (p2 < l2)
                ans.push_back(word2[p2++]);
        }
        return ans;
    }
};

Problem B - 移动所有球到每个盒子所需的最小操作数​

分别考虑把所有左边的球移到当前盒子的操作数，以及把所有右边的球移到当前盒子的操作数。

对于左边的情况，我们只需要维护当前一共的球数，就能够计算出再向右移动一位需要的额外花费。

右边的情况可以类似地进行处理。

  • 时间复杂度O(N)\mathcal{O}(N)。
  • 空间复杂度O(N)\mathcal{O}(N)。
参考代码（C++）
class Solution {
public:
    vector<int> minOperations(string boxes) {
        int n = boxes.size();
        vector<int> l(n), r(n);
        int ln = 0, tot = 0;
        for (int i = 0; i < n; ++i) {
            l[i] = tot;
            if (boxes[i] == '1')
                ln++;
            tot += ln;
        }
        int rn = 0;
        tot = 0;
        for (int i = n - 1; i >= 0; --i) {
            r[i] = tot;
            if (boxes[i] == '1')
                rn++;
            tot += rn;
        }
        vector<int> ans(n);
        for (int i = 0; i < n; ++i)
            ans[i] = l[i] + r[i];
        return ans;
    }
};

Problem C - 执行乘法运算的最大分数​

考虑当前已经从numsnums左边取了LL个数，从右边取了RR个数，则对于第L+R+1L+R+1个数，multipliers[L+R+1]multipliers[L+R+1]（这里下标从11开始）的取值是确定的，而在numsnums中，我们可以选择nums[L+1]nums[L+1]或nums[N−R−1]nums[N-R-1]。由于这里无论我们选择左边还是右边，都与前面的L+RL+R次选择无关，满足无后效性的要求，所以我们可以考虑进行动态规划，用dp[L][R]dp[L][R]表示左边取LL个，右边取RR个数时的最大分数。

实际上，如果已经取了KK个数，而左边取了LL个，右边自然是取了N−LN-L个，因此我们可以进一步将空间降低到一维。

  • 时间复杂度O(M2)\mathcal{O}(M^2)。
  • 空间复杂度O(M)\mathcal{O}(M)。
参考代码（C++）
#define INF 0x3f3f3f3f

class Solution {
public:
    int maximumScore(vector<int>& nums, vector<int>& multipliers) {
        int n = nums.size(), m = multipliers.size();
        vector<int> dp(m + 1, -INF);
        dp[0] = 0;
        for (int i = 0; i < m; ++i) {
            vector<int> ndp(m + 1, -INF);
            for (int j = 0; j <= i; ++j) {
                ndp[j + 1] = max(ndp[j + 1], dp[j] + nums[j] * multipliers[i]);
                ndp[j] = max(ndp[j], dp[j] + nums[n - 1 - (i - j)] * multipliers[i]);
            }
            dp = move(ndp);
        }
        return *max_element(dp.begin(), dp.end());
    }
};

Problem D - 由子序列构造的最长回文串的长度​

实际上就是一个有条件限制的最长回文子序列问题。考虑串S=word1+word2S=word1+word2，这里的限制条件就是前∣word1∣|word1|个字符中至少取一个，且后∣word2∣|word2|个字符中至少取一个。

我们首先考虑没有限制条件的最长回文子序列。这是一个经典的动态规划问题，我们有两种做法：

  1. 中心扩展，dp[L][R]dp[L][R]表示S[L…R]S[L\dots R]范围的最长回文子序列。
  2. 令T=S′T=S'（SS的倒序），然后求SS和TT的最长公共子序列。

考虑引入限制条件。我们使用三个数组，分别记录使用了word1word1的最长回文子序列，使用了word2word2的最长回文子序列和既使用了word1word1又使用了word2word2的最长回文子序列的长度。

在每一次转移时，我们根据当前字符的归属情况（属于word1word1还是word2word2）来决定是否能进行转移。

需要注意的是，这里我们应该使用上面的方法一（方法二可能也可以，但是会比较复杂），因为方法一中，我们是同时使用了两个字符，可以确保归属情况的正确处理。

  • 时间复杂度O((∣word1∣+∣word2∣)2)\mathcal{O}((|word1|+|word2|)^2)。
  • 空间复杂度O((∣word1∣+∣word2∣)2)\mathcal{O}((|word1|+|word2|)^2)。
参考代码（C++）
class Solution {
public:
    int longestPalindrome(string word1, string word2) {
        int n = word1.size(), m = word2.size();
        string s = word1 + word2;
        vector<vector<int>> lps1(n + m + 1, vector<int>(n + m + 1));
        vector<vector<int>> lps2(n + m + 1, vector<int>(n + m + 1));
        vector<vector<int>> lps12(n + m + 1, vector<int>(n + m + 1));
        for (int len = 1; len <= n + m; ++len)
            for (int l = 1; l + len - 1 <= n + m; ++l) {
                int r = l + len - 1;
                bool use1 = l <= n;
                bool use2 = r > n;
                if (len == 1) {
                    if (use1)
                        lps1[l][l] = 1;
                    if (use2)
                        lps2[l][l] = 1;
                    continue;
                }
                if (s[l - 1] == s[r - 1]) {
                    if (use1 && use2) {
                        lps12[l][r] = lps12[l + 1][r - 1] + 2;
                    }
                    if (use1) {
                        if (lps2[l + 1][r - 1] > 0)
                            lps12[l][r] = max(lps12[l][r], lps2[l + 1][r - 1] + 2);
                        lps1[l][r] = lps1[l + 1][r - 1] + 2;
                    }
                    if (use2) {
                        if (lps1[l + 1][r - 1] > 0)
                            lps12[l][r] = max(lps12[l][r], lps1[l + 1][r - 1] + 2);
                        lps2[l][r] = lps2[l + 1][r - 1] + 2;
                    }
                }
                lps12[l][r] = max(lps12[l][r], max(lps12[l + 1][r], lps12[l][r - 1]));
                lps1[l][r] = max(lps1[l][r], max(lps1[l + 1][r], lps1[l][r - 1]));
                lps2[l][r] = max(lps2[l][r], max(lps2[l + 1][r], lps2[l][r - 1]));
        }
        return lps12[1][n + m];
    }
};