250321饿了么后端暑期笔试

a了2.8，贴个Java代码供参考

统计低谷数量

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            int[] nums = new int[n];
            for (int i = 0; i < n; i++) nums[i] = in.nextInt();
            int res = 0;
            for (int i = 0; i+2 < n; i++) {  // 遍历判断是不是低谷即可
                if (nums[i] >= nums[i+1] && nums[i+1] <= nums[i+2]) res++;
            }
            System.out.println(res);
        }
    }
}

计算奇偶字符串在位置差范围内的组合情况

这题题目对这个位置差的描述有问题，a和d的位置差应该是3，题目说是2。。

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        // 这个位置差描述有问题！！！！！
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            int g = in.nextInt();
            String s = in.next();
            char[] cs = s.toCharArray();
            long[] oddCnt = new long[26], evenCnt = new long[26];
            for (int i = 0; i < n; i++) {  // 分别统计奇数和偶数位置的字符
                if (i % 2 == 0) {
                    evenCnt[cs[i]-'a']++;
                } else {
                    oddCnt[cs[i]-'a']++;
                }
            }
            long[] oddSum = new long[27], evenSum = new long[27];  // 计算oddCnt和evenCnt的前缀和
            for (int i = 0; i < 26; i++) {
                oddSum[i+1] = oddSum[i] + oddCnt[i];
                evenSum[i+1] = evenSum[i] + evenCnt[i];
            }
            long res = 0;
            for (int i = 0; i < 26; i++) {
                int nxt = i+g+1 > 26 ? 26 : i+g+1;  // 位置差g范围的右边界
                res += oddCnt[i] * (oddSum[nxt] - oddSum[i+1]);  // 当前字符和后面范围内的字符，直接相乘个数
                res += oddCnt[i] * (oddCnt[i]-1) / 2;  // 当前相同字符，计算选两个的组合数
                res += evenCnt[i] * (evenSum[nxt] - evenSum[i+1]);  // 偶数位置同理
                res += evenCnt[i] * (evenCnt[i]-1) / 2;
            }
            System.out.println(res);
        }
    }
}

按顺序接雨水

所有case，n的总和最多3*10^5

a了80%，应该是这个解法需要排序，太耗时了

看了下别人ak的思路，也用到了排序，这里主要耗时的地方应该就是排序吧，那不知道为什么过不了了

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int T = in.nextInt();
            while (T-- > 0) {
                int n = in.nextInt(), k = in.nextInt();
                int[][] nums = new int[n+1][2];
                nums[0] = new int[]{k, 0};  // 第0个位置存入传送点
                for (int i = 0; i < n; i++) {
                    nums[i+1] = new int[]{in.nextInt(), in.nextInt()};
                }
                Arrays.sort(nums, (a, b) -> a[1]-b[1]);  // 按照纵坐标从小到大排序
                int res = 0;
                for (int i = 0; i < n; i++) {
                    int time = nums[i+1][1] - nums[i][1];  // 相邻纵坐标的差值，就是可以运动的时间
                    if (time == 0) {  // 如果时间为0，那么这里直接认为它走不到（似乎不用考虑nums[i+1][0] == k的情况）
                        res = -1;
                        break;
                    }
                    int curV = (Math.abs(nums[i+1][0]-k)-1)/time + 1;  // 计算当前速度，向下取整
                    res = Math.max(res, curV);  // 取最大值
                }
                System.out.println(res);
            }
        }
    }
}