leetcode contest 154 writeup

 

概要

比赛链接:leetcode第154周周赛

题目 难度 知识点
“气球” 的最大数量 简单
反转每对括号间的子串 中等
K 次串联后最大子数组之和 中等 lcs/分类讨论
查找集群内的「关键连接」 困难 tarjan算法

注:思路是理想思路,代码有可能是我比赛时写的,就不那么理想.

所以代码与思路不一定等价

第一题

思路

根据字母的数量判断就行

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
def maxNumberOfBalloons(self, text: str) -> int:
d = dict()
d["b"] = d["a"] = d["l"] = d["o"] = d["n"] = 0
for c in text:
if c not in d:
d[c] = 1
else:
d[c] += 1
num_b = d["b"]
num_a = d["a"]
num_l = d["l"]
num_o = d["o"]
num_n = d["n"]
m_single = min(num_b, num_a, num_n)
m_double = min(num_l, num_o)
return min(m_single, int(m_double / 2))


s = Solution()
print(s.maxNumberOfBalloons("leetcode"))

第二题

思路

将待翻转的字符串压栈就可以,类似的有用括号表示优先级的,都可以用这个方法。

因为理论上翻转两次可以抵消,我就写了注释里面的代码,但好像有点问题,我就懒得改进了。

代码

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
import typing


class Solution:
def reverseParentheses(self, s: str) -> str:
ans = ['']
for c in s:
if c == '(':
ans += ['']
elif c == ')':
ans[-2] += ans[-1][:: -1] # 倒数第二个串压入倒数第一个的翻转
ans.pop()
else:
ans[-1] += c # 压入最后一个字符串
return ans[0]
# ans: typing.List[(str, int)] = []
# level = 0 # 翻转等级
# temp = ""
# for c in s:
# if c == '(':
# ans.append((temp, level))
# level += 1
# temp = ""
# elif c == ')':
# ans.append((temp, level))
# level -= 1
# temp = ""
# else:
# temp += c
# result = ""
# for a, l in ans:
# if l % 2 == 1:
# result += a[::-1]
# else:
# result += a
# return result


s = Solution()
print(s.reverseParentheses("a(bcdefghijkl(mno)p)q"))

第三题

思路

分成几种情况就可以。

  1. 单周期总和为负数:结果为单周期最大的子序列和,用lcs就行。
  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
31
32
33
34
35
36
37
38
39
40
41
42
43
#!/usr/bin/env Python
# coding=utf-8
from typing import List


def find_max_child(l: List) -> (int, int, int):
# return left right sum
dp = [0] * len(l)
lefts = [0] * len(l) # 以i结尾的最大的子序列的左界
dp[0] = l[0] # 以i为结尾的最大子序列
lefts[0] = 0
for i in range(1, len(l)):
if l[i] > dp[i - 1] + l[i]:
dp[i] = l[i]
lefts[i] = i
else:
dp[i] = dp[i - 1] + l[i]
lefts[i] = lefts[i - 1]
maxi = 0
for i in range(1, len(l)):
if dp[i] > dp[maxi]:
maxi = i
return lefts[maxi], maxi, dp[maxi]


class Solution:
def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
length = len(arr)
one_max = find_max_child(arr)[2] # 一个周期内最大
if k == 1:
return max(0, one_max)
s = sum(arr)
pre_sum = [arr[0]]
for i in range(1, length):
pre_sum.append(pre_sum[i - 1] + arr[i])
after_sum = [arr[-1]]
for i in range(1, length):
after_sum.append(after_sum[i - 1] + arr[- i - 1])
return (max(pre_sum + [0]) + max(after_sum + [0]) + (k - 2) * max(s, 0)) % 1000000007


s = Solution()
s.kConcatenationMaxSum([1, 2], 3)

第四题

思路

tarjan算法一把梭,听说中文版比赛少一组测试用例,可以取巧(已经修复。

这题的时间卡的有问题,不修常数的话,有些语言能过,py过不了。不过我就不修常数了

代码

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
class Solution:
def __init__(self):
self.maxV = 100001
self.dfn = [0 for _ in range(self.maxV)]
self.low = [self.maxV for _ in range(self.maxV)]
self.vis = [0 for _ in range(self.maxV)]
self.edgs = [[] for _ in range(self.maxV)]
self.ans = []
self.times = 0

def tarjan(self, curr, parent):
self.times += 1
self.low[curr] = self.times
self.dfn[curr] = self.times
self.vis[curr] = 1

for e in self.edgs[curr]:
if e == parent:
continue

if self.vis[e] == 0:
self.tarjan(e, curr)
self.low[curr] = min(self.low[curr], self.low[e])
if self.low[e] > self.dfn[curr]:
self.ans.append([curr, e])
else:
self.low[curr] = min(self.low[curr], self.dfn[e])

def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
for conn in connections:
self.edgs[conn[0]].append(conn[1])
self.edgs[conn[1]].append(conn[0])

self.tarjan(0, -1)
return self.ans

后记

不得不提,自从我花了一点时间写出了根据模板自动生成文档的程序,写周赛题解方便了很多。