当前位置：首页 > article >正文

腾讯2025年校招笔试真题手撕（三）

article 2025/9/11 17:45:24

一、题目

今天正在进行赛车车队选拔，每一辆赛车都有一个不可以改变的速度。现在需要选取速度差距在10以内的车队（车队中速度的最大值减去最小值不大于10），用于迎宾。车队的选拔按照的是人越多越好的原则，给出n辆车的速度，你能选出满足条件的最多车辆的车队吗。输入描述第一行一个数字n(1<=n<=100000)。接下来一行n个整数，speed[i] 表示第i辆车的速度为speed（i）(1<=speed[i]<=109)。输出描述输出一行，最大车辆数目。

二、分析

在这个问题中，我们的目标是从给定的赛车速度中找到一个满足速度差距不超过10的最大车队。首先，需要理解题目中的输入和输出要求。输入的第一行是一个整数n，表示赛车的数量。接下来的一行中有n个整数，分别代表每辆赛车的速度。我们的任务是找出这些赛车中一个最大的子集，使得这个子集中速度的最大值和最小值之差不超过10，并输出这个最大子集的大小。

为了有效地解决这个问题，可以采用排序和滑动窗口技术相结合的方法。首先，将所有赛车的速度进行排序。排序后，我们可以利用滑动窗口来维护一个满足条件的区间。滑动窗口的左侧代表当前区间的起始位置，右侧代表区间的结束位置。窗口内的所有速度都在一个有效的范围内，即最大值和最小值的差不超过10。在排序后的速度列表中，最大值和最小值分别对应于窗口的右端和左端。

在滑动窗口的过程中，右指针不断向右移动以扩展窗口。当窗口内的最大速度和最小速度的差超过10时，左指针向右移动以缩小窗口的大小，确保窗口内的速度差不超过10。在每次调整窗口的大小时，记录下当前窗口的大小，并与历史最大值进行比较，以便找出满足条件的最大车队的大小。这种方法的优势在于它不需要遍历所有可能的子集，而是通过线性扫描来找到最优解，从而大大提高了效率。在整个过程中，排序操作的时间复杂度为O(n log n)，而滑动窗口的遍历操作为O(n)。因此，整个算法的时间复杂度为O(n log n)，这使得该算法能够在合理的时间内处理较大的输入规模。

三、代码

这段代码首先从标准输入读取整个输入，然后将输入的字符串分割成一个列表。第一个元素被转换为数整以表示赛车的数量n，随后的n个元素被转换为整数列表speed。对speed进行排序后，初始化左指针left为0，max_count为1。然后，通过一个循环遍历速度列表，使用右指针right向右扩展窗口，同时检查窗口内的速度差是否超过10。如果超过，则移动左指针left以缩小窗口，确保窗口内的速度差不超过10。在每次调整窗口的大小时，比较当前窗口的大小和历史最大值，并更新max_count。最后，输出max_count作为结果。

def main():import sysinput = sys.stdin.read().split()n = int(input[0])speed = list(map(int, input[1:n+1]))speed.sort()max_count = 1left = 0for right in range(n):while speed[right] - speed[left] > 10:left += 1current_length = right - left + 1if current_length > max_count:max_count = current_lengthprint(max_count)if __name__ == "__main__":main()

读取输入：
- 使用 sys.stdin.read() 读取整个输入，并将其分割成一个列表。
- 第一个元素是整数 n，表示赛车的数量。
- 接下来的 n 个元素是赛车的速度，存储在列表 speed 中。
排序：
- 对速度列表进行排序，以便可以使用滑动窗口技术来查找满足条件的车队。
初始化：
- max_count 用于记录找到的最大车队大小，初始化为1（因为至少有一辆车可以组成一个车队）。
- left 是滑动窗口的左指针，初始化为0。
滑动窗口：
- 使用右指针 right 遍历速度数组。
- 对于每个右指针位置，检查当前窗口内的速度差是否超过10。
- 如果速度差超过10，移动左指针以缩小窗口，直到速度差满足条件。
- 计算当前窗口的大小，并更新 max_count5。