10-24 17:06 北京理工大学算法工程师发布于江苏

关注

【秋招笔试】10.23花子秋招(已改编)-三语言题解

🍭 大家好这里是 春秋招笔试突围，一起备战大厂笔试

💻 ACM金牌团队🏅️ | 多次AK大厂笔试｜大厂实习经历

✨ 本系列打算持续跟新 春秋招笔试题

👏 感谢大家的订阅➕ 和喜欢💗 和手里的小花花🌸

✨ 笔试合集传送们 -> 🧷春秋招笔试合集

🍒 本专栏已收集 140+ 套笔试题，笔试真题 会在第一时间跟新

🍄 题面描述等均已改编，如果和你笔试题看到的题面描述不一样请理解，做法和题目本质基本不变。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力 💞

alt

🌈 花子秋招笔试，来啦！！！

🧸 不出所料，花子那 ex 的模拟题又回来了，

1️⃣ DFS模拟

2️⃣ 树形DP，比较经典的题了，根据力扣改编

3️⃣ 字符串模拟

🟰 01.函数调用栈分析评测链接🔗

问题描述

在软件开发中，函数调用是一个常见的操作。每个函数在执行时都需要占用一定的栈空间，如果函数调用链过长或单个函数占用栈空间过大，可能会导致栈溢出。现在需要你开发一个工具来分析函数调用链中是否存在栈溢出风险。

输入格式

第一行：一个整数 $N$ ，表示系统中的函数数量。

第二行到第 $N+1$ 行：每行包含一个大写字母（函数名）和一个正整数（函数栈大小），以空格分隔。

第 $N+2$ 行：一个整数 $M$ ，表示函数调用关系的数量。

接下来 $M$ 行：每行包含多个大写字母，第一个字母表示调用方函数，后续字母表示被调用的函数（按调用顺序排列）。

最后一行：一个整数 $K$ ，表示系统配置的最大栈空间。

输出格式

输出一行，包含三个部分，以空格分隔：

是否发生栈溢出（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）。

数据范围

$1 \leq N \leq 26$ （函数数量）
$1 \leq$ 函数栈大小 $\leq 1000$
$1 \leq M \leq 100$ （调用关系数量）
$1 \leq K \leq 10000$ （系统最大栈空间）

题解

这道题本质上是一个函数调用栈分析问题，需要通过DFS遍历所有可能的调用路径来找出最大栈消耗或栈溢出情况。

数据结构设计
- 使用数组存储每个函数的栈大小，函数名可以映射为下标(A->0, B->1等)
- 使用邻接表存储调用关系，便于遍历每个函数的所有被调用函数
核心算法
- 从入口函数开始进行DFS遍历
- 维护当前调用路径和累计栈大小
- 检查每个调用点是否发生栈溢出
- 记录最大栈消耗路径
关键点
- 需要正确处理回溯，保证路径和栈大小的计算准确
- 一旦发现栈溢出就停止继续搜索
- 路径格式化为指定的"A-B-C"形式

复杂度分析

时间复杂度： $O(V + E)$ ，其中 $V$ 是函数数量， $E$ 是调用关系数量
空间复杂度： $O(V)$ ，主要是递归栈的开销和路径存储

参考代码

#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.基站建设评测链接🔗