# # Leetcode 第55场双周赛题解

## # Problem A - 删除一个元素使数组严格递增 (opens new window)

### # 方法一：暴力

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

class Solution:
def canBeIncreasing(self, nums: List[int]) -> bool:
n = len(nums)
for i in range(n):
sub = nums[:i] + nums[i + 1:]
good = True
for j in range(len(sub) - 1):
if sub[j + 1] <= sub[j]:
good = False
break
if good:
return True
return False
1
2
3
4
5
6
7
8
9
10
11
12
13

### # 方法二：双指针

• 左指针找出最长的严格递增的前缀；
• 右指针找出最长的严格递增的后缀。

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

class Solution {
public:
bool canBeIncreasing(vector<int>& nums) {
int n = nums.size();
if (n <= 2)
return true;

int p = 0;
while (p + 1 < n && nums[p + 1] > nums[p])
p++;
if (p == n - 1)
return true;

int q = n - 1;
while (q >= 1 && nums[q - 1] < nums[q])
q--;

if (p + 2 == q && nums[p] < nums[q])
return true;

if (p + 1 == q) {
if (p == 0 || (p >= 1 && nums[p - 1] < nums[q]))
return true;
if (q == n - 1 || (q + 1 < n && nums[p] < nums[q + 1]))
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
24
25
26
27
28
29
30

## # Problem B - 删除一个字符串中所有出现的给定子字符串 (opens new window)

### # 方法一：模拟

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

class Solution {
public:
string removeOccurrences(string s, string part) {
string ans;
for (char c : s) {
ans.push_back(c);
if (ans.size() >= part.size() && ans.substr(ans.size() - part.size(), part.size()) == part)
ans = ans.substr(0, ans.size() - part.size());
}
return ans;
}
};
1
2
3
4
5
6
7
8
9
10
11
12

### # 方法二：KMP算法

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

class Solution:
def removeOccurrences(self, s: str, part: str) -> str:
m = len(part)
pi = [0] * m
for i in range(1, m):
j = pi[i - 1]
while j != 0 and part[i] != part[j]:
j = pi[j - 1]
pi[i] = j + 1 if part[i] == part[j] else 0

ans = []
dp = [0]
for c in s:
ans.append(c)
j = dp[-1]
while j != 0 and c != part[j]:
j = pi[j - 1]
dp.append(j + 1 if c == part[j] else 0)
if dp[-1] == m:
dp = dp[:-m]
ans = ans[:-m]

return ''.join(ans)
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 - 最大子序列交替和 (opens new window)

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

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

class Solution:
def maxAlternatingSum(self, nums: List[int]) -> int:
odd = int(-1e10)
even = 0
for num in nums:
odd, even = max(odd, even + num), max(even, odd - num)
return odd
1
2
3
4
5
6
7

## # Problem D - 设计电影租借系统 (opens new window)

### # 方法一：数据结构+模拟

• 使用一个键值为set的哈希表来存储当前拥有每部电影的店铺。
• 使用一个set来存储当前借出的所有电影。
• 使用一个map来存储每个店铺中每部电影的租借价格。

• search$\mathcal{O}(\log N)$
• rent$\mathcal{O}(\log N+\log M)$
• drop$\mathcal{O}(\log N+\log M)$
• report$\mathcal{O}(\log M)$

class MovieRentingSystem {
int n;
unordered_map<int, set<pair<int, int>>> has;
set<tuple<int, int, int>> borrowed;
map<pair<int, int>, int> query;

public:
MovieRentingSystem(int n, vector<vector<int>>& entries): n(n) {
for (auto &v : entries) {
int shop = v[0], movie = v[1], price = v[2];
query[{shop, movie}] = price;
has[movie].emplace(price, shop);
}
}

vector<int> search(int movie) {
vector<int> ans;
for (int i = 0; i < 5 && !has[movie].empty(); ++i) {
ans.emplace_back(has[movie].begin()->second);
has[movie].erase(has[movie].begin());
}

for (int shop : ans)
has[movie].emplace(query[{shop, movie}], shop);

return ans;
}

void rent(int shop, int movie) {
int price = query[{shop, movie}];
has[movie].erase({price, shop});
borrowed.emplace(price, shop, movie);
}

void drop(int shop, int movie) {
int price = query[{shop, movie}];
has[movie].emplace(price, shop);
borrowed.erase({price, shop, movie});
}

vector<vector<int>> report() {
vector<vector<int>> ans;

for (int i = 0; i < 5 && !borrowed.empty(); ++i) {
auto [price, shop, movie] = *borrowed.begin();
ans.push_back({shop, movie});
borrowed.erase(borrowed.begin());
}

for (auto &v : ans) {
int shop = v[0], movie = v[1];
int price = query[{shop, movie}];
borrowed.emplace(price, shop, movie);
}

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59