【秋招笔试】10.23花子秋招(已改编)-三语言题解
🍭 大家好这里是 春秋招笔试突围,一起备战大厂笔试
💻 ACM金牌团队🏅️ | 多次AK大厂笔试 | 大厂实习经历
✨ 本系列打算持续跟新
春秋招笔试题
👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸
✨ 笔试合集传送们 -> 🧷春秋招笔试合集
🍒 本专栏已收集
140+
套笔试题,笔试真题
会在第一时间跟新🍄 题面描述等均已改编,如果和你笔试题看到的题面描述不一样请理解,做法和题目本质基本不变。
🍹 感谢各位朋友们的订阅,你们的支持是我们创作的最大动力 💞
🌈 花子秋招笔试,来啦!!!
🧸 不出所料,花子那
ex
的模拟题又回来了,1️⃣ DFS模拟
2️⃣ 树形DP,比较经典的题了,根据力扣改编
3️⃣ 字符串模拟
🟰 01.函数调用栈分析 评测链接🔗
问题描述
在软件开发中,函数调用是一个常见的操作。每个函数在执行时都需要占用一定的栈空间,如果函数调用链过长或单个函数占用栈空间过大,可能会导致栈溢出。现在需要你开发一个工具来分析函数调用链中是否存在栈溢出风险。
输入格式
第一行:一个整数 ,表示系统中的函数数量。
第二行到第 行:每行包含一个大写字母(函数名)和一个正整数(函数栈大小),以空格分隔。
第 行:一个整数 ,表示函数调用关系的数量。
接下来 行:每行包含多个大写字母,第一个字母表示调用方函数,后续字母表示被调用的函数(按调用顺序排列)。
最后一行:一个整数 ,表示系统配置的最大栈空间。
输出格式
输出一行,包含三个部分,以空格分隔:
- 是否发生栈溢出(true/false)
- 导致栈溢出的调用路径或最大栈消耗的调用路径(用"-"连接)
- 对应的栈空间大小
样例输入1
6
A 20
B 10
C 5
D 15
E 50
F 60
3
A B C
B D
C E F
70
样例输出1
true A-C-E 75
样例输入2
6
A 20
B 10
C 5
D 15
E 50
F 60
3
A B C
B D
C E F
100
样例输出2
false A-C-F 85
样例解释
样例1 | 从入口函数 A 开始,当执行到 A-C-E 调用链时,总栈空间为75(A:20 + C:5 + E:50),超过系统配置的最大栈空间70,触发栈溢出。 |
样例2 | 系统最大栈空间为100,所有调用链都能正常执行。其中 A-C-F 调用链消耗最大栈空间85(A:20 + C:5 + F:60)。 |
数据范围
- (函数数量)
- 函数栈大小
- (调用关系数量)
- (系统最大栈空间)
题解
这道题本质上是一个函数调用栈分析问题,需要通过DFS遍历所有可能的调用路径来找出最大栈消耗或栈溢出情况。
-
数据结构设计
- 使用数组存储每个函数的栈大小,函数名可以映射为下标(A->0, B->1等)
- 使用邻接表存储调用关系,便于遍历每个函数的所有被调用函数
-
核心算法
- 从入口函数开始进行DFS遍历
- 维护当前调用路径和累计栈大小
- 检查每个调用点是否发生栈溢出
- 记录最大栈消耗路径
-
关键点
- 需要正确处理回溯,保证路径和栈大小的计算准确
- 一旦发现栈溢出就停止继续搜索
- 路径格式化为指定的"A-B-C"形式
复杂度分析
- 时间复杂度:,其中 是函数数量, 是调用关系数量
- 空间复杂度:,主要是递归栈的开销和路径存储
参考代码
- Cpp
#include <bits/stdc++.h>
using namespace std;
// 路径格式化函数
string get_path_string(const vector<char> &path) {
string s;
for(int i = 0; i < path.size(); ++i) {
if(i > 0) s += "-";
s += path[i];
}
return s;
}
// DFS函数
void dfs(char curr, int curr_stack, vector<char> &path,
bool &overflow, string &overflow_path, int &overflow_size,
int &max_stack, string &max_path, int K,
vector<char> graph[], int stack_size[]) {
// 已发生溢出则直接返回
if(overflow) return;
// 更新当前状态
curr_stack += stack_size[curr - 'A'];
path.push_back(curr);
// 检查溢出
if(curr_stack > K) {
overflow = true;
overflow_path = get_path_string(path);
overflow_size = curr_stack;
path.pop_back();
return;
}
// 更新最大栈使用
if(curr_stack > max_stack) {
max_stack = curr_stack;
max_path = get_path_string(path);
}
// 遍历所有被调用函数
for(char next : graph[curr - 'A']) {
dfs(next, curr_stack, path,
overflow, overflow_path, overflow_size,
max_stack, max_path, K,
graph, stack_size);
if(overflow) return;
}
path.pop_back();
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
cin >> N;
// 读取函数栈大小
int stack_size[26] = {0};
for(int i = 0; i < N; ++i) {
char func;
int size;
cin >> func >> size;
stack_size[func - 'A'] = size;
}
// 读取调用关系
int M;
cin >> M;
vector<char> graph[26];
char start = 'A';
bool first = true;
cin.ignore();
for(int i = 0; i < M; ++i) {
string line;
getline(cin, line);
if(line.empty()) {
--i;
continue;
}
stringstream ss(line);
char caller;
ss >> caller;
if(first) {
start = caller;
first = false;
}
char callee;
while(ss >> callee) {
graph[caller - 'A'].push_back(callee);
}
}
int K;
cin >> K;
// DFS遍历
bool overflow = false;
string overflow_path, max_path;
int overflow_size = 0, max_stack = 0;
vector<char> path;
dfs(start, 0, path,
overflow, overflow_path, overflow_size,
max_stack, max_path, K,
graph, stack_size);
// 输出结果
if(overflow) {
cout << "true " << overflow_path << " " << overflow_size << "\n";
} else {
cout << "false " << max_path << " " << max_stack << "\n";
}
return 0;
}
- Python
def get_path_string(path):
return "-".join(path)
def dfs(curr, curr_stack, path, K, graph, stack_size, result):
# 已发生溢出则返回
if result['overflow']:
return
# 更新当前状态
curr_stack += stack_size[curr]
path.append(curr)
# 检查溢出
if curr_stack > K:
result['overflow'] = True
result['path'] = get_path_string(path)
result['size'] = curr_stack
path.pop()
return
# 更新最大栈使用
if curr_stack > result['size']:
result['size'] = curr_stack
result['path'] = get_path_string(path)
# 遍历被调用函数
if curr in graph:
for next_func in graph[curr]:
dfs(next_func, curr_stack, path, K, graph, stack_size, result)
if result['overflow']:
return
path.pop()
def solve():
# 读取输入
N = int(input())
# 读取函数栈大小
stack_size = {}
for _ in range(N):
func, size = input().split()
stack_size[func] = int(size)
# 读取调用关系
M = int(input())
graph = {}
start_func = None
for _ in range(M):
line = input().strip()
if not line:
continue
funcs = line.split()
caller = funcs[0]
if start_func is None:
start_func = caller
if caller not in graph:
graph[caller] = []
graph[caller].extend(funcs[1:])
K = int(input())
# DFS遍历
result = {
'overflow': False,
'path': '',
'size': 0
}
dfs(start_func, 0, [], K, graph, stack_size, result)
# 输出结果
print(str(result['overflow']).lower(), result['path'], result['size'])
if __name__ == "__main__":
solve()
- Java
import java.util.*;
public class Main {
static class Result {
boolean overflow = false;
String path = "";
int size = 0;
}
// 路径格式化
static String getPathString(List<Character> path) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < path.size(); i++) {
if (i > 0) sb.append("-");
sb.append(path.get(i));
}
return sb.toString();
}
// DFS遍历
static void dfs(char curr, int currStack, List<Character> path,
Result result, int K,
Map<Character, List<Character>> graph,
Map<Character, Integer> stackSize) {
if (result.overflow) return;
currStack += stackSize.get(curr);
path.add(curr);
if (currStack > K) {
result.overflow = true;
result.path = getPathString(path);
result.size = currStack;
path.remove(path.size() - 1);
return;
}
if (currStack > result.size) {
result.size = currStack;
result.path = getPathString(path);
}
if (graph.containsKey(curr)) {
for (char next : graph.get(curr)) {
dfs(next, currStack, path, result, K, graph, stackSize);
if (result.overflow) return;
}
}
path.remove(path.size() - 1);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 读取函数数量
int N = sc.nextInt();
// 读取函数栈大小
Map<Character, Integer> stackSize = new HashMap<>();
for (int i = 0; i < N; i++) {
char func = sc.next().charAt(0);
int size = sc.nextInt();
stackSize.put(func, size);
}
// 读取调用关系
int M = sc.nextInt();
sc.nextLine();
Map<Character, List<Character>> graph = new HashMap<>();
Character startFunc = null;
for (int i = 0; i < M; i++) {
String line = sc.nextLine().trim();
if (line.isEmpty()) {
i--;
continue;
}
String[] funcs = line.split(" ");
char caller = funcs[0].charAt(0);
if (startFunc == null) {
startFunc = caller;
}
graph.putIfAbsent(caller, new ArrayList<>());
for (int j = 1; j < funcs.length; j++) {
graph.get(caller).add(funcs[j].charAt(0));
}
}
int K = sc.nextInt();
// DFS遍历
Result result = new Result();
dfs(startFunc, 0, new ArrayList<>(), result, K, graph, stackSize);
// 输出结果
System.out.println(result.overflow + " " + result.path + " " + result.size);
}
}
⛽️ 02.基站建设 评测链接🔗
问题描述
在一个山区,村落呈二叉树状分布。为了让所有村民都能享受到通信服务,需要在一些村落建设基站。每个基站能覆盖它所在的村落以及与之相邻的村落(包括父节点和子节点)。请计算最少需要建设多少个基站,才能使所有村落都能接收到信号。
输入格式
输入一行数据,使用完全二叉树的数组表示方式,从左到右、从上到下依次给出每个位置是否存在村落,用空格分隔。其中 表示该位置存在村落, 表示该位置不存在村落。
输出格式
输出一个整数,表示最少需要建设的基站数量。
样例输入1
1 1 1 1 0 1 1
样例输出1
2
样例输入2
1 1 0 1 0 0 0
样例输出2
1
样例解释
样例1 | 如图所示,最少需要2个基站才能覆盖所有村落。可以在第2层的左节点和第3层的右节点建设基站。 |
样例2 | 如图所示,只需要在第2层的左节点建设1个基站即可覆盖所有存在的村落。 |
数据范围
- 节点总数
- 输入数据中只包含 和
题解
树形DP
力扣原题的改编:968. 监控二叉树
这是一个典型的最小支配集问题。在二叉树结构中,我们需要选择最少的节点,使得每个存在的村落都能被覆盖。
关键思路是使用动态规划。对于每个节点,我们可以定义三种状态:
- 该节点放置基站
- 该节点被父节点的基站覆盖
- 该节点被子节点的基站覆盖
可以自底向上进行状态转移。对于每个节点:
- 如果该节点不存在(值为0),则不需要考虑覆盖
- 如果该节点存在,则需要考虑三种状态的最优解
时间复杂度为 ,其中 为节点总数。这个复杂度对于给定的数据范围(最大8191个节点)来说是完全可以接受
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
这里收集了超全的互联网春秋招笔试题,欢迎大家的订阅,会持续跟新的