# # Leetcode 第40场双周赛题解

## # Problem A - 最大重复子字符串 (opens new window)

### # 方法一：暴力枚举

class Solution:
def maxRepeating(self, sequence: str, word: str) -> int:
n = len(sequence)
m = len(word)
for i in range(n // m, 0, -1):
if word * i in sequence:
return i
return 0
1
2
3
4
5
6
7
8

### # 方法二：KMP算法

class Solution:
def maxRepeating(self, sequence: str, word: str) -> int:
n = len(sequence)
m = len(word)
s = word + '#' + sequence
pi = [0] * (n + m + 1)
match = [0] * (n + m + 1)
for i in range(1, n + m + 1):
j = pi[i - 1]
while j > 0 and s[i] != s[j]:
j = pi[j - 1]
pi[i] = j + 1 if s[i] == s[j] else 0
if pi[i] == m:
match[i] = match[i - m] + 1 if i >= m else 1
return max(match)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

## # Problem B - 合并两个链表 (opens new window)

def flatten(node):
p = node
while p:
yield p.val
p = p.next

class Solution:
def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:
la = list(flatten(list1))
lb = list(flatten(list2))
ans = la[:a] + lb + la[b+1:]
sen = ListNode(0)
p = sen
for i in ans:
p.next = ListNode(i)
p = p.next
return sen.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

## # Problem C - 设计前中后队列 (opens new window)

class FrontMiddleBackQueue {
deque<int> left, right;
void maintain() {
if (left.size() > right.size()) {
right.push_front(left.back());
left.pop_back();
} else if (left.size() + 1 < right.size()) {
left.push_back(right.front());
right.pop_front();
}
}
public:
FrontMiddleBackQueue() {
}

void pushFront(int val) {
left.push_front(val);
maintain();
}

void pushMiddle(int val) {
left.push_back(val);
maintain();
}

void pushBack(int val) {
right.push_back(val);
maintain();
}

int popFront() {
if (left.empty()) {
if (right.empty())
return -1;
int ans = right.front();
right.pop_front();
return ans;
}
int ans = left.front();
left.pop_front();
maintain();
return ans;
}

int popMiddle() {
if (left.empty() && right.empty())
return -1;
if (left.size() == right.size()) {
int ans = left.back();
left.pop_back();
return ans;
}
int ans = right.front();
right.pop_front();
return ans;
}

int popBack() {
if (right.empty())
return -1;
int ans = right.back();
right.pop_back();
maintain();
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
60
61
62
63
64
65
66
67

## # Problem D - 得到山形数组的最少删除次数 (opens new window)

class Solution {
public:
int minimumMountainRemovals(vector<int>& nums) {
int n = nums.size();
vector<int> L(n), R(n);
vector<int> LIS;
for (int i = 0; i < n; ++i) {
auto it = lower_bound(LIS.begin(), LIS.end(), nums[i]);
if (it == LIS.end()) {
L[i] = LIS.size();
LIS.emplace_back(nums[i]);
} else {
L[i] = it - LIS.begin();
*it = nums[i];
}
}
LIS.clear();
for (int i = n - 1; i >= 0; --i) {
auto it = lower_bound(LIS.begin(), LIS.end(), nums[i]);
if (it == LIS.end()) {
R[i] = LIS.size();
LIS.emplace_back(nums[i]);
} else {
R[i] = it - LIS.begin();
*it = nums[i];
}
}
int ans = n;
for (int i = 0; i < n; ++i) {
if (L[i] > 0 && R[i] > 0)
ans = min(ans, n - L[i] - R[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