【秋招笔试】10.16花子秋招(已改编)-海外留学生版
🍭 大家好这里是 春秋招笔试突围,一起备战大厂笔试
💻 ACM金牌团队🏅️ | 多次AK大厂笔试 | 大厂实习经历
✨ 本系列打算持续跟新
春秋招笔试题
👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸
✨ 笔试合集传送们 -> 🧷春秋招笔试合集
🍒 本专栏已收集
140+
套笔试题,笔试真题
会在第一时间跟新🍄 题面描述等均已改编,如果和你笔试题看到的题面描述不一样请理解,做法和题目本质基本不变。
🍹 感谢各位朋友们的订阅,你们的支持是我们创作的最大动力 💞
🌈 花子(海外留学生版)秋招笔试,来啦!!!
🧸 强烈建议国内的宝子也刷一刷
海外版本
的,以下是一些数据
- 海外
0924
第一题 国内0927
第二题- 海外
0924
第二题 国内1012
第一题- 海外
0924
第三题 国内1009
第三题- 海外
1009
第三题 国内1016
第三题无须多言,冲 🐛🐛🐛 就完事了!!!!
1️⃣ 比较基础的大根堆的应用
2️⃣ 直接暴力枚举/双指针+滑动窗口
3️⃣ 思维+贪心+分类讨论
🎫 01.智能家居定时系统评测链接🔗
题目描述
K小姐最近购买了一套智能家居系统。该系统有一个定时控制功能,可以设置多个定时任务来控制各种家电设备。系统的特点如下:
- 系统精度为1分钟,最多可以设置 个定时任务。
- 每个任务包含一个执行时间 (整数,表示从当前时刻起多少分钟后执行)。
- 如果多个任务在同一时刻执行,按照添加顺序依次执行。
- 当系统中任务数少于 个时,可以直接添加新任务。
- 当系统中已有 个任务时,如果新任务执行时间晚于系统中最晚的任务,则丢弃新任务;否则,删除系统中最晚的任务,添加新任务。
现在K小姐想要一次性添加 个定时任务。请你帮她计算出,最终系统中最晚执行的任务是第几个添加的。
输入格式
第一行包含一个正整数 ,表示系统最多可以设置的任务数。
第二行包含一个正整数 ,表示K小姐想要添加的任务数。
第三行包含 个正整数,表示每个任务的执行时间 。
输出格式
输出一个整数,表示最终系统中最晚执行的任务是第几个添加的(编号从0开始)。如果有多个任务同时是最晚执行的,输出编号最大的那个。
样例输入1
2
12
1 2 3 4 6 19 20 21 22 23 25 1
样例输出1
11
样例输入2
1
2
10 2
样例输出2
1
样例输入3
20
5
1 2 3 4 5
样例输出3
4
样例解释
样例1 | 系统最多可行时间也为1)。这两个任务同时是最晚执行的,所以输出编号较大的那个,即11。 |
样例2 | 系统最多可以设置1个任务。第一个任务(执行时间为10)被添加后,第二个任务(执行时间为2)会替换掉第一个任务。所以最终系统中只有第二个任务,输出1。 |
样例3 | 系统最多可以设置20个任务,而只添加了5个任务,所以所有任务都被保留。最晚执行的是第5个任务(执行时间为5),所以输出4。 |
数据范围
题解
堆模拟
这道题目本质上是在模拟一个固定容量的优先队列。维护一个大小为 的优先队列,队列中的元素按照执行时间从早到晚排序。同时还需要记录每个任务的添加顺序。
解题思路如下:
-
创建一个优先队列,用于存储任务。队列中的每个元素是一个二元组 ,其中 是执行时间, 是添加顺序。
-
遍历所有要添加的任务:
- 如果队列大小小于 ,直接将任务加入队列。
- 如果队列已满:
- 比较新任务的执行时间和队列中最晚任务的执行时间。
- 如果新任务执行时间不晚于队列中最晚任务,则移除队列中最晚的任务,添加新任务。
- 否则,丢弃新任务。
-
遍历结束后,队列中执行时间最晚的任务就是我们要找的。如果有多个任务执行时间相同且最晚,我们需要返回添加顺序最大的那个。
时间复杂度分析:
- 对于每个任务,我们需要进行一次优先队列的操作(插入或删除),时间复杂度为 。
- 总共有 个任务,所以总的时间复杂度为 。
考虑到 且 ,这个时间复杂度是可以接受的。
参考代码
- Python
# 使用优先队列解决定时任务问题
from heapq import heappush, heappop, heapreplace
def solve():
# 读取输入
n = int(input()) # 系统容量
m = int(input()) # 任务数量
tasks = list(map(int, input().split())) # 任务执行时间列表
# 初始化优先队列
q = []
# 处理每个任务
for i, val in enumerate(tasks):
if len(q) < n:
# 队列未满,直接添加任务
heappush(q, (-val, -i))
else:
# 队列已满,判断是否需要替换
if -q[0][0] >= val:
# 当前任务执行时间不晚于队列中最晚的任务
heapreplace(q, (-val, -i))
# 输出最晚任务的索引
print(-q[0][1])
if __name__ == "__main__":
solve()
- Java
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 读取输入
int n = sc.nextInt(); // 系统容量
int m = sc.nextInt(); // 任务数量
// 创建优先队列,按照时间降序排列,时间相同按索引降序
PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> {
if (a[0] != b[0]) {
return Long.compare(a[0], b[0]);
}
return Long.compare(a[1], b[1]);
});
// 处理每个任务
for (int i = 0; i < m; i++) {
long val = sc.nextLong();
if (pq.size() < n) {
// 队列未满,直接添加任务
pq.offer(new long[]{-val, -i});
} else {
// 队列已满,判断是否需要替换
if (-pq.peek()[0] >= val) {
pq.poll();
pq.offer(new long[]{-val, -i});
}
}
}
// 输出最晚任务的索引
System.out.println(-pq.peek()[1]);
}
}
- Cpp
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
// 读取输入
int n, m;
cin >> n >> m;
// 创建优先队列,pair的first存储时间,second存储索引
priority_queue<pll, vector<pll>, greater<pll>> pq;
// 处理每个任务
for (int i = 0; i < m; i++) {
ll val;
cin >> val;
if (pq.size() < n) {
// 队列未满,直接添加任务
pq.push({-val, -i});
} else {
// 队列已满,判断是否需要替换
if (-pq.top().first >= val) {
pq.pop();
pq.push({-val, -i});
}
}
}
// 输出最晚任务的索引
cout << -pq.top().second << endl;
return 0;
}
🦸♂️ 02.智能系统优化 评测链接🔗
问题描述
LYA 公司正在开发一款智能家居系统。该系统由多个智能设备组成,每个设备都可以在两种模式下运行:高性能模式和节能模式。在高性能模式下,设备的响应速度更快,但能耗较高;在节能模式下,设备的响应速度较慢,但能耗较低。
系统中有两种处理单元:主处理器和辅助处理器。主处理器的处理速度是辅助处理器的 6 倍,但能耗也相应更高。为了优化系统性能和能耗,LYA 公司需要合理分配设备的运行模式。
系统优化的目标是:最小化整体响应时间,同时平衡两种处理器的负载。整体响应时间定义为:max(主处理器总处理时间,辅助处理器总处理时间)。
为简化问题,我们假设:
- 每个设备只能在一种模式下运行。
- 分配给辅助处理器的设备必须是连续的。
输入格式
第一行输入一个整数 ,表示智能设备的数量。
第二行输入 个整数,表示每个设备在主处理器上的处理时间 。
输出格式
输出一个整数,表示系统的最小整体响应时间。
样例输入1
9
1 2 3 4 5 6 7 8 9
样例输出1
39
样例输入2
9
3 2 17 8 3 5 4 18 15
样例输出2
66
样例解释
样例1 | 将第 6 个设备(处理时间为 6)分配给辅助处理器,其处理时间变为 。其余设备分配给主处理器,总处理时间为 。整体响应时间为 max(39, 36) = 39。 |
样例2 | 将第 4 和第 5 个设备(处理时间分别为 8 和 3)分配给辅助处理器,总处理时间为 。其余设备分配给主处理器,总处理时间为 。整体响应时间为 max(64, 66) = 66。 |
数据范围
题解
双指针
这道题目本质上是一个最大子数组问题的变种。需要找到一个连续的子数组,使得将这个子数组中的元素分配给辅助处理器后,能够最小化整体响应时间。
关键思路是使用滑动窗口算法。维护一个窗口,表示分配给辅助处理器的设备。窗口的和乘以 6 就是辅助处理器的处理时间,窗口外的和就是主处理器的处理时间。
算法步骤如下:
- 初始化左右指针 left 和 right,都指向数组开始。
- 计算整个数组的和 total_sum,这是所有设备都分配给主处理器的情况。
- 使用滑动窗口,不断移动右指针:
- 如果当前窗口和的 6 倍小于 total_sum 的 1/7,继续扩大窗口。
- 否则,开始移动左指针,缩小窗口。
- 在这个过程中,不断更新最小的整体响应时间。
这个算法的时间复杂度是 O(n),因为每个元素最多被访问两次(一次被右指针,一次被左指针)。空间复杂度是 O(1),只使用了常数额外空间。
对于给定的数据范围(),这个线性时间复杂度的算法是完全可以接受的,能够在较短时间内得出结果。
参考代码
- Python
# 导入系统模块
import sys
# 定义输入函数
input = lambda: sys.stdin.readline().strip()
def solve(times, total):
"""
计算最优执行时间
Args:
times: 每个算子在矩阵计算单元的执行时间列表
total: 所有算子在矩阵计算单元的总执行时间
Returns:
最小的总体执行时间
"""
threshold = total / 7
min_time = min(total, 6 * total)
left = window_sum = 0
for right in range(len(times)):
window_sum += times[right]
while left <= right and window_sum > threshold:
vector_time = 6 * window_sum
matrix_time = total - window_sum
min_time = min(min_time, max(matrix_ti
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
这里收集了超全的互联网春秋招笔试题,欢迎大家的订阅,会持续跟新的