牛客笔试｜美团2024春招第一场【测试方向】

第一题：小美的数组询问

小美拿到了一个由正整数组成的数组，但其中有一些元素是未知的（用 0 来表示）。
现在小美想知道，如果那些未知的元素在区间 [l, r] 范围内随机取值的话，数组所有元素之和的最小值和最大值分别是多少？共有 q次 询 

输入描述：

第一行输入两个正整数 n, q ，代表数组大小和询问次数。
第二行输入 n 个整数。
接下来的 q 行，每行输入两个正整数 l, r，代表一次询问。

输出描述：

输出 q 行，每行输出两个正整数，代表所有元素之和的最小值和最大值。

---

示例：

输入例子：

3 2
1 0 3
1 2
4 4

输出例子：

5 6
8 8

例子说明：

只有第二个元素是未知的。
第一次询问，数组最小的和是 1+1+3=5，最大的和是 1+2+3=6。
第二次询问，显然数组的元素和必然为 8。

思路：给从一个范围取值，并给出最大和最小值，必然是取此范围中的两个最值。因此我们可以分别使用范围中的两个最值来填充数组中的 0 并求和。

先对已知元素求和 sum_known

接着计数未知元素 count_unknown

与最值相乘 count_unknown * max (min)

最后与已知元素和相加 sum_known + count_unknown * max (min)

n, q = map(int, input().split())
arr = map(int, input().split())sum_known = 0
count_unknown = 0for num in arr:if num == 0:count_unknown += 1else:sum_known += numfor _ in range(q):l, r = map(int, input().split())min_sum = sum_known + count_unknown * lmax_sum = sum_known + count_unknown * rprint(min_sum, max_sum)

第二题：验证工号

假设美团的工号是由18位数字组成的，由以下规则组成：

• 前面6位代表是哪个部门
• 7-14位代表是出生日期，范围是1900.01.01-2023.12.31
• 15-17位代表是哪个组，不能是完全一样的3位数字
• 18位是一位的校验和，假设是 x ，则需要满足 (x+a1​+a2​+a3​+a4​+...+a17​) mod 8=1 ，a1​−a17​ 代表了前面的17位数字

现在需要写一份代码，判断输入的工号是否符合对应的规则。

提示：出生日期这里需要判断闰年。闰年判断的条件是能被 4 整除， 但不能被 100 整除；或能被 400 整除。

输入描述：

第一行输入一个整数 n
接下来 n 行，每行输入一个字符串，表示一个合法的部门。如果工号不属于合法部门的话，则认为这个工号不符合规则
接下来输入一个整数 m
接下来 m 行，每行输入一个字符串，表示需要验证的工号。

输出描述：

如果不满足上述任一个规则，输出 "error" ，都满足的话输出 "ok"  

---

示例1

输入例子：

2
123456
123457
1
123456202312120636

输出例子：

ok

---

示例2

输入例子：

1
123455
1
123456202312120633

输出例子：

error

例子说明：

部门号不对

---

示例3

输入例子：

1
123456
2
123456202313120633
123456202302290633

输出例子：

error
error

例子说明：

出生日期不对
2023不是闰年，没有29号

---

示例4

输入例子：

1
123456
1
123456202312120635

输出例子：

error

例子说明：

校验码不对

 思路：一道模拟题，不涉及算法，具体见代码

def is_valid_date(year, month, day):if year < 1900 or year > 2023:return Falseif month < 1 or month > 12:return Falsedays_in_month = [31, 29 if (year % 4 == 0 and year % 100 != 0) or (year % 400 == 0) else 28, 31, 30, 31, 30, 31, 31 , 30, 31, 30, 31]if day < 1 or day > days_in_month[month - 1]:return Falsereturn Truedef check_work_number(number, valid_departments):if len(number) != 18:return 'error'department = number[:6]if department not in valid_departments:return 'error'year, month, day = int(number[6: 10]), int(number[10: 12]), int(number[12: 14])if not is_valid_date(year, month, day):return 'error'group = number[14: 17]if group[0] == group[1] == group[2]:return 'error'checksum = sum(int(digit) for digit in number)if checksum % 8 != 1:return 'error'return 'ok'n = int(input())
valid_departments = []
for _ in range(n):valid_departments.append(input())m = int(input())
work_numbers = []
for _ in range(m):work_numbers.append(input())for work_number in work_numbers:print(check_work_number(work_number, valid_departments))

第三题：小美的平衡矩阵

小美拿到了一个 n ∗ n 的矩阵，其中每个元素是 0 或者 1。
小美认为一个矩形区域是完美的，当且仅当该区域内 0 的数量恰好等于 1 的数量。
现在，小美希望你回答有多少个 i ∗ i 的完美矩形区域。你需要回答 1 ≤ i ≤ n 的所有答案。

 

输入描述：

第一行输入一个正整数 n，代表矩阵大小。
接下来的 n 行，每行输入一个长度为 n 的 01 串，用来表示矩阵

输出描述：

输出 n 行，第 i 行输出 i * i 的完美矩形区域的数量。

---

示例1

输入例子：

4
1010
0101
1100
0011

输出例子：

0
7
0
1

思路：要解决这个问题，我们可以遍历所有可能的矩形区域，并检查每个区域内0和1的数量是否相等。一种方法是使用前缀和。具体来说，我们可以分别维护0和1的前缀和矩阵，这样就可以在O(1)时间内得到任意矩形区域内0和1的数量。

下面是具体的步骤：

1. 构建前缀和矩阵：分别计算并存储0和1的前缀和。对于矩阵中的每个点(i, j)，prefix_0[i][j]表示左上角(0, 0)到(i, j)形成的矩形区域内0的数量，prefix_1[i][j]同理。

2. 遍历所有可能的i*i矩形区域：对于每个可能的边长i（从1到n），遍历矩阵中所有可能的 i * i 的矩形区域。

3. 检查矩形区域是否完美：对于每个矩形区域，使用前缀和快速计算区域内0和1的数量，检查它们是否相等。

4. 计数并输出结果：对于每个边长 i，计算满足条件的 i * i 的完美矩形区域数量。

注意：此方法在牛客网上显示大部分用例超时。 

n = int(input())  # 矩阵大小
matrix = [list(map(int, input())) for _ in range(n)]  # 读取矩阵# 初始化前缀和矩阵
prefix_0 = [[0] * (n + 1) for _ in range(n + 1)]
prefix_1 = [[0] * (n + 1) for _ in range(n + 1)]
# 计算前缀和
for i in range(1, n+1):for j in range(1, n+1):prefix_0[i][j] = prefix_0[i-1][j] + prefix_0[i][j-1] - prefix_0[i-1][j-1] + (matrix[i-1][j-1] == 0)prefix_1[i][j] = prefix_1[i-1][j] + prefix_1[i][j-1] - prefix_1[i-1][j-1] + (matrix[i-1][j-1] == 1)
# 计算完美矩阵数量
for i in range(1, n+1):count = 0for x in range(i, n+1):for y in range(i, n+1):zeros = prefix_0[x][y] - prefix_0[x-i][y] - prefix_0[x][y-i] + prefix_0[x-i][y-i]ones = prefix_1[x][y] - prefix_1[x-i][y] - prefix_1[x][y-i] + prefix_1[x-i][y-i]if zeros == ones:count += 1print(count)

选择题

1. 在计算机网络中，端口号的作用是什么？

• A. 区分主机内不同进程
• B. 加密数据传输
• C. 确保数据完整性
• D. 控制数据流量

端口号的主要作用是 A. 区分主机内不同进程。

在计算机网络中，一个主机可能同时运行多个网络服务，比如Web服务器、电子邮件服务器和FTP服务器等。端口号用来标识主机上的特定进程或网络服务，使得数据包能够被正确地发送到目的地进程。每个网络服务监听在特定的端口上，当数据到达时，根据端口号就能知道该数据是为哪个服务或进程而来。

---

2. HTTPS协议通过使用哪些机制来确保通信的安全性（）

• A. 加密和身份验证
• B. 压缩和缓存
• C. 路由和负载均衡
• D. 访问控制和权限管理

HTTPS协议通过使用 A. 加密和身份验证 机制来确保通信的安全性。

HTTPS（超文本传输安全协议）是HTTP的安全版，它通过SSL/TLS协议提供数据加密、数据完整性和身份验证的功能，从而保护用户数据免遭窃听和篡改，并验证通信双方的身份。

---

3. ETag用于标识资源的唯一标识符，它可以用于（）

• A. 验证资源是否发生变化
• B. 控制缓存的过期时间
• C. 指定缓存的最大大小
• D. 加密缓存中的数据

ETag用于标识资源的唯一标识符，它可以用于 A. 验证资源是否发生变化。

ETag（实体标签）是一个HTTP响应头，用于Web浏览器缓存验证。它可以帮助浏览器了解服务器上的资源是否已被修改，从而决定是否需要重新下载资源或可以使用缓存的版本，这有助于优化网页加载时间并减少服务器负载。

---

4. 在一个单道系统中，有4个作业P、Q、R和S，执行时间分别为2小时、4小时、6小时和8小时，P和Q同时在0时到达，R和S在2小时到达，采用短作业优先算法时，平均周转时间为（）。

• A. 15小时
• B. 12小时
• C. 6小时
• D. 9小时

短作业优先（SJF）算法优先执行预计执行时间最短的作业。作业的到达和执行时间如下：

• 0时刻：P（2小时），Q（4小时）到达
• 2时刻：R（6小时），S（8小时）到达

执行顺序如下：

1. 在0时刻，P和Q到达，P的执行时间最短（2小时），所以首先执行P。
2. P执行完毕后是2时刻，此时Q、R和S都已到达。在这些中，Q的执行时间最短（4小时），接下来执行Q。
3. Q执行完毕后是6时刻，此时R和S待执行，R的执行时间最短（6小时），接下来执行R。
4. R执行完毕后是12时刻，最后执行S（8小时）。
5. S执行完毕后是20时刻。

周转时间是指从作业提交到作业完成所需的总时间。根据执行顺序，各作业的周转时间如下：

• P：2小时（从0到2）
• Q：6小时（从0到6）
• R：10小时（从2到12）
• S：18小时（从2到20）

平均周转时间 = (2 + 6 + 10 + 18) / 4 = 36 / 4 = 9小时。

---

5. 系统中现有一个任务进程在11:30到达系统，如果在14:30开始运行这个任务进程，其运行时间为3小时，现求这个任务进程的响应比为（）。

• A. 0.5
• B. 2
• C. 1
• D. 1.5

响应比是指作业的周转时间与服务时间（运行时间）的比值。公式可以表示为：

响应比 = 周转时间 / 服务时间​

周转时间是指从作业提交到作业完成的总时间，包括作业在系统中等待的时间加上作业的执行时间。

根据题目，任务进程在11:30到达系统，14:30开始运行，运行时间为3小时。所以：

• 等待时间 = 14:30 - 11:30 = 3小时
• 运行时间 = 3小时
• 周转时间 = 等待时间 + 运行时间 = 3小时 + 3小时 = 6小时

因此，响应比为：

响应比 = 6小时 / 3小时 = 2。

---

6. 在一个物流管理系统中，需要一个功能来处理不同类型的货物运输请求，如陆运、空运或海运。该系统应能够根据运输类型的不同选择不同的处理策略。哪种设计模式最合适（）

• A. 工厂方法模式
• B. 桥接模式
• C. 策略模式
• D. 适配器模式

这个场景最适合使用 C. 策略模式。

策略模式允许在运行时选择算法或行为的具体实现。在给定的问题中，根据不同的运输类型（陆运、空运、海运）选择不同的处理策略正是策略模式的典型应用场景。使用策略模式，可以定义一系列的算法（即不同的运输策略），并将每一个算法封装起来，使它们可以相互替换，这样算法的变化不会影响到使用算法的客户端。

• 工厂方法模式主要用于创建对象，特别是在创建对象时需要考虑到系统的扩展性时，而不是用于选择行为或算法。
• 桥接模式主要用于将抽象部分与实现部分分离，以便两者可以独立地变化，更多关注于不同维度的组合，而不是行为的选择。
• 适配器模式主要用于使原本因接口不兼容而不能一起工作的类可以一起工作，关注的是接口的兼容性，而非行为的选择。

---

7. 对关键码序列{9, 27, 18, 36, 45, 54, 63}进行堆排序，输出2个最大关键码后的剩余堆是（）。

• A. {9, 18, 27, 36, 45}
• B. {9, 18, 45, 27, 36}
• C. {45, 9, 18, 27, 36}
• D. {45, 36, 18, 9, 27}

剩余堆是 D. {45, 36, 18, 9, 27}。

首先，我们需要构建一个最大堆，然后交换堆顶元素（最大值）与堆的最后一个元素的位置，这样最大值就被放到了数组的最末端。之后，将剩余的元素再次调整为最大堆，继续上述操作，直至堆中剩余元素足够少，无法继续进行交换为止。

---

8. 以下哪个设计模式主要用于在不改变原始类的情况下扩展其功能（）

• A. 装饰器模式
• B. 适配器模式
• C. 工厂模式
• D. 建造者模式

A. 装饰器模式 主要用于在不改变原始类的情况下扩展其功能。

装饰器模式通过创建一个包装对象，也称为装饰器，来给原始对象动态地添加额外的功能或责任。这种模式非常有用，因为它允许在遵守开闭原则的前提下，即对扩展开放、对修改封闭，来增加对象的功能。

---

9. 设哈希表长m=10，有一堆数据元素，关键字分别为{14, 25, 36, 47, 58, 69, 80}，按照哈希函数为H(key)=key%10，如用线性探测法处理冲突，求关键字90填装的哈希表位置的序号是（）。

• A. 3
• B. 4
• C. 1
• D. 6

线性探测法处理哈希冲突时，如果发现预期的哈希位置已被占用，它会检查下一个位置，依此类推，直到找到一个空闲的位置。给定哈希函数 H(key) = key % 10，我们首先计算每个关键字的哈希位置，然后按顺序填入哈希表，处理冲突时采用线性探测法。

关键字及其哈希位置如下：

• 14 % 10 = 4
• 25 % 10 = 5
• 36 % 10 = 6
• 47 % 10 = 7
• 58 % 10 = 8
• 69 % 10 = 9
• 80 % 10 = 0

按照这些关键字填表，哈希表的填装情况为：

• 位置0：80
• 位置4：14
• 位置5：25
• 位置6：36
• 位置7：47
• 位置8：58
• 位置9：69

当关键字90被插入时，90 % 10 = 0，但位置0已经被关键字80占据，因此需要采用线性探测法向后查找空闲位置。位置1是表中下一个空闲的位置，所以关键字90将被放置在位置1。

因此，关键字90填装的哈希表位置的序号是 C. 1。

---

10. 在一颗深度为8的完全二叉树中，最少可以有多少个结点，最多可以有多少个结点？

• A. 128和255
• B. 256和512
• C. 511和1022
• D. 512和1024

在一棵深度为8的完全二叉树中：

• 最少结点数发生在除了最后一层外，所有层都完全填满，而最后一层只有1个节点的情况下。这种情况下，完全二叉树变成了一个满二叉树，加上最后一层的一个节点。满二叉树的节点总数为 2^深度 - 1，所以深度为7的满二叉树的节点数为 2^7 - 1 = 127，加上最后一层的一个节点，总数为128。因此，最少结点数是 128。

• 最多结点数发生在所有层都完全填满的情况下。完全二叉树在所有层都完全填满时，其节点总数为 2^深度 - 1。因此，深度为8的完全二叉树的节点数为 2^8 - 1 = 255。所以，最多结点数是 255。

综上所述，正确答案是 A. 128和255。

---

11. 在编译器的目标代码生成阶段，以下哪个不是优化的主要目标是（）

• A. 降低程序的功耗
• B. 减小目标代码的体积
• C. 提高目标代码的执行效率
• D. 减少程序的编译时间

在编译器的目标代码生成阶段，优化旨在改进最终生成的代码，使其在执行时更高效。然而，D. 减少程序的编译时间不是目标代码生成阶段优化的主要目标。编译时间的优化关注的是编译器的性能，而不是生成的目标代码的性能。编译时间优化旨在改进编译过程本身，使编译器能够更快地完成工作，但这通常是编译器设计者需要考虑的问题，而不是目标代码优化的直接目标。

---

12. 若入栈序列为1, 3, 5, 2, 4, 6，且进栈和出栈可以穿插进行，则不可能的输出序列为（）。

• A. 1, 3, 5, 2, 4, 6
• B. 1, 3, 6, 2, 5, 4
• C. 1, 3, 5, 4, 2, 6
• D. 1, 3, 5, 4, 6, 2

B. 1, 3, 6, 2, 5, 4 不可能，手动模拟一下即可。

---

13. 在用KMP算法进行模式匹配时，若是指向模式串"mnopmn"的指针在指到第5个字符"m"时发生失配，则指针回溯的位置为（）。

注：字符串中字符从字符数据1号位开始存储，也即从1开始编号。

• A. 1
• B. 2
• C. 3
• D. 4

KMP算法中的关键是next数组（也被称为部分匹配表），该数组用于在发生失配时决定模式串中指针应该回溯到的位置。对于模式串"mnopmn"，我们首先需要计算其next数组。

模式串："mnopmn"

• m (1号位): next[1] = 0，因为m之前没有更短的相同前缀和后缀。
• n (2号位): next[2] = 0，因为n之前没有更短的相同前缀和后缀。
• o (3号位): next[3] = 0，因为o之前没有更短的相同前缀和后缀。
• p (4号位): next[4] = 0，因为p之前没有更短的相同前缀和后缀。
• m (5号位): next[5] = 1，因为在m之前，有一个字符m可以作为相同的前缀和后缀。
• n (6号位): next[6] = 2，因为在n之前，有"mn"可以作为相同的前缀和后缀。

根据这个分析，当指向模式串的指针在指到第5个字符"m"时发生失配，根据next数组，指针应该回溯到next[5] = 1的位置。

因此，正确答案是 A. 1。

---

14. 代码需要经过一系列步骤编译成机器指令，根据完成任务不同，可以将编译器的组成部分划分为前端与后端。下列选项是编译器前端在编译源程序时编译的顺序，正确的是（）

• A. 词法分析器->语法分析器->中间代码生成器
• B. 语法分析器->词法分析器->中间代码生成器
• C. 词法分析器->中间代码生成器->语法分析器
• D. 语法分析器->中间代码生成器->词法分析器

编译器前端的工作主要包括词法分析、语法分析和中间代码生成等步骤。正确的编译顺序是：

1. 词法分析器：将源代码的字符序列转换成一系列的记号（Token）。这个过程涉及到识别变量名、关键字、操作符等。

2. 语法分析器：根据词法分析器输出的记号序列和语言的语法规则，构建出一棵抽象语法树（AST）。这一步骤检查代码的语法结构是否正确。

3. 中间代码生成器：将抽象语法树转换成一种中间表示（IR）形式的代码。这种中间代码是一种独立于具体机器语言的高级表示，用于进一步的优化和转换。

因此，正确的选项是 A. 词法分析器->语法分析器->中间代码生成器。

---

15. 不同的数据存放区存放的数据和对应的管理方法是不同的。对于某些数据，如果在编译期间就可以确定数据对象的大小和数据对象的数目，在编译期间为数据对象分配存储空间，这些数据对应的存储分配策略是（）

• A. 栈式存储分配
• B. 堆式存储分配
• C. 动态存储分配
• D. 静态存储分配

存储分配策略是 D. 静态存储分配。

静态存储分配是指编译时就确定了每个数据对象的存储空间大小和生命周期的存储方式。这些数据在程序的整个运行期间都存在，不会被创建和销毁。常见的静态存储包括全局变量和静态变量。

---

16.

某硬盘有240个磁道（最外侧磁道号为0），磁道访问请求序列为30, 60, 90, 120, 190, 150, 220，当前磁头位于第180号磁道并从外侧向内侧移动。按照SCAN调度（电梯调度）方法处理完上述请求后，磁头移过的磁道数是（）。

• A. 280
• B. 200
• C. 230
• D. 250

在SCAN调度（电梯调度）方法中，磁头移动的方式类似于电梯运行：当它移动到一个方向的最边缘时，如果没有更远的请求，就会改变方向。根据题目，当前磁头位于第180号磁道并从外侧向内侧移动。

给定的磁道访问请求序列是30, 60, 90, 120, 190, 150, 220，我们首先将这些请求按照磁道号排序，并根据当前的磁头位置和移动方向处理请求。

排序后的请求序列为30, 60, 90, 120, 150, 190, 220。

从180号磁道开始，向内侧移动，磁头首先访问190和220。到达220后，由于已经是内侧最远的请求，磁头将改变方向，向外侧移动，并按顺序访问150, 120, 90, 60, 30。

计算磁头移过的磁道数：

• 从180到220 = 40磁道
• 从220回到30 = 220 - 30 = 190磁道

所以，磁头移过的磁道总数是40 + 190 = 230。

因此，正确答案是 C. 230。

---

17. 下列选项中只要其中一个表中存在匹配，则返回行的SQL JOIN的 类型是（）。

• A. INNER JOIN
• B. LEFT JOIN
• C. RIGHT JOIN
• D. FULL JOIN

当你想从两个表中返回匹配的行，并且当其中一个表中存在匹配时也返回行，即使另一个表中没有匹配，你应该使用 D. FULL JOIN。

FULL JOIN 返回左表和右表中的所有记录。当左表（table1）和右表（table2）中的行在 JOIN 条件上匹配时，它将返回这些匹配的行。如果在一个表中没有匹配的行，则结果集中相关表的部分将包含 NULL 值。这意味着它会返回左表的所有记录（与 LEFT JOIN 相同）和右表的所有记录（与 RIGHT JOIN 相同），以及这两个表的交集（与 INNER JOIN 相同）。