# # Leetcode 第58场双周赛题解

## # Problem A - 删除字符使字符串变好 (opens new window)

### # 方法一：模拟

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

class Solution {
public:
string makeFancyString(string s) {
string ans;
char last = '\$';
int cnt = 0;
for (char c : s) {
if (c == last) {
if (++cnt <= 2)
ans.push_back(c);
} else {
ans.push_back(c);
last = c;
cnt = 1;
}
}
return ans;
}
};

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

## # Problem B - 检查操作是否合法 (opens new window)

### # 方法一：模拟

• 中间有至少一个颜色相异的格子
• 结尾处有一个颜色相同的格子

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

const int d[8][2] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
const int n = 8;

class Solution {
public:
bool checkMove(vector<vector<char>>& board, int r, int c, char color) {
int bw = 'B' + 'W';
auto valid = [&](int i, int j) {
return i >= 0 && i < n && j >= 0 && j < n;
};

for (int k = 0; k < 8; ++k) {
int nr = r + d[k][0], nc = c + d[k][1];
int len = 0;
while (valid(nr, nc) && board[nr][nc] + color == bw) {
len++, nr += d[k][0], nc += d[k][1];
}
if (valid(nr, nc) && board[nr][nc] == color && len > 0)
return true;
}
return false;
}
};

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

## # Problem C - K 次调整数组大小浪费的最小总空间 (opens new window)

### # 方法一：动态规划

$dp[i][j]$表示到第$i$个位置为止，共调整了$j$次大小时的最小浪费值。我们从$dp[i][j]$出发，枚举下一个区间的结束位置$nxt$，就可以更新$dp[nxt][j + 1]$

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

const int INF = 0x3f3f3f3f;

class Solution {
public:
int minSpaceWastedKResizing(vector<int>& nums, int k) {
int n = nums.size();
vector<vector<int>> dp(n + 1, vector<int>(k + 1, INF));
dp[0][0] = 0;
int hi = 0, sum = 0;
for (int i = 0; i < n; ++i) {
hi = max(hi, nums[i]);
sum += nums[i];
dp[i + 1][0] = hi * (i + 1) - sum;
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < k; ++j) {
int hi = 0, sum = 0;
for (int nxt = i + 1; nxt <= n; ++nxt) {
hi = max(hi, nums[nxt - 1]);
sum += nums[nxt - 1];
dp[nxt][j + 1] = min(dp[nxt][j + 1], dp[i][j] + hi * (nxt - i) - sum);
}
}
}
return dp[n][k];
}
};

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

## # Problem D - 两个回文子字符串长度的最大乘积 (opens new window)

### # 方法一：Manacher算法

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

vector<int> manacher_pre(const string &s) {
int n = s.size();
vector<int> a(n), hi(n, 1);
for (int i = 0, l = 0, r = -1; i < n; ++i) {
int j = (i > r) ? 1 : min(a[l + r - i], r - i + 1);
while (i >= j && i + j < n && s[i - j] == s[i + j])
j++;
a[i] = j--;
if (i + j > r) {
l = i - j;
r = i + j;
}
} // Manacher算法，因为只考虑奇数长度的回文串，不需要对原串进行插入特殊字符的操作
int chi = 0; // 单指针，指向当前第一个没有被覆盖的回文串的中心位置
for (int i = 0; i < n; ++i) {
if (i >= 1)
hi[i] = hi[i - 1];
while (chi + a[chi] - 1 < i) // 被覆盖，右移指针寻找下一个没有被覆盖的中心位置
chi++;
hi[i] = max(hi[i], i - chi + 1);
}
return hi;
}

class Solution {
public:
long long maxProduct(string s) {
int n = s.size();
string rs(s.rbegin(), s.rend());
auto lhi = manacher_pre(s), rhi = manacher_pre(rs); // lhi为前缀包含的最大回文串长度（单侧），rhi为后缀包含的最大回文串长度（单侧）
long long ans = 1;
for (int i = 0; i < n - 1; ++i) // 枚举前缀
ans = max(ans, 1LL * (2 * lhi[i] - 1) * (2 * rhi[n - 2 - i] - 1));
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
27
28
29
30
31
32
33
34
35
36