牛客编程巅峰赛S2第5场 - 青铜&白银&黄金

牛客： 牛客编程巅峰赛S2第5场 - 青铜&白银&黄金

基本上三题都是直接模拟就能过

第一题： 牛牛算数

直接排序，求和取平均值 以及 len 定位到中位数

直接比较就行。

AC Code

import java.util.*;


public class Solution {
    /**
     * 
     * @param arr int整型一维数组 
     * @return int整型
     */
    public int Answerofjudge (int[] arr) {
        // write code here
        double avg = 0;
        Arrays.sort(arr);
        int len = arr.length;
        for(int i = 0; i < len ; i++){
            avg += arr[i];
        }
        double midv = 0;
        if(len % 2 == 1)
            midv = arr[len / 2];
        else 
            midv = (arr[len / 2] + arr[(len / 2) - 1]) / 2.0;
       
        
        if(midv > (avg / (double)len)) return 1;
        else if(midv < (avg / (double)len)) return -1;
        else return 0;
    }
}

---

第二题： 怕npy的牛牛

一开始思路： 双重循环暴力截取所有区间的子串，算出能截取到的最长子串， 超时两次。 （ 有点想到 最长子序列

换了种思路， 直接 双指针 + 模拟

使用 slow 记录子串开始的位置， i 为子串结束的位置。

当子串同时存在 n p y 三个字符的时候， slow 向后移动，直到这三个字符没有同时存在。

AC Code

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回符合题意的最长的子串长度
     * @param x string字符串 
     * @return int整型
     */
    public int Maximumlength (String s) {
        // write code here
        int ans = 1;
        int slow = 0;
        int n = 0, p = 0, y = 0;
        int temp = 0;
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) == 'n') n++;
            else if(s.charAt(i) == 'p') p++;
            else if(s.charAt(i) == 'y') y++;
            
            while(n >= 1 && p >= 1 && y >= 1) {
                ans = Math.max(ans, i - slow);
                if(s.charAt(slow) == 'n') n--;
                else if(s.charAt(slow) == 'p') p--;
                else if(s.charAt(slow) == 'y') y--;
                slow++;
            }
            
            ans = Math.max(ans, i - slow + 1);
        }
        
        return ans;
    }
    
}

---

第三题： 牛牛与后缀表达式

给定字符串， 计算其中的结果，就是那种表达式计算的题

一般思路： 创建两个栈， 一个存储操作数， 一个存储操作符，每次遇到操作符， 取出两个数进行计算。然后存回操作数栈中。

这题使用一个栈就行了， 因为这个不用考虑运算符优先级， 先在前面的运算符优先运算。

模拟。

AC Code

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 给定一个后缀表达式，返回它的结果
     * @param str string字符串 
     * @return long长整型
     */
    public long solve (String str) {
        // write code here
        Stack<Long> s = new Stack<>();
        Stack<String> op = new Stack<>();
        char[] cs = str.toCharArray();
        
        long temp = 0;
        for(int i = 0; i < cs.length; i++){
            if(cs[i] == '#'){
                s.add(temp);
                temp = 0;
                continue ;
            }
            if(cs[i] >= '0' && cs[i] <= '9'){
                temp = temp * 10 + (cs[i] - '0');
            } else {
                // 操作符
                // 取出两个数
                long a = s.pop();
                long b = s.pop();
                long res = 0;
                if(cs[i] == '+'){
                    res = a + b;
                }else if(cs[i] == '-'){
                    res = (b - a);                    
                } else if(cs[i] == '*'){
                    res = (a * b);
                }
                
                // 回栈
                s.add(res);
            }
            
        }
        
        return s.pop();
    }
}