# # Leetcode 第229场周赛题解

## # Problem A - 交替合并字符串 (opens new window)

• 时间复杂度$\mathcal{O}(|word1|+|word2|)$
• 空间复杂度$\mathcal{O}(|word1|+|word2|)$

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;
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

## # Problem B - 移动所有球到每个盒子所需的最小操作数 (opens new window)

• 时间复杂度$\mathcal{O}(N)$
• 空间复杂度$\mathcal{O}(N)$

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;
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

## # Problem C - 执行乘法运算的最大分数 (opens new window)

• 时间复杂度$\mathcal{O}(M^2)$
• 空间复杂度$\mathcal{O}(M)$

#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());
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

## # Problem D - 由子序列构造的最长回文串的长度 (opens new window)

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

• 时间复杂度$\mathcal{O}((|word1|+|word2|)^2)$
• 空间复杂度$\mathcal{O}((|word1|+|word2|)^2)$

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];
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42