leetcode contest 154 writeup

概要

比赛链接:leetcode第154周周赛

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

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

第一题

思路

根据字母的数量判断就行

代码

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"))

第二题

思路

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

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

代码

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. 单周期总数为正数：结果为中间的加起来，加上头尾两端为首的最大的连续子序列和，用前/后缀和就可以了。如果这个值比单周期的最大子序列和还大的话，就用上面的。

小于零去领，大于零记得模。

代码

#!/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过不了。不过我就不修常数了

代码

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

后记

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