# # Leetcode 第288场周赛题解

## # Problem A - 按奇偶性交换后的最大数字 (opens new window)

### # 方法一：模拟

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

class Solution:
def largestInteger(self, num: int) -> int:
s = list(map(int, str(num)))
n = len(s)
for i in range(n):
for j in range(i +1, n):
if (s[i] - s[j]) % 2 == 0 and s[i] < s[j]:
s[i], s[j] = s[j], s[i]
return int(''.join(map(str, s)))

1
2
3
4
5
6
7
8
9

## # Problem B - 向表达式添加括号后的最小结果 (opens new window)

### # 方法一：模拟

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

class Solution:
def minimizeResult(self, expression: str) -> str:
l, r = expression.split('+')
best = eval(expression)
best_expr = '(' + expression + ')'

ln = len(l)
rn = len(r)

for i in range(ln):
for j in range(rn):
expr = l[:i] + '(' + l[i:] + '+' + r[:j+1] + ')' + r[j+1:]
expr1 = l[:i] + ('*' if i > 0 else '') + '(' + l[i:] + '+' + r[:j+1] + ')' + ('*' if j + 1 < rn else '') + r[j+1:]
val = eval(expr1)
if val < best:
best = val
best_expr = expr

return best_expr

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

## # Problem C - K 次增加后的最大乘积 (opens new window)

### # 方法一：贪心

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

using ll = long long;

class Solution {
public:
int maximumProduct(vector<int>& nums, int k) {
priority_queue<int, vector<int>, greater<>> pq;
for (int num : nums) pq.push(num);

while (k--) {
int u = pq.top();
pq.pop();
pq.push(u + 1);
}

ll ans = 1;
while (!pq.empty()) {
int u = pq.top();
pq.pop();
ans = ans * u % 1000000007;
}

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

## # Problem D - 花园的最大总美丽值 (opens new window)

### # 方法一：枚举填满的数目，然后最大化剩余部分的最小值

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

using ll = long long;

class Solution {
public:
long long maximumBeauty(vector<int>& flowers,
long long newFlowers,
int target,
int full,
int partial) {
int n = flowers.size();
sort(flowers.begin(), flowers.end());

if (flowers[0] >= target) return 1LL * full * n;

vector<ll> rneed(n + 1);
int rp = n - 1;
for (int i = n - 1; i >= 0; --i) {
rneed[i] = max(0, target - flowers[i]);
if (i + 1 < n) rneed[i] += rneed[i + 1];
if (rneed[i] <= newFlowers) rp = i;
}

ll best = 0;
if (rneed[0] <= newFlowers) best = 1LL * n * full;

vector<ll> pre(n + 1);
for (int i = 1; i <= n; ++i) pre[i] = pre[i - 1] + flowers[i - 1];

for (int lp = 0; lp < n; ++lp) {
if (rneed[lp + 1] > newFlowers) continue;
ll rem = newFlowers - rneed[lp + 1];

ll lo = flowers[0], hi = target - 1;
while (lo <= hi) {
ll mid = (lo + hi) >> 1;
int n = lower_bound(flowers.begin(), flowers.begin() + lp + 1,
mid) -
flowers.begin();
ll lneed = mid * n - pre[n];
if (lneed > rem)
hi = mid - 1;
else
lo = mid + 1;
}

best = max(best, hi * partial + 1LL * (n - lp - 1) * full);
}

return best;
}
};

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
43
44
45
46
47
48
49
50
51