LeetCode Weekly Contest 154

简单题 + 板子

1189. Maximum Number of Balloons

数气球(字面意义上)

1
2
3
class Solution:
def maxNumberOfBalloons(self, text: str) -> int:
return min(sum([ch=='b' for ch in text]), sum([ch=='a' for ch in text]), sum([ch=='l' for ch in text])//2, sum([ch=='o' for ch in text])//2, sum([ch=='n' for ch in text]))

1190. Reverse Substrings Between Each Pair of Parentheses

模拟可过

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
def reverseParentheses(self, s: str) -> str:
tmp_str = ""
stk = []
level = 0
for ch in s:
if ch == '(':
stk.append(tmp_str)
tmp_str = ""
level += 1
elif ch == ')':
tmp_str = "".join(reversed(tmp_str))
tmp_str = stk.pop() + tmp_str
level -= 1
else:
tmp_str += ch
return tmp_str

1191. K-Concatenation Maximum Sum

单个数组的最大区间和可以翻Contest 153 的1186的dp1

然后答案则是:

  • 单数组最大区间 (k == 1)
  • 最大后缀+最大前缀 (k == 2)
  • 最大后缀+中间$k-2$个的数组和+最大前缀 (k > 2)

三种情况中最大的。

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
class Solution:
def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
MOD = 10**9 + 7
INF = 10**9 + 1000
dp1 = collections.Counter()
ans = arr[0]
presum = [0, -1, 0, -1]
sufsum = [0, -1, 0, -1]
totsum = sum(arr)
for i, a in enumerate(arr):
dp1[i] = a;
j = len(arr) - i - 1
presum[0] += a
sufsum[0] += arr[j]
if presum[0] > 0:
presum[1] = i
if presum[0] > presum[2]:
presum[2] = presum[0]
presum[3] = i
if sufsum[0] > 0:
sufsum[1] = j
if sufsum[0] > sufsum[2]:
sufsum[2] = sufsum[0]
sufsum[3] = j
if i:
dp1[i] = max(a, dp1[i-1] + a);
ans = max(ans, dp1[i])
if k > 1:
ans = max(ans, max(totsum, 0) * k, max(totsum, 0) * max(0, k-2) + max(presum[2], 0) + max(sufsum[2], 0))
return max(ans, 0)%MOD

PS: 忘了取模WA了好多发

1192. Critical Connections in a Network

模板题,没什么意思:Bridge

Tarjan’s bridge-finding algorithm:

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

def tarjan(x, fa, bid):
global dfn, dot, low, ans
dot += 1
dfn[x] = dot
low[x] = dot
for y in bid[x]:
if dfn[y] == 0:
tarjan(y, x, bid)
low[x] = min(low[x], low[y])
if low[y] > dfn[x]:
ans.append([x, y])
elif y != fa:
low[x] = min(low[x], dfn[y])

class Solution:
def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
global dfn, dot, low, ans
dfn = [0] * (100000+5)
low = [0] * (100000+5)
dot = 0
ans = []
bid = collections.defaultdict(list)
for edge in connections:
bid[edge[0]].append(edge[1])
bid[edge[1]].append(edge[0])
for i in range(0, n):
if dfn[i] == 0:
tarjan(i, i, bid)
return ans

PS: Leetcode 的 Python 的 Run Code 环境和 Submit 环境对全局变量的行为不一致,在外部定义全局变量会在 Submit 时吃瘪()

后记

复健路漫漫