美团24春招笔试一笔

题目分布

共5个编程题

题目

Q1：

Q2：

我的题解：

package leetcode;
import java.util.ArrayList;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main1 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        long cnt = 0;
        long cnt0 = 0;
        ArrayList<Integer> list = new ArrayList<>();
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            int q = in.nextInt();
            for (int i = 0; i < n; i++) {
                list.add(in.nextInt());
                cnt += list.get(i);
                if (list.get(i) == 0) cnt0++;
                // System.out.print(list.get(i));
            }
            for (int i = 0; i < q; i++) {
                long l = in.nextLong();
                long r = in.nextLong();
                System.out.println((cnt + l*cnt0) + " " + (cnt + r*cnt0));
            }
        }
    }
}

春招的第一个笔试，属实有点紧张了，没有想起来用前缀和数组，而是使用了最简单的且浪费效率遍历查询，最终虽然AC了90% ，但是还是超时了，造成没有全AC的原因之一可能还与没有处理[L,R]边界有关！

下面是来自AI的建议：

造成这段代码超时的原因在于：重复计算：在处理每个查询时，代码都会遍历整个数组来重新计算总和cnt和0的个数cnt0。对于多个查询，这种做法会> 导致大量的重复计算。无效操作：对每个查询范围内的元素并未进行任何针对性的计算，而是直接使用全局累计的cnt和cnt0进行求解。这种方> 式无法正确处理区间内包含0的情况，因为在计算结果时未剔除区间内的0的影响。为了优化这个问题，应当在读取输入数组之后，预先计算出所有非零元素的累加和（可以采用前缀和的方法），同时记录> 每个位置之前连续非零元素的累加和。这样，在处理查询时，可以直接根据前缀和计算出给定区间的非零元素之和，从而> 避免重复计算并提高效率。