title: 牛客编程巅峰赛S2第5场Python解法
categories:

• 刷题
  date: 2020-12-01 20:32:15
  tags:
• 刷题

https://ac.nowcoder.com/acm/contest/9556

这次题目比周末的简单。

第一题

链接：https://ac.nowcoder.com/acm/contest/9556/A

给你一个含有n个元素的数组arr[i]，请你告诉牛牛这个数组的中位数大还是平均数大，如果中位数更大输出1，如果平均数更大输出-1，如果中位数和平均数相等输出0

代码

class Solution:
    def Answerofjudge(self , arr ):
        # write code here
        arr.sort()
        s = sum(arr)
        av = s / len(arr)
        i = len(arr) >> 1
        if len(arr) % 2 == 1:
            x = arr[i]
        else:
            x = (arr[i] + arr[i-1]) / 2
        if abs(x - av) < 1e-7:
            return 0
        elif av > x:
            return -1
        return 1

排序，算平均数和中位数

第二题

链接：https://ac.nowcoder.com/acm/contest/9556/B

牛牛非常怕他的女朋友，怕到了走火入魔的程度，以至于每当他看到一个字符串同时含有n,p,y三个字母他都害怕的不行。现在有一个长度为m的只包含小写字母‘a’-‘z’的字符串x，牛牛想知道能令他不害怕的最长子串的长度是多少。（对于字符串”abc”来说，”c”,”ab”都是原串的子串，但”ac”不是原串子串）

示例1

"abcdefghijklmn"

返回值

14

示例2

"ynp"

返回值

2

示例3

"ypknnbpiyc"

返回值

7

代码

class Solution:
    def Maximumlength(self , x ):
        # write code here
        d = {'n': 0, 'p': 0, 'y': 0}  # 统计当前窗口内的三个字母数量
        l, r = 0, 0  # 窗口左右指针
        ans = 0  # 窗口最大值
        f = False  # 当前窗口内是否同时出现三种字母
        c = 0
        while l < len(x) and r < len(x):
            if not f:
                if x[r] in 'npy':
                    if d[x[r]] == 0:
                        c += 1
                        if c == 3:
                            f = True
                    d[x[r]] += 1
                r += 1
            else:
                if x[l] in 'npy':
                    if d[x[l]] == 1:
                        c -= 1
                        f = False
                    d[x[l]] -= 1
                l += 1
            if not f:
                ans = max(ans, r - l)
        return ans

滑动窗口，l 是起始位置，r是终止位置，r - l 是窗口大小（即当前字符串长度）

第三题

链接：https://ac.nowcoder.com/acm/contest/9556/C

给定牛牛一个后缀表达式s，计算它的结果，例如，1+1对应的后缀表达式为1#1#+，‘#’作为操作数的结束符号。

其中，表达式中只含有‘+’、’-‘、’*‘三种运算，不包含除法。

本题保证表达式一定合法，且计算过程和计算结果的绝对值一定不会超过101810^{18}1018

示例1

"1#1#+"

返回值

2

示例2

"12#3#+15#*"

返回值

复制

225

代码

class Solution:
    def solve(self , str ):
        # write code here
        # 解析后缀表达式
        x = str.split('#')
        xx = []
        for p in x:
            while len(p) != 1 and not p.isdigit(): # 判断是否粘连  ++ 或者 ++3 类似的情况
                xx.append(p[0])
                p = p[1:]
            xx.append(p)
        x = xx
        # 后缀表达式求值
        ns = [] # 操作数栈
        for p in x:
            if p.isdigit():
                ns.append(int(p))  # 入栈
            else:
                o1 = ns.pop()  # 出栈
                o2 = ns.pop()
                if p == '+':
                    a = o1 + o2
                elif p == '-':
                    a = o2 - o1
                else:
                    a = o2 * o1
                ns.append(a)  # 运算结果入栈
        return ns[0]

先按照 '#' split 字符串，这时候可能有 符号 + 操作数 或者 符号 + 符号黏在一起的情况。例如 “1#1#1#1#+++”，这里需要依次处理 split 后的每个元素。只要元素长度大于 1 且不是数字，就一定是粘连的情况，这时候第一个字符必然是符号，把符号取下来，继续验证是否粘连，直到没有粘连。