# # Leetcode 第45场双周赛题解

## # Problem A - 唯一元素的和 (opens new window)

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

class Solution:
def sumOfUnique(self, nums: List[int]) -> int:
cnt = collections.Counter(nums)
ans = 0
for key in cnt:
if cnt[key] == 1:
ans += key
return ans

1
2
3
4
5
6
7
8

## # Problem B - 任意子数组和的绝对值的最大值 (opens new window)

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

class Solution:
def maxAbsoluteSum(self, nums: List[int]) -> int:
ans = 0
lo = 0
hi = 0
for num in nums:
lo = min(0, lo + num)
hi = max(0, hi + num)
ans = max(ans, abs(lo), abs(hi))
return ans

1
2
3
4
5
6
7
8
9
10

## # Problem C - 删除字符串两端相同字符后的最短长度 (opens new window)

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

class Solution {
public:
int minimumLength(string s) {
int n = s.size();
int l = 0, r = n - 1;
while (l < r && s[l] == s[r]) {
int nl = l, nr = r;
while (nl + 1 < n && s[nl + 1] == s[l])
nl++;
while (nr - 1 >= 0 && s[nr - 1] == s[r])
nr--;
l = nl + 1, r = nr - 1;
}
return max(0, r - l + 1);
}
};

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

## # Problem D - 最多可以参加的会议数目 II (opens new window)

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

class Solution {
public:
int maxValue(vector<vector<int>>& events, int k) {
int n = events.size();
set<int> s;
for (auto &v : events)
s.insert(v[0]), s.insert(v[1]);
unordered_map<int, int> mp;
int idx = 0;
for (int i : s)
mp[i] = ++idx;
vector<vector<pair<int, int>>> end(idx + 1);
for (auto &v : events) {
end[mp[v[1]]].emplace_back(mp[v[0]], v[2]);
}

vector<vector<int>> dp(idx + 1, vector<int>(k + 1));
dp[0][0] = 0;
int ans = 0;
for (int i = 1; i <= idx; ++i) {
for (int j = k; j >= 0; --j) {
dp[i][j] = dp[i - 1][j];
if (j < k) {
for (auto [start, value] : end[i])
dp[i][j + 1] = max(dp[i][j + 1], dp[start - 1][j] + value);
}
}
}

for (int i = 1; i <= k; ++i)
ans = max(ans, dp[idx][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
27
28
29
30
31
32
33
34
35