Bluefissure's Blog

A Place for Recording

0%

LeetCode Weekly Contest 154

Posted on Edited on In , Disqus:

简单题 + 板子

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 时吃瘪（）

后记

复健路漫漫