# # Leetcode 第214场周赛题解

## # Problem A - 获取生成数组中的最大值 (opens new window)

• 时间复杂度$O(N)$
• 空间复杂度$O(N)$

@functools.lru_cache(None)
def f(n):
return n if n <= 1 else f(n // 2) if n % 2 == 0 else f(n // 2) + f(n // 2 + 1)

class Solution:
def getMaximumGenerated(self, n: int) -> int:
a = [f(i) for i in range(n + 1)]
return max(a)

1
2
3
4
5
6
7
8

## # Problem B - 字符频次唯一的最小删除次数 (opens new window)

• 时间复杂度$O(N+K\log K)$$K$为不同字符的个数。
• 空间复杂度$O(K)$

class Solution:
def minDeletions(self, s: str) -> int:
cnt = collections.Counter(s)
freq = sorted([cnt[key] for key in cnt])
upper = [i for i in range(len(freq) + 1)]
upper[-1] = int(1e9)
ans = 0
for i in range(len(freq) - 1, -1, -1):
upper[i] = min(freq[i], max(0, upper[i + 1] - 1))
ans += freq[i] - upper[i]
return ans % int(1e9 + 7)

1
2
3
4
5
6
7
8
9
10
11

## # Problem C - 销售价值减少的颜色球 (opens new window)

• 时间复杂度$O(N\log N)$
• 空间复杂度$O(N)$

typedef long long ll;

class Solution {
public:
int maxProfit(vector<int>& inventory, int orders) {
sort(inventory.begin(), inventory.end());
vector<pair<int, int>> v = {{0, 0}};
for (int i : inventory)
v.emplace_back(i, 1);
ll ans = 0;
while (orders) {
int m = v.size();
if (v[m - 1].first == v[m - 2].first) {
v[m - 2].second += v[m - 1].second;
v.pop_back();
} else {
int l = v[m - 2].first + 1, r = v[m - 1].first;
ll delta = r - l + 1;
ll sell = min(delta * v[m - 1].second, (ll)orders);
ll full = sell / v[m - 1].second;
ans += ((ll)r + r - full + 1) * full * v[m - 1].second / 2 + ((ll)r - full) * (sell - full * v[m - 1].second);
orders -= sell;
if (orders) {
v[m - 2].second += v[m - 1].second;
v.pop_back();
}
}
}
return ans % int(1e9 + 7);
}
};

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

## # Problem D - 通过指令创建有序数组 (opens new window)

• 时间复杂度$O(N\log K)$$K$为不同数字的个数。
• 空间复杂度$O(K)$

typedef long long ll;

template <class T> class FenwickTree {
int limit;
vector<T> arr;

T lowbit(T x) { return x & (-x); }

public:
FenwickTree(int limit) {
this->limit = limit;
arr = vector<T>(limit + 1);
}

void update(int idx, T delta) {
for (; idx <= limit; idx += lowbit(idx))
arr[idx] += delta;
}

T query(int idx) {
T ans = 0;
for (; idx > 0; idx -= lowbit(idx))
ans += arr[idx];
return ans;
}
};

class Solution {
public:
int createSortedArray(vector<int>& instructions) {
ll ans = 0;
set<int> s(instructions.begin(), instructions.end());
unordered_map<int, int> dict;
int idx = 0;
for (int i : s)
dict[i] = ++idx;
FenwickTree<int> ft((int)s.size());
int n = 0;
for (int i : instructions) {
int pos = dict[i];
int l = ft.query(pos - 1);
int r = n - ft.query(pos);
ans += min(l, r);
ft.update(pos, 1);
n++;
}
return ans % int(1e9 + 7);
}
};

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