✅ 秋招备战指南 ✅

💡 学习建议：

• 先尝试独立解题
• 对照解析查漏补缺

🧸 题面描述背景等均已深度改编，做法和题目本质基本保持一致。

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

🌸 目前本专栏已经上线180+套真题改编解析，后续会持续更新的

春秋招笔试机考招合集 -> 互联网必备刷题宝典🔗

钉钉

题目一：小柯的表格格式化器

1️⃣：二次扫描算法，先统计每列最大宽度再格式化输出

2️⃣：字符串解析和空格补充计算，保证列对齐效果

难度：中等

这道题目的核心在于理解列对齐的规则，通过两次遍历实现高效的表格格式化。第一次遍历统计每列最大宽度，第二次遍历进行格式化输出，关键是正确计算每列需要补充的空格数量。

题目二：K 小姐的网络布线成本

1️⃣：使用两次 BFS 算法求解树的直径

2️⃣：根据给定成本函数计算最大可能费用

3️⃣：利用数学公式简化计算过程

难度：中等

这道题目结合了图论中的树直径求解和数学计算。关键是理解两次 BFS 求直径的正确性，以及成本函数的数学性质。通过 O(n) 时间复杂度找到最长路径，然后应用求和公式计算最终答案。

题目三：A 先生的地下停车场导航

1️⃣：反向 BFS 计算每个节点到终点的最短距离

2️⃣：分层构造路径，确保始终在最短路径上

3️⃣：贪心选择每层最小颜色，保证字典序最小

难度：中等偏难

这道题目需要在保证路径最短的前提下，构造字典序最小的颜色序列。核心思想是先通过反向 BFS 确定最短路径的层次结构，然后在每一层贪心选择最小颜色。算法巧妙地结合了最短路径搜索和贪心策略。

01. 小柯的表格格式化器

问题描述

小柯在一家科技公司担任数据分析师，她经常需要处理各种格式不规范的数据表格。公司刚引进了一套新的数据处理系统，要求所有输入的表格必须严格按列对齐，以便系统能够正确解析。

具体的对齐规则如下：

• 每行的第一列数据从位置 开始
• 每行的第二列数据从最小可能位置 开始，确保所有第一列数据的结束位置不超过
• 每行的第三列数据从最小可能位置 开始，确保所有第二列数据的结束位置不超过

以此类推...

换句话说，每列数据都必须左对齐，且相邻两列之间至少要有一个空格的间隔。系统要求输出的表格尽可能紧凑，即各列之间只保留必要的空格。

每行数据由一个或多个字段组成，字段之间用空格分隔。每个字段可以包含大小写拉丁字母、ASCII 标点符号及其他非空白 ASCII 字符（ASCII 码 至 ）。

输入格式

输入包含一个或多个数据行，直到文件末尾。所有行均以标准换行符结束。每行至少包含一个字段，每个字段长度为 到 个字符。字段之间用一个或多个空格分隔。输入的数据行可能包含前导和后导空格。输入文件中每行最多 个字符，总行数不超过 行。

输出格式

输出重新格式化后的对齐表格。输出需满足：

1. 行数与输入相同，字段的顺序保持不变

2. 不包含前导和后导空格

3. 通过一个或多个空格分隔字段，使得每行的第 个字段均从相同位置 开始

样例输入

start:integer; // begins here
stop:integer; // ends here
s:string;
c:char;//temp

样例输出

start:integer; // begins here
stop:integer;  // ends   here
s:string;
c:char;//temp

样例	解释说明
样例1	将输入的四行数据按列对齐：第一列在位置1开始，第二列在位置15开始，第三列在位置18开始。注意第三行只有两列数据，第四行的注释紧跟在字段后面

数据范围

• 
• 
• 

题解

这道题的核心思想是二次扫描：先统计每列的最大宽度，再进行格式化输出。

首先我们需要理解题目要求：把输入的多行文本按列对齐，使得每一列的开始位置都相同，同时保持紧凑（列间只有必要的空格）。

解决步骤：

1. 解析输入：读取所有行，将每行按空格分割成字段。需要注意处理多个连续空格的情况。

2. 统计列宽：遍历所有行的所有字段，记录每一列中最长字段的长度。

3. 格式化输出：再次遍历所有行，对于每一行：

   • 对于非最后一个字段，输出字段内容后补充空格，使得下一列能在正确位置开始
   • 对于最后一个字段，直接输出内容，不添加尾随空格

4. 空格计算：对于第 列（非最后列），需要输出的空格数 = 该列最大宽度 - 当前字段长度 + 1（保证至少一个空格间隔）

这种方法的时间复杂度是 ，其中 是所有字段的总数。空间复杂度也是 ，用于存储所有字段。

关键点在于正确处理输入解析（忽略多余空格）和空格补充的计算。

参考代码

Python

import sys
input = lambda: sys.stdin.readline().strip()

# 读取所有行并解析
lines = []
while True:
    try:
        line = input()
        if not line:
            break
        # 按空格分割，过滤空字符串
        words = [w for w in line.split(' ') if w]
        lines.append(words)
    except EOFError:
        break

# 统计每列的最大宽度
max_cols = max(len(row) for row in lines) if lines else 0
col_w = [0] * max_cols

for row in lines:
    for j, word in enumerate(row):
        col_w[j] = max(col_w[j], len(word))

# 格式化输出
for row in lines:
    result = []
    for j, word in enumerate(row):
        result.append(word)
        # 如果不是最后一个字段，添加必要的空格
        if j + 1 < len(row):
            spaces = col_w[j] - len(word) + 1
            result.append(' ' * spaces)
    print(''.join(result))

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    vector<vector<string>> data;
    string line;
    
    // 读取所有行并解析成字段
    while (getline(cin, line)) {
        vector<string> words;
        string cur = "";
        
        for (int i = 0; i <= (int)line.size(); ++i) {
            if (i == (int)line.size() || line[i] == ' ') {
                if (!cur.empty()) {
                    words.push_back(cur);
                    cur = "";
                }
            } else {
                cur += line[i];
            }
        }
        data.push_back(words);
    }
    
    // 计算每列最大宽度
    int max_col = 0;
    for (const auto& row : data) {
        max_col = max(max_col, (int)row.size());
    }
    
    vector<int> w(max_col, 0);
    for (const auto& row : data) {
        for (int j = 0; j < (int)row.size(); ++j) {
            w[j] = max(w[j], (int)row[j].size());
        }
    }
    
    // 输出格式化结果
    for (const auto& row : data) {
        for (int j = 0; j < (int)row.size(); ++j) {
            cout << row[j];
            // 非最后一列需要补充空格
            if (j + 1 < (int)row.size()) {
                int spaces = w[j] - (int)row[j].size() + 1;
                cout << string(spaces, ' ');
            }
        }
        cout << "\n";
    }
    
    return 0;
}

Java

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        List<List<String>> data = new ArrayList<>();
        String line;
        
        // 读取并解析所有行
        while ((line = br.readLine()) != null) {
            List<String> words = new ArrayList<>();
            String[] parts = line.split(" ");
            
            // 过滤空字符串
            for (String part : parts) {
                if (!part.isEmpty()) {
                    words.add(part);
                }
            }
            data.add(words);
        }
        
        // 计算每列的最大宽度
        int maxCol = 0;
        for (List<String> row : data) {
            maxCol = Math.max(maxCol, row.size());
        }
        
        int[] colWidth = new int[maxCol];
        for (List<String> row : data) {
            for (int j = 0; j < row.size(); j++) {
                colWidth[j] = Math.max(colWidth[j], row.get(j).length());
            }
        }
        
        // 格式化输出
        StringBuilder sb = new StringBuilder();
        for (List<String> row : data) {
            for (int j = 0; j < row.size(); j++) {
                sb.append(row.get(j));
                // 非最后一列补充空格
                if (j + 1 < row.size()) {
                    int spaces = colWidth[j] - row.get(j).length() + 1;
                    for (int k = 0; k < spaces; k++) {
                        sb.append(' ');
                    }
                }
            }
            sb.append('\n');
        }
        System.out.print(sb.toString());
    }
}

02. K 小姐的网络布线成本

问题描述

K 小姐是一家网络工程公司的技术顾问，负责为客户设计最经济的网络布线方案。最近她接到了一个特殊的项目：为一个新建的科技园区设计网络基础设施。

这个科技园区有 个建筑物，需要通过光纤网络连接。由于地理和成本限制，这些建筑物之间的连接呈现树形结构，即任意两个建筑物之间都有且仅有一条网络路径相连，不存在环路。

园区的网络设备供应商提供了一个独特的计费方案：当需要在两个建筑物之间建立连续的网络连接时，光纤铺设的成本按以下方式计算：

• 铺设第 公里光纤的成本是 万元
• 铺设第 公里光纤的成本是 万元
• 铺设第 公里光纤的成本是 万元
• ...
• 铺设第 公里光纤的成本是 万元

也就是说，如果要在两个建筑物之间铺设长度为 公里的连续光纤，总成本就是： 万元

现在 K 小姐想知道：在这个园区的网络拓扑结构中，任选两个建筑物进行直连，最高可能需要多少成本？

输入格式

第一行包含一个正整数 ，表示建筑物总数（建筑物编号从 到 ，其中 号是主要办公楼）。

接下来 行，每行包含三个正整数 、、，表示建筑物 和建筑物 之间有一条长度为 公里的连接路径。

输出格式

输出一个整数，表示可能的最高铺设成本。

样例输入

5
1 2 2
1 3 1
2 4 5
2 5 4

样例输出

135

样例	解释说明
样例1	建筑物连接关系形成树形结构，最长路径是从建筑物4到建筑物5，路径长度为5+2+4=11公里。成本计算： 万元。经计算验证，最长路径应该是9公里，成本为135万元

数据范围

• 
• 
• 

题解

这道题本质上是在一棵带权树中找到直径（最长的简单路径），然后根据给定的成本公式计算费用。

解题思路分为两个步骤：

1. 找到树的直径：树的直径是指树中任意两点间距离的最大值。可以用两次 BFS/DFS 来求解：

   • 从任意一个节点（如节点1）开始 BFS，找到距离它最远的节点
   • 从节点 开始 BFS，找到距离 最远的节点 ，此时 到 的距离就是树的直径

2. 计算成本：设直径长度为 ，则总成本为：

为什么两次 BFS 能找到直径？这是因为：

• 第一次 BFS 找到的最远点 一定是直径的一个端点
• 第二次 BFS 从 出发找到的最远点 就是直径的另一个端点

算法的时间复杂度是 ，空间复杂度是 。

参考代码

Python

import sys
from collections import deque
input = lambda: sys.stdin.readline().strip()

n = int(input())
# 构建邻接表
graph = [[] for _ in range(n + 1)]

for _ in range(n - 1):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))
    graph[b].append((a, c))

def bfs(start):
    """从start开始BFS，返回最远节点和距离"""
    dist = [-1] * (n + 1)
    dist[start] = 0
    q = deque([start])
    
    while q:
        u = q.popleft()
        for v, w in graph[u]:
            if dist[v] == -1:  # 未访问
                dist[v] = dist[u] + w
                q.append(v)
    
    # 找到距离最远的节点
    max_dist = 0
    farthest = start
    for i in range(1, n + 1):
        if dist[i] > max_dist:
            max_dist = dist[i]
            farthest = i
    
    return farthest, max_dist

# 两次BFS求直径
u, _ = bfs(1)  # 从节点1开始找最远节点u
v, diameter = bfs(u)  #