笔试时间：2024年09月13日 秋招

历史笔试传送门：2023秋招笔试合集

第一题

题目

vivo项目组新老员工分组完成任务员工数组staff，其中0表示新员工，1表示老员工分组规则如下:1、一个小组至多3个员工2、一个小组中最多有1个老员工3、如果一个小组中有1个老员工，那么这组最多有2个员工，求最小的分组数。

输入描述

输入员工数组 staff，元素只包含0,1。

输出描述

输出一个整数，表示最小分组数。

样例输入一

[1,0,0,0,1]

样例输出一

3

样例输入二

[1,1]

样例输出二

2

参考题解

模拟。遍历员工数组：根据规则进行分组。如果遇到一个老员工 (1)，需要开始一个新组。如果遇到两个新员工 (0)，它们可以被加入到一个已有的组，或者形成一个新的组。一旦满足组内有一个老员工且组最大人数为2的情况，或者只有新员工且数量达到3的情况，形成一个新的组。统计数最小的分组数。

C++：[此代码未进行大量数据的测试，仅供参考]

#include <vector>

int minimumGroups(const std::vector<int>& staff) {
    int n = staff.size();
    int groups = 0;
    int i = 0;

    while (i < n) {
        if (staff[i] == 1) {  // 老员工情况
            groups++;  // 老员工自己成组
            if (i + 1 < n && staff[i + 1] == 0) {  // 检查下一个是否为新员工
                i += 2;  // 老员工和一个新员工成组
            } else {
                i++;  // 老员工单独成组
            }
        } else {  // 新员工情况
            int count = 0;
            while (i < n && staff[i] == 0 && count < 3) {  // 最多3个新员工成组
                i++;
                count++;
            }
            groups++;  // 新员工成组
        }
    }

    return groups;
}

Java：[此代码未进行大量数据的测试，仅供参考]

public static int minimumGroups(int[] staff) {
        int n = staff.length;
        int groups = 0;
        int i = 0;

        while (i < n) {
            if (staff[i] == 1) {  // 老员工情况
                groups++;  // 老员工自己成组
                if (i + 1 < n && staff[i + 1] == 0) {  // 检查下一个是否为新员工
                    i += 2;  // 老员工和一个新员工成组
                } else {
                    i++;  // 老员工单独成组
                }
            } else {  // 新员工情况
                int count = 0;
                while (i < n && staff[i] == 0 && count < 3) {  // 最多3个新员工成组
                    i++;
                    count++;
                }
                groups++;  // 新员工成组
            }
        }

        return groups;
}

Python：[此代码未进行大量数据的测试，仅供参考]

def minimumGroups(staff):
    n = len(staff)
    groups = 0
    i = 0

    while i < n:
        if staff[i] == 1:  # 老员工情况
            groups += 1  # 老员工自己成组
            if i + 1 < n and staff[i + 1] == 0:  # 检查下一个是否为新员工
                i += 2  # 老员工和一个新员工成组
            else:
                i += 1  # 老员工单独成组
        else:  # 新员工情况
            count = 0
            while i < n and staff[i] == 0 and count < 3:  # 最多3个新员工成组
                i += 1
                count += 1
            groups += 1  # 新员工成组

    return groups

第二题

题目

你是一名手机应用开发工程师，需要分析应用在手机上的内存使用情况。你有一个数组 memoryUsage，其中 memoryUsage[i]表示应用在第 i秒的内存使用量(以MB为单位)。为了评估应用的稳定性，你需要找出每个连续 k秒内的内存使用量的波动范围(即最大值与最小值的差值)，并返回这些波动范围。

样例输入一

[120,150,110,180,130,160,140,170],3

样例输出一

[40,70,70,50,30,30]

样例输入二

[80,100,70,90,60,85,75, 95, 110],4

样例输出二

[30,40,30,30,35,35]

参考题解

滑动窗口。滑动窗口：使用两个双端队列（Deque）分别维护当前窗口的最大值和最小值。最大值队列：从左到右存储当前窗口的降序元素（最大值在最前面）。最小值队列：从左到右存储当前窗口的升序元素（最小值在最前面）。2、遍历数组：对于每个新元素，移除队列中已经不在窗口范围内的元素。更新两个队列，确保队列中的元素保持排序。当窗口大小达到 k 时，计算最大值与最小值的差值，并存储到结果数组中。

C++：[此代码未进行大量数据的测试，仅供参考]

#include <vector>
#include <deque>

std::vector<int> memoryFluctuations(const std::vector<int>& memoryUsage, int k) {
    int n = memoryUsage.size();
    if (n == 0 || k <= 0 || k > n) return {};

    std::vector<int> result(n - k + 1);
    std::deque<int> maxDeque;
    std::deque<int> minDeque;

    for (int i = 0; i < n; i++) {
        // 移除不在当前窗口范围内的元素
        if (!maxDeque.empty() && maxDeque.front() < i - k + 1) maxDeque.pop_front();
        if (!minDeque.empty() && minDeque.front() < i - k + 1) minDeque.pop_front();

        // 维护最大值队列
        while (!maxDeque.empty() && memoryUsage[maxDeque.back()] <= memoryUsage[i]) maxDeque.pop_back();
        maxDeque.push_back(i);

        // 维护最小值队列
        while (!minDeque.empty() && memoryUsage[minDeque.back()] >= memoryUsage[i]) minDeque.pop_back();
        minDeque.push_back(i);

        // 计算当前窗口的最大最小值的差值
        if (i >= k - 1) {
            int maxVal = memoryUsage[maxDeque.front()];
            int minVal = memoryUsage[minDeque.front()];
            result[i - k + 1] = maxVal - minVal;
        }
    }

    return result;
}

Java：[此代码未进行大量数据的测试，仅供参考]

public static int[] memoryFluctuations(int[] memoryUsage, int k) {
        int n = memoryUsage.length;
        if (n == 0 || k <= 0 || k > n) return new int[0];

        int[] result = new int[n - k + 1];
        Deque<Integer> maxDeque = new ArrayDeque<>();
        Deque<Integer> minDeque = new ArrayDeque<>();

        for (int i = 0; i < n;