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

目录

1. 第一题
   1. 代码
2. 第二题
   1. 示例1
      1. 返回值
   2. 示例2
      1. 返回值
   3. 示例3
      1. 返回值
   4. 代码
3. 第三题
   1. 示例1
      1. 返回值
   2. 示例2
      1. 返回值
   3. 代码

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 且不是数字，就一定是粘连的情况，这时候第一个字符必然是符号，把符号取下来，继续验证是否粘连，直到没有粘连。