【秋招笔试】10.23花子秋招(已改编)-海外留学生版
🍭 大家好这里是 春秋招笔试突围,一起备战大厂笔试
💻 ACM金牌团队🏅️ | 多次AK大厂笔试 | 大厂实习经历
✨ 本系列打算持续跟新
春秋招笔试题
👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸
✨ 笔试合集传送们 -> 🧷春秋招笔试合集
🍒 本专栏已收集
140+
套笔试题,笔试真题
会在第一时间跟新🍄 题面描述等均已改编,如果和你笔试题看到的题面描述不一样请理解,做法和题目本质基本不变。
🍹 感谢各位朋友们的订阅,你们的支持是我们创作的最大动力 💞
🌈 花子(海外留学生版)秋招笔试,来啦!!!
🧸 强烈建议国内的宝子也刷一刷
海外版本
的,以下是一些数据
- 海外
0924
第一题 国内0927
第二题- 海外
0924
第二题 国内1012
第一题- 海外
0924
第三题 国内1009
第三题- 海外
1009
第三题 国内1016
第三题无须多言,冲 🐛🐛🐛 就完事了!!!!
本次的难度相对23号国内笔的相对较低
1️⃣ 模拟/数据结构+二分
2️⃣ DFS模拟即可
3️⃣ 贪心+优先队列
📦 01.集装箱智能堆放 评测链接🔗
问题描述
LYA 港口的智能物流系统需要对一批集装箱进行堆放优化。每个集装箱都有一个承重等级,决定了它上面最多可以堆放多少个集装箱。承重等级为 的集装箱最多可以承载 个集装箱。所有集装箱的底面积都是 个单位面积。现在需要设计一个堆放方案,使得这批集装箱占用的地面面积最小。
输入格式
输入为一行整数,数字之间用空格隔开,表示每个集装箱的承重等级。
输出格式
输出一个整数,表示最小占地面积。
样例输入1
0 2 1
样例输出1
1
样例输入2
1 2 1 2
样例输出2
2
样例解释
样例1 | 输入:0 2 1 输出: 1 |
可以将承重等级为2的集装箱放在最下面,上面放承重等级为1的集装箱,最上面放承重等级为0的集装箱,只需要占用1个单位面积。 |
样例2 | 输入:1 2 1 2 输出: 2 |
有多种堆放方式,但最少需要占用2个单位面积。可以是: 方案1:第一堆(2,1,1),第二堆(2) 方案2:第一堆(2,2,1),第二堆(1) 方案3:第一堆(2,1,2),第二堆(1) |
数据范围
- (承重等级)
- (集装箱数量)
题解
贪心/模拟+二分
这道题的核心思路是贪心算法。需要尽可能地将集装箱堆得更高,这样才能减少占地面积。
关键思路:
- 首先将集装箱按承重等级排序
- 使用二分查找找到最适合放置的堆,堆按照从大到小排序
- 如果找不到合适的堆,就新开一个堆
时间复杂度分析:
- 排序需要
- 每个集装箱的放置需要二分查找,复杂度
- 总体复杂度为
参考代码
- Python
def solve():
# 读取输入
a = list(map(int, input().split()))
# 按承重等级排序
a.sort()
# 存储每堆的高度
q = []
for i in a:
found = False
# 二分查找合适的堆
l, r = 0, len(q) - 1
while l < r:
mid = (l + r) >> 1
if q[mid] <= i:
r = mid
else:
l = mid + 1
# 如果没有合适的堆或当前堆不满足条件
if not q or q[l] > i:
q.append(1)
else:
q[l] += 1
print(len(q))
if __name__ == "__main__":
solve()
- Java
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 读取输入
List<Integer> a = new ArrayList<>();
while (sc.hasNextInt()) {
a.add(sc.nextInt());
}
// 排序
Collections.sort(a);
List<Integer> q = new ArrayList<>();
for (int i : a) {
int l = 0, r = q.size() - 1;
// 二分查找
while (l < r) {
int mid = (l + r) >> 1;
if (q.get(mid) <= i) r = mid;
else l = mid + 1;
}
if (q.isEmpty() || q.get(l) > i) {
q.add(1);
} else {
q.set(l, q.get(l) + 1);
}
}
System.out.println(q.size());
}
}
- Cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
// 存储集装箱承重等级
vector<int> a;
int x;
// 读取输入
while (cin >> x) {
a.push_back(x);
}
// 排序
sort(a.begin(), a.end());
// 存储每堆的高度
vector<int> q;
for (int i : a) {
int l = 0, r = q.size() - 1;
// 二分查找合适的堆
while (l < r) {
int mid = l + r >> 1;
if (q[mid] <= i) r = mid;
else l = mid + 1;
}
// 创建新堆或在现有堆上添加
if (q.empty() || q[l] > i) {
q.push_back(1);
} else {
q[l]++;
}
}
cout << q.size() << "\n";
return 0;
}
📚 02.公司调用链分析 评测链接🔗
问题描述
LYA 公司的技术团队正在开发一个性能分析工具,用于分析软件运行过程中的函数调用关系。该工具通过采样分析得到了一棵调用树,每个节点代表一个函数调用链,并记录了该调用链被采样到的次数。现在需要计算每个节点包含其所有子调用链的总采样次数。
调用链是指从主函数到某个函数的调用路径。例如,如果函数 调用了函数 ,我们记作 ->。如果函数 又调用了函数 ,形成 ->->,则称后者是 -> 的子调用链。
输入格式
第一行为一个整数 ,表示调用树的节点总数。
第二行包含 个整数,表示按层序遍历得到的树结构。其中正整数表示节点的采样次数, 用于分隔每个节点的子节点序列。第 个 和第 个 之间的节点为第 个节点的子节点。
输出格式
输出一行 个整数,表示更新后的调用树。格式与输入保持一致。
样例输入1
6
5 -1 2 3 8 -1 -1 1 7 -1 -1 -1
样例输出1
26 -1 2 11 8 -1 -1 1 7 -1 -1 -1
样例解释
样例1 | 输入描述了一棵有6个节点的调用树。根节点采样次数为5,有三个子节点,采样次数分别为2、3和8。第三个节点(采样次数为3)有两个子节点,采样次数分别为1和7。计算包含子节点的总采样次数后,根节点的值更新为26(5+2+11+8),第三个节点更新为11(3+1+7),其他节点值保持不变。 |
数据范围
- 采样次数
题解
DFS模拟
这道题本质上是在处理一棵树的后序遍历问题。对于每个节点,需要将其子树中所有节点的采样次数累加到该节点上。
关键点在于如何从输入格式构建树结构。输入使用了层序遍历加分隔符的方式,通过 来标记每个节点的子节点序列的边界。可以:
- 用一个计数器记录当前处理到第几个节点
- 遇到正数时存储节点值,并根据分隔符确定父子关系
- 建图后使用DFS进行后序遍历,计算每个节点包含子树的总和
时间复杂度为 ,空间复杂度为 。对于给定的数据范围()完全可以接受。
参考代码
- Python
def solve():
n = int(input()) # 读取节点数
arr = list(map(int, input().split())) # 读取树的序列化输入
# 建图
g = [[] for _ in range(n + 1)] # 邻接表存储树
cnt = [0] * (n + 1) # 存储每个节点的采样次数
p = 1 # 当前父节点编号
c = 1 # 当前处理的节点编号
# 解析输入,构建树结构
for i in range(2 * n):
if arr[i] < 0:
p += 1
else:
cnt[c] = arr[i]
if c > 1:
g[p-1].append(c)
g[c].append(p-1)
c += 1
# DFS计算每个节点包含子树的总采样次数
def dfs(u, fa):
for v in g[u]:
if v != fa:
dfs(v, u)
cnt[u] += cnt[v]
dfs(1, -1) # 从根节点开始DFS
# 按原格式输出结果
vis = [False] * (n + 1)
vis[1] = True
print(cnt[1], -1, end=' ')
for i in range(1, n + 1):
if len(g[i]) > 1:
for v in g[i]:
if not vis[v]:
vis[v] = True
print(cnt[v], end=' ')
if i
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
这里收集了超全的互联网春秋招笔试题,欢迎大家的订阅,会持续跟新的